#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);
}