n皇后问题.cpp

解决N皇后问题

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


#define MAXN     20


int n,m,flag;
int col[MAXN+1],a[MAXN+1];  //数组col[j]表示在棋盘第j列，col[j]行有一个皇后；数组a[k]表示第k条斜线上没有皇后
int b[2*MAXN+1],c[2*MAXN+1];  //数组b[k]表示第k条右高左低斜线上没有皇后，数组c[k]表示第k条左高右低斜线上没有皇后
void main()
{
	int j;
	char awn;
	printf("Enter n=");
	scanf("%d",&n);
	for(j=0;j<=n;j++)
	{
		a[j]=1;                                                    //初始化为1，表示没有放皇后
	}
	for(j=0;j<=2*n;j++)
	{
		b[j]=c[j]=1;                                               //初始化为1，表示没有放皇后
	}
	m=1;col[1]=1;flag=1;col[0]=0;
	do
	{
		if(flag){
			if(m==n)                                               //找到一个解
			{
				printf("列\t行");
				for(j=1;j<=n;j++)
					printf("%3d\t%d\n",j,col[j]);
				printf("Enter a character(Q/q for exit)!\n");
				cout << endl;
				scanf("%c",&awn);
				if(awn=='Q'||awn=='q')   exit(0);
				while(col[m]==n)
				{
					m--;                                           //清除关于第m-1列，col[m-1]行有皇后标志
					a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
				}
				col[m]++;                                          //调整第m列的皇后配置
			}
			else
			{                                                      //在第m列，col[m]行位置设定有皇后标志
				a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0;
				col[++m]=1;                                        //第m+1列，从第1行开始配置
			}
		}
		else                                                       //回溯调整
			{
				while(col[m]==n)                                   //回溯
				{
					m--;                                           //清除关于第m-1列，col[m-1]行有皇后的标志
					a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
				}
				col[m]++;                                          //调整第m列的皇后配置
			}
			flag=a[col[m]]&&b[m+col[m]]&&c[n+m-col[m]];
	}while(m!=0);
}