n-queens.cpp

此N皇后问题更具通用性

#include <stdlib.h>
#include <stdio.h>
#include <conio.h> 

char Chessboard[8][8]; /*声明8＊8的空白棋盘*/ 
int QueenPlace(int LocX,int LocY) /*判断传入坐标本身及入八个方向上是否有皇后*/
{
	int i,j;
	if(Chessboard[LocX][LocY] != 'X')
		return 0;
	for(j=LocY-1;j>=0;j--)
		if(Chessboard[LocX][j] != 'X')
			return 0;
		for(j=LocY+1;j<8;j++)
			if(Chessboard[LocX][j] != 'X')
				return 0;
			for(i=LocX-1;i>=0;i--)
				if(Chessboard[i][LocY] != 'X')
					return 0;
				for(i=LocX+1;i<8;i++)
					if(Chessboard[i][LocY] != 'X')
						return 0;
					i= LocX - 1;
					j= LocY - 1;
					while (i>=0&&j>=0)
						if(Chessboard[i--][j--] != 'X')
							return 0;
						i= LocX + 1;
						j= LocY - 1;
						while (i<8&&j>=0)
							if(Chessboard[i++][j--] != 'X')
								return 0;
							i= LocX - 1;
							j= LocY + 1;
							while (i>=0&&j<8)
								if(Chessboard[i--][j++] != 'X')
									return 0;
								i= LocX + 1;
								j= LocY + 1;
								while (i<8&&j<8)
									if(Chessboard[i++][j--] != 'X')
										return 0;
		return 1;
}
int N_Queens(int LocX, int LocY, int Queens) /*递归*/
{
int i,j;
int Result=0;
if(Queens == 8)/*递归结束条件*/
 return 1;
else if(QueenPlace(LocX,LocY))/*递归执行部分*/
{
	Chessboard[LocX][LocY] = 'Q';
	for(i=0;i<8;i++)
		for(j=0;j<8;j++)
		{
			Result += N_Queens(i,j,Queens+1);
			if(Result>0)
				break;
		}
		if(Result>0)
			return 1;
		else
		{
			Chessboard[LocX][LocY] = 'X';
		}
}
else
return 0;
}
void main() /*主程序*/
{
int i,j;
for(i=0;i<8;i++)
for(j=0;j<8;j++)
Chessboard[i][j] = 'X';
N_Queens(0,0,0);
printf("the graph of 8 Queens on the Chessboard.is:\n");
for(i=0;i<8;i++)
for(j=0;j<8;j++)
{
	if(Chessboard[i][j] == 'Q')
		printf("(%d,%d)n",i,j);
	printf("\n");
}
getch();
}