八皇后的递归和非递归的解法(C++)

八皇后的递归和非递归的解法(C++)

//描述：用递归和非递归模拟n皇后问题
//输入：问题的规模:n
//输出：皇后放置的方法排列和总数

#include<iostream>
#include<iomanip>
#include<cmath>
#include<stack>
using namespace std;

//利用递归求解皇后问题 x[i]表示皇后放在第i行第x[i]列
static int count;

//判断如果皇后放在第i行，第j列是否与前面的皇后冲突
bool place(int i,int j,int* path)//path存放路径
{
int row;
for(row=0;row<i;row++)
{
   if(abs(row-i)==abs(path[row]-j))//在同一条斜线上
    return false;
   if(j==path[row])//在同一列
    return false;
}
return true;
}

//利用递归来求解，而且当row==0时，即求解全局的解
//path[n]用来存放路径
void queen(int row,int* path,int n)
{
if(row==n)
{
   //输出结果，并将办法数加1
   for(int i=0;i<n;i++)
   {
    cout<<setw(5)<<left<<path[i];
      }
   cout<<endl;
         count++;  
}
else
{
      int j;//表示当前列是否可行
      for(j=0;j<n;j++)
     {
   //如果可行，则放置并且递归调用处理下一行
     
     if(place(row,j,path))
     {
    path[row]=j;
    //这里相当于入栈的过程
    queen(row+1,path,n);
     }
      }
   }
}

//利用迭代来求解
void queen_another(int n,int* path)
{

int i=0;
     for(i=0;i<n;i++)
{
   int j=0;
   for(;j<n;j++)
   {
    if(place(i,j,path))
    {

     path[i]=j;
     cout<<"row "<<i<<"col   "<<j<<endl;
     break;
    }
   }
   //没有合适的位置，所以要回溯到上一个最合适的节点
   if(j==n)
   {
    i--;
    while(i>=0)
    {
     int k=path[i]+1;
     while(k<n&&!(place(i,k,path)))
      k++;
     if(k==n)
      i--;
     else
     {
      path[i]=k;
      break;
     }
    }
    if(i<0)
    {
     cout<<"there is no way "<<endl;
     return;
    }
   }
}
if(i==n)
for(int j=0;j<n;j++)
{
   cout<<setw(5)<<left<<path[j];
   path[j]=-1000;
}
}

//利用栈来模拟递归，在某个扩展节点出处，将所有符合条件的节点加入到里面
struct pos
{
int row;
int col;
};
//找到当前最合适的节点,如果没有找到则返回-1
int find_col(int row,int col,int* path,int n)
{
int j;
for(j=col;j<n;j++)
{
   if(place(row,j,path))
    return j;
}
if(j==n)
   return -1;
}
//利用栈来模拟八皇后问题
void stack_stimu(int n,int* path)
{
stack<struct pos> s;
int currow=0;
int flag=0;
//主要结构分为两部分，第一 按照正常顺序寻找节点
//然后找出回溯的情况：在八皇后问题中主要有两中：1.到达结尾 找出路径 2.当前行没有满足条件的位置
while(true)
{
   if(currow<n)
    {
        int col=find_col(currow,0,path,n);
           if(col!=-1)
        {
     pos node;
        node.row=currow;
        node.col=col;
        s.push(node);
     path[currow]=col;
        currow++;
        }
     else
      flag=1;
     }
else
   {
    for(int i=0;i<n;i++)
     cout<<setw(5)<<left<<path[i];
    cout<<endl;
    count++;
    flag=1;
    }
// 进行回溯
if(flag==1)
{
          //描述了回溯的过程
          while(!s.empty())
         {
          pos temp=s.top();
          if(temp.col!=7)
         {
           //查找当前最适合的节点，并入栈
          int j=find_col(temp.row,temp.col+1,path,n);
         if(j!=-1)
         {
     pos node;
     node.row=temp.row;
     node.col=j;
     s.pop();
     s.push(node);
     path[temp.row]=j;
     currow=temp.row+1;
     flag=0;
     break;
        }
      else
     s.pop();
       }
       else
           s.pop();
            }
    if(s.empty())
     return;//函数的出口处
        }
     }//end for while(true)
}

int main()
{
cout<<"Queen Place Problem:"<<endl;
cout<<"Input the value of n"<<endl;
int n;
cout<<"   n>";
cin>>n;
int* path=new int[n];

//初始化
for(int i=0;i<n;i++)
   path[i]=-1000;

//queen_another(n,path);
//queen(0,path,n);
stack_stimu(n,path);
cout<<"the count is: "<<count<<endl;
getchar();
getchar();
     return 0;
}