【DFS】N皇后问题_每行输出一种方案,每种方案顺序输出皇后所在的列号,每个输出占5位宽度。如果不存

题目描述
在N*N的棋盘上放置N个皇后（n<=10）而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法。

输入
输入：n
输出
每行输出一种方案，每种方案顺序输出皇后所在的列号，每个数占5列（输出时按字典序）。若无方案，则输出no solute!
样例输入

 4
1

样例输出

2    4    1    3
3    1    4    2
1
2

八皇后问题衍生而来

AC 代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define abss(x) ((x)>(0)?(x):(-1)*(x))
#define maxs(a,b) ((a)>(b)?(a):(b))
#define mins(a,b) ((a)<(b)?(a):(b))
#define FOR(i,a,b) for(register int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(register int i=(a);i>=(b);i--)
#define mem(a) memset(a,0,sizeof(a))
const int INF (1<<30);
const int inf (-1<<30);
using namespace std;

int matx[10][10];
int n,ans;

bool check_edge(int x,int y){
	if(x>=1 and x<=n and y>=1 and y<=n)
		return true;
	return false;
}

bool check_unblocked(int x,int y){
	FOR(i,1,n){
		if(matx[i][y]==1)return false;
		if(matx[x][i]==1)return false;
	}
	int tx=x,ty=y;
	while(check_edge(tx,ty)) if(matx[tx++][ty++]==1)return false;
	tx=x,ty=y;
	while(check_edge(tx,ty)) if(matx[tx--][ty++]==1)return false;
	tx=x,ty=y;
	while(check_edge(tx,ty)) if(matx[tx++][ty--]==1)return false;
	tx=x,ty=y;
	while(check_edge(tx,ty)) if(matx[tx--][ty--]==1)return false;
	return true;
}

void print(){
	FOR(i,1,n)
		FOR(j,1,n)
			if(matx[i][j]==1) printf("%5d",j);
	putchar('\n');
}

void dfs(int x,int y,int queen){
	if(x>queen)return;
	if(queen==n){
		print();
		ans++;
		return;
	}
	FOR(nx,x+1,n)
		FOR(ny,1,n){
			if(matx[nx][ny]==0 and check_unblocked(nx,ny)){
				matx[nx][ny]=1;
				dfs(nx,ny,queen+1);
				matx[nx][ny]=0;
			}
		}
}

int main(){
	ans=0;
	cin>>n;
	FOR(i,1,n){
		mem(matx);
		matx[1][i]=1;
		dfs(1,i,1);
	}
	if(ans==0)cout<<"no solute!\n";
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72