题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。
第 i 个数字表示在第 i 行的相应位置有一个棋子，如下：

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 33 个解。最后一行是解的总个数。

输入格式
一行一个正整数 n，表示棋盘是 n×n 大小的。

输出格式
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
6 <= n <= 13

题解

详情点击查看
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
#include <iostream>

using namespace std;

const int N = 30;

int n, cnt;
int p[N];
bool col[N], dg[N], udg[N];//记录行，主对角线，反对角线

void dfs(int u){
	if(u == n){
		if(cnt <= 2){
			for(int i = 0; i < n; i++){
				cout << p[i] <<" ";
			}
			cout << endl;
		}
		cnt++;
		return;
	}
	
	for(int i = 1; i <= n; i++){
		if(!col[i] && !dg[i + u] && !udg[u - i + n]){
			p[u] = i;
			col[i] = dg[i + u] = udg[u - i + n] = true;
			dfs(u + 1);
			col[i] = dg[i + u] = udg[u - i + n] = false;//回溯
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	
	dfs(0);
	
	cout << cnt << endl;
 	
	return 0;
	
}