n皇后问题.txt

N皇后问题 主要是运用递归来做的一个算法

//#include "stdafx.h"
#include<stdio.h>
#define M 6
char chessboard[M][M];
int QueenPlace(int LocX,int LocY);
int N_Queens(int LocX,int LocY,int Queens)
{
	int i,j;
	int Result = 0;
	if(Queens == M)	
		return 1;
	else
		if(QueenPlace(LocX,LocY))
		{
			chessboard[LocX][LocY] = 'Q';
			for(i=0;i<M;i++)
				for(j=0;j<M;j++)
				{
					Result += N_Queens(i,j,Queens+1);
					if(Result>0)
						break;
				}
				if(Result > 0)
					return 1;
				else
				{
					chessboard[LocX][LocY] = ' ';
					return 0;
				}
		}
		else
			return 0;
		}
 int QueenPlace(int LocX,int LocY)
 {
	 int i,j;
	 if(chessboard[LocX][LocY] != ' ')
		 return 0;
	 for(j=LocY-1;j>=0;j--)
		 if(chessboard[LocX][j] != ' ')
			 return 0;
     for(j=LocY+1;j<M;j++)
		 if(chessboard[LocX][j] != ' ')
			 return 0;
	 for(i=LocX-1;i>=0;i--)
		 if(chessboard[i][LocY] != ' ')
			 return 0;
	 for(i=LocX+1;i<M;i++)
		 if(chessboard[i][LocY] != ' ')
			 return 0;

			i = LocX-1;
			j = LocY-1;
			while(i>=0 && j>=0)
				if(chessboard[i--][j--] != ' ')
					return 0;
				i = LocX+1;
				j = LocY-1;

				while (i<M && j>=0)
					if(chessboard[i++][j--] != ' ')
						return 0;
					i = LocX -1;
					j = LocY +1;
					while (i>=0 && j<M)
						if(chessboard[i--][j++] != ' ')
							return 0;
					i = LocX+1;
					j = LocY+1;
					while (i<M && j<M)
						if(chessboard[i++][j++] != ' ')
							return 0;
		return 1;
 }
void main()
{
	int i,j;
	for(i=0;i<M;i++)
		for(j=0;j<M;j++)
			chessboard[i][j] = ' ';
		int num1=0,num2=0,num3=0;
		    N_Queens(num1,num2,num3);
           while(chessboard[num1][num2]==' ')
		  {
		      N_Queens(num1,++num2,num3);
			  if(num2>=M)
				  break;
		  }
		
		printf("The graph of 8 Queens on the chessboard .\n");
		printf("   0   1   2   3   4   5   6   7 \n");
		printf(" +---+---+---+---+---+---+---+---+\n");
		for(i=0;i<M;i++)
		{
			printf("%d|",i);
			for(j=0;j<M;j++)
				printf(" %c |",chessboard[i][j]);
			printf("\n +---+---+---+---+---+---+---+---+\n");
		}
}