学步园

#include<iostream><br /> using namespace std;</p> <p>#define N 8<br /> //N代表皇后数<br /> void queen()<br /> {<br /> int Count=0; //计算总共的解的数量<br /> int column[N+1]; //column[m]=n表示第m行，第n行放置了皇后,这里下表并从0开始<br /> int row[N+1]; //row[m]=1表示第m行没有皇后，=0表示有皇后<br /> int b[2*N+1]; //b[m]=1表示第m条主对角线没有皇后，<br /> int c[2*N+1]; //c[m]=1表示第m条次对角线没有皇后，=0表示有皇后<br /> int numQueen=1; //计数已经放置的皇后数目，当numQueen=N时候则表示已经完成探测<br /> int good=1; //good=1表示没有发生冲突,good=0表示发生冲突</p> <p> //初始化这些标记<br /> for(int j=0;j<N+1;++j)<br /> {<br /> row[j]=1;<br /> }<br /> for(int j=0;j<2*N+1;++j)<br /> {<br /> b[j]=c[j]=1;<br /> }<br /> column[1]=1;<br /> column[0]=0; //初始化第一行第一列，第二行第二列放置皇后<br /> do<br /> {<br /> //没有发生冲突，则继续向下探测，增加皇后或者判断当前是否是解<br /> if(good)<br /> {<br /> //当前皇后数是解，打印，继续向下探测<br /> if(numQueen==N)<br /> {<br /> Count++;<br /> cout<<"找到解"<<endl;<br /> for(int j=1;j<N+1;++j)<br /> {<br /> cout<<j<<"列"<<column[j]<<"行"<<endl;<br /> }<br /> //最后一个棋子向下移动,移动到本列最后一个<br /> while(column[numQueen]==N)<br /> {<br /> numQueen--; //皇后数减1，即列数减1，回溯<br /> //回溯后将该列以及该列最后一行状态位修改<br /> //第numQueen列column[numQueen]行处状态位置修改<br /> row[column[numQueen]]=1;<br /> b[numQueen+column[numQueen]]=1;<br /> c[N+numQueen-column[numQueen]]=1;<br /> }<br /> column[numQueen]++; //回溯至上一行，向上一行的下一列继续探测<br /> }<br /> //当前不是解，那么继续向下探测<br /> else<br /> {<br /> //改变该位置对应标志<br /> row[column[numQueen]]=0;<br /> b[numQueen+column[numQueen]]=0;<br /> c[N+numQueen-column[numQueen]]=0;<br /> //本次位置没有发生冲突，也不是正确解，那么就应该向下探测下一列的第一行<br /> column[++numQueen]=1;<br /> }<br /> }<br /> //如果当前发生了冲突，就在本列继续向下，如果到了本列最后一行，则回溯到上一列<br /> else<br /> {<br /> while(column[numQueen]==N) //到了本列最后一行，还是冲突，那么回溯到上一列<br /> {<br /> numQueen--;<br /> row[column[numQueen]]=1;<br /> b[numQueen+column[numQueen]]=1;<br /> c[N+numQueen-column[numQueen]]=1;<br /> }<br /> column[numQueen]++; //发生冲突了，又没有到本列的最后一行，那么在本列继续向下一行探测<br /> }<br /> //检测放置了这个位置后是否冲突<br /> good=row[column[numQueen]]&b[numQueen+column[numQueen]]&c[N+numQueen-column[numQueen]];<br /> }while(numQueen);<br /> cout<<N<<"皇后总共找到解："<<Count<<"个"<<endl;<br /> }<br /> void main()<br /> {<br /> queen();<br /> system("pause");<br /> }<br />

这种非递归方法还是比较容易理解的

另外还有递归方法，先来看一下递归算法的伪代码

void trial(int row)

{

     //递归时候，我们从第0行开始，然后每次递归时候，都向下一行，一直到棋盘的最后一行

     //这时候就表示已经是正确的解了，所有进入该函数首先判断是否是正确的解

     if(row>N)

    {

         //输出此时的棋盘

    }

    else

    {

        for(int i=0;i<N;++i)

        { 

             //不是解，这时候需要在本行的每一列开始试探放旗子，如果可以的话继续向下递归

             #修改记录冲突的数组

              if(放在这个位置不会冲突)

             {

                     trial(row+1);

             }

             放在这里冲突，那么修改回记录的数组，继续下一列

        }

     }

}

下面给出递归的

void EightQueen (int row)<br /> {<br /> if(row>N)<br /> {<br /> PrintMap(); //打印棋盘<br /> }<br /> else<br /> {<br /> int column;<br /> for (column = 0; column < N; ++column)<br /> {<br /> A[row]= column; //代表第row行的第column列放皇后<br /> if (IsCorrect (row, column)) //判断在第row行的第column列放皇后是否可行<br /> {<br /> EightQueen (row + 1);<br /> }<br /> //将标记数组修改回原来<br /> }<br /> }<br /> }

查看源代码示例