今天尝试写了下八皇后的代码,但是运行的时候发现无法跳出递归。
疯狂输出第一组解法。查了半天无果。还请大佬们给代码看看病,
诊断诊断。下面贴出代码。
(对于代码中的棋盘数组vist[i][j]+1=1的解释是,某个格子可能被多个棋子影响,拿掉其中一个棋子后格子可能还在其他棋子的影响下不能放置,所以采用的是+-1的方式表示影响该格子的棋子数,如果vist[i][j]大于0则必然不能放置。)
#include<stdio.h>
int ans[9] = { 0 }, vist[10][10] = {0};//vist数组模棋盘,ans表示每列能放下棋子的行坐标
void solve_queen(int x);//用来遍历可能结果的函数
void _vist(int m,int n);
void _clear(int m1,int n1);
int main(void)
{
printf("This program will solve the 8 queen problem\n.Button the Enter to Solve it\n");
getchar();
solve_queen(1);
getchar();
getchar();
return 0;
}
void _vist(int m,int n)
{
int i1=1, j1=1;
vist[m][n]+=1;//放下棋子的那一格数值+1表示遍历过
while (n + j1 <= 8)//与该棋子同行的不能再放
{
vist[m][n + j1] += 1;
j1+=1;
}
j1 = 1;
while ((m + i1 <= 8) && (n + j1 <= 8))//与该棋子在斜向下45°方向的位置都不能放
{
vist[m + i1][n + j1]+= 1;
i1+=1, j1+=1;
}
i1 = j1 = 1;
while ((n + j1 <= 8) && (m - i1 >= 1))//与该棋子在斜向上45°方向的位置都不能放
{
vist[m - i1][n + j1] += 1;
i1+=1, j1+=1;
}
}
void _clear(int m1,int n1)//用于回溯时,清除拿回的那颗棋子对棋盘放置区域的影响。
{
int i2 = 1, j2 = 1;
vist[m1][n1] = 0;
while (n1 + j2 <= 8)
{
vist[m1][n1 + j2] -= 1;
j2+=1;
}
j2 = 1;
while ((m1 + i2 <= 8) && (n1 + j2 <= 8))
{
vist[m1 + i2][n1 + j2] -= 1;
i2+=1, j2+=1;
}
i2 = j2 = 1;
while ((n1 + j2 <= 8) && (m1 - i2 >= 1))
{
vist[m1 - i2][n1 + j2] -= 1;
i2+=1, j2+=1;
}
}
void solve_queen(int x)
{
int i;
if (x > 8)
{
for (i=1;i<= 8;i++)
printf("%d ", ans[i]);
printf("\n");
}
for (i = 1;i <= 8;i++)
{
if (!vist[i][x])
{
ans[x] = i;
_vist(i, x);
solve_queen(x + 1);
_clear(i, x);
}
}
}