这么经典的问题一直没认真思考，现在终于弄出来了，还费了点周折。
用二维数组表示棋盘，空的全部置0。大概思路是递归处理每一行，一开始可以从n=4来思考，简单点。放棋子到合法位置上（置1），非法的位置就是为2的位置，已经被判断是不能放的了；然后使这颗棋子位置对应的列和斜行成为不能放的位置（置2），然后处理下一行。这样到最后一行输出棋盘结果。
下面的程序思路清晰，结果没考虑周全，有错误
#include <stdio.h>
#include <stdlib.h>
#define N 4
int a[N][N]={{0}}; //0表示没有放棋但还可能放，1表示放下，2表示不能放
int jie=0;
int num_of_jie=0;
void queen(int row,int n) //处理某一行
{
int i,j,k;
if (jie &&(row==n)) { //输出
for(i=0;i<n;i++) {
for(j=0;j<n ;j++ )
if(a[i][j]!=1)
printf("0");
else
printf("1");
printf("\n");
}
printf("\n");
jie=0;
num_of_jie++;
}
else
for (i=0;i<n ;i++ )
{
if (a[row][i]==2) continue; //该位置不能放棋
a[row][i]=1; //放棋
if(row==n-1) //最后一行处理完成
jie = 1;
for (j=row+1;j<n ;j++ )
a[j][i]=2; //放的棋子这一列不能再放
for(j=1;(j<(n-i))&&(j<(n-row)) ;j++) //注意终止条件，棋子可以在对角线上也可能在下
a[row+j][i+j]=2; //对的斜行也不能放
for(k=1;(k<=i)&&(k<(n-row)) ;k++) //对的反斜行也不能放
a[row+k][i-k]=2;
queen(row+1,n); //递归处理下一行
for(--j;j>0;j--) // 恢复放这颗棋以前的状态，继续考虑下一个i值的可能性，这里利用j先恢复斜行
a[row+j][i+j]=0;
for(--k;k>0;k--) //恢复反斜行
a[row+k][i-k]=0;
for (j=n-1;j>=row ;j-- ) //恢复列，和这次放棋的位置
a[j][i]=0;
}
}
int main()
{
queen(0,N);
printf("\n共有%d组解\n",num_of_jie);
return 0;
}
|
错就错在没有考虑这一个事实：递归后，恢复当前棋子的影响。有的位置在这粒棋子之前，就已经被判定为非法位置了（受前面某行放棋的影响），却恢复成了合法位置。于是程序会可能在这一本来是非法的位置上放棋，最终导致输出错误结果。这个错误程序在八皇后时输出了229个解，明显是不对的。
这使我知道了，每次恢复放棋所影响的位置为0，应该是只有该颗棋子影响的位置才恢复，之前棋子同样影响的位置是应该保留的。怎么实现呢？我用一个数组模拟栈，先将受影响的棋子的坐标放进去，后面再恢复，这样就可以通过判断来保证达到上面所说。修改后的程序如下
#include <stdio.h>
#include <stdlib.h>
#define N 8
int a[N][N]={{0}}; //0表示没有放棋但还可能放，1表示放下，2表示不能放
int jie=0; //有解的标志
int num_of_jie=0;
void queen(int row,int n) //处理某一行
{
int i,j,k;
int stack[4*N]={0}; //利用一个数组作为栈，存储和恢复不可以放棋的位置
int stackindex;
int tempx,tempy;
if (jie &&(row==n)) { //输出
for(i=0;i<n;i++) {
for(j=0;j<n ;j++ )
if(a[i][j]!=1)
printf("0");
else
printf("1");
printf("\n");
}
printf("\n");
jie=0;
num_of_jie++;
}
else
for (i=0;i<n ;i++ )
{
if (a[row][i]==2) continue; //该位置不能放棋
a[row][i]=1; //放棋
if(row==n-1) //最后一行处理完成
jie = 1;
stackindex=0;
for (j=row+1;j<n ;j++ )
if(a[j][i]!=2) { //如果等于2，表示之前的棋子已经使这里不能放棋了，属于前面旗子的处理范围，不过问
a[j][i]=2;
stack[stackindex++]=j; //记录横坐标
stack[stackindex++]=i; //记录纵坐标
}
else
continue;
for(j=1;(j<(n-i))&&(j<(n-row)) ;j++) //对的斜行也不能放。注意终止条件，棋子可以在对角线上也可能在下
if(a[row+j][i+j]!=2) {
a[row+j][i+j]=2;
stack[stackindex++]=row+j;
stack[stackindex++]=i+j;
}
else
continue;
for(k=1;(k<=i)&&(k<(n-row)) ;k++) //对的反斜行也不能放
if(a[row+k][i-k]!=2) {
a[row+k][i-k]=2;
stack[stackindex++]=row+k;
stack[stackindex++]=i-k;
}
else
continue;
queen(row+1,n); //递归处理下一行
while(stackindex>0) { //恢复这颗棋子影响的位置，让它们又能放棋。
tempy=stack[--stackindex];
tempx=stack[--stackindex];
a[tempx][tempy]=0;
}
a[row][i]=0; //恢复这颗棋子的位置为空
}
}
int main()
{
queen(0,N);
printf("\n共有%d组解\n",num_of_jie);
return 0;
}
|
阅读(352) | 评论(0) | 转发(0) |
