#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <time.h>
using namespace std;

#define START 1
#define MAX 30

//八皇后問(wèn)題 回溯法
/*
輸入
4

輸出
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
*/
int where[MAX]={0};//初始化，未開(kāi)始訪問(wèn)

bool isok(int now)
{
	int i;
	for(i=1;i<now;i++)
		if((where[i]-where[now])==(i-now)||where[i]==where[now]) return false;
	return true;
}

void print(int num)
{
	int i,j;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
			if(where[i]==j) cout<<"1 ";
			else cout<<"0 ";
		cout<<endl;
	}
	cout<<endl;
//	system("pause");
}
bool Queue(int num)
{
/*
	回溯法的整體思路：
	次數(shù)=1；初始化所有狀態(tài)x[次數(shù)]為0（1<=x[次數(shù)]<=限制）
	while(次數(shù)〉=1）
	{
		x[次數(shù)]++；
		while(x[次數(shù)]<=限制）
		{
			if(x[次數(shù)]符合條件) break;
			else x[次數(shù)]++；
		} 
		if(x[次數(shù)]<=限制)
		{
			if(次數(shù)==總次數(shù)) return true;
			else 次數(shù)++;
		}
		else
		{
			x[次數(shù)]=0；
			次數(shù)--；
		}
	}
	return false;
*/
	int k=1;
	while(k>=1)
	{
		where[k]++;//訪問(wèn)第k行的下一個(gè)位置
		while(where[k]<=num)
		{
			if(isok(k)) break;
			else where[k]++;//這一位置不符合條件，訪問(wèn)下一個(gè)位置
		}
		if(where[k]<=num) 
		{	//在第k行找到了符合條件的位置
			if(k==num) 
			{	//找到所有位置
				return true;
			}
			else k++;//找到部分位置，進(jìn)行對(duì)k+1行的訪問(wèn)
		}
		else 
		{	//回溯
			where[k]=0;//將當(dāng)前點(diǎn)的訪問(wèn)位置置為初始化
			k--;
		}
//		print(num);
	}
	return false;
}

int main()
{
	int num,timea,timeb;
	cout<<"輸入棋盤(pán)大小:";
	cin>>num;
	timea=time(NULL);
	if(Queue(num)) print(num);
	else cout<<"沒(méi)有解決方案"<<endl;
	timeb=time(NULL);
	cout<<"所花時(shí)間為"<<timeb-timea<<"s"<<endl;
	return 0;
}