八皇后问题 DFS 结束条件是什么

来源:百度知道 编辑:UC知道 时间:2024/07/08 17:06:20
我写了一个程序,已经找到了92个解,但是程序找完以后停不下来了,成了死循环,我想问一下,结束条件是什么?
代码如下,供参考:

//8 Queen Problem
//Use DFS

#include <iostream>
#include <vector>
using namespace std;

void SetMainCrossLine(int Chess[][8], int x, int y, int Value)
{
for(int i=-8;i<8;i++)
{
if(x+i>=0 && x+i<8 && y+i>=0 && y+i<8)
{
if(Chess[x+i][y+i] != -1) //Check if there's already a Queen in it!
{
Chess[x+i][y+i] += Value ;
}
}
}
}

void SetViceCrossLine(int Chess[][8], int x, int y, int Value)
{
int sum = x+y;
for(int i=-8;i<8;i++)
{
if(x+i>=0 && x+i<8 && sum-x-i>=0 && sum-x-i<8)
{
if(Chess[x+i][y+i] != -1)
{
Chess[x+i][sum-x-i] += Value;
}
}
}
}

void SetRowAndColoum(int Chess[][8], int x, int y, int Value)
{
for(int i=0;i<8;i++)

放皇后q[i]=j,同时让第j列和过(i,j)位置的两条对角线变为不安全,即让C[j]=false,L[i-j+8]=false,R[i+j]=false。
查一下i是否为8,如果为8,则表明已经放完8个皇后,方案数Num加1,输出该方案下8个皇后的位置;否则,未到8个,则皇后数i加1再试着放,递归调用 Try(i+1)。
为了寻找不同方案,当一个方案输出后,要回溯,将先前放的皇后从棋盘上拿起来,看看能否再换一处位置。这时要将被拿起来的皇后的所在位置的第j列和两条对角线恢复为安全的
void Try( int i )
{
for ( int j = 1; j <= n; j++ )
{
if ( 第 i 行第 j 列没有攻击 )
{
在第 i 行第 j 列安放皇后;
if ( i == n ) 输出一个布局;
else Try ( i+1 );
撤消第 i 行第 j 列的皇后;
}
}
}

csdn上有八皇后问题的解法和源代码,可以参考下