题目描述
给定一个 $N×N$ 的棋盘,请你在上面放置 $N$ 个棋子,要求满足:
- 每行每列都恰好有一个棋子
- 每条对角线上都最多只能有一个棋子
1 2 3 4 5 6
-------------------------
1 | | O | | | | |
-------------------------
2 | | | | O | | |
-------------------------
3 | | | | | | O |
-------------------------
4 | O | | | | | |
-------------------------
5 | | | O | | | |
-------------------------
6 | | | | | O | |
-------------------------
上图给出了当 N=6 时的一种解决方案,该方案可用序列 2 4 6 1 3 5
来描述,该序列按顺序给出了从第一行到第六行,每一行摆放的棋子所在的列的位置。
请你编写一个程序,给定一个 $N×N$ 的棋盘以及 $N$ 个棋子,请你找出所有满足上述条件的棋子放置方案。
样例
输入样例:
6
输出样例:
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
算法1
(暴搜)
类似八皇后的做法。
注意需要用path
来记录方案,
错误的方案输出方法
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n;j ++ )
if (col[j] == 1){
cout << j << ' ';
break;
}
cout << endl;
因为当搜索完,每列必定都被填上数字了,所以col[1]~col[N]
必定都为1
,所以必须在搜索过程中用path
数组记录填在了哪列。
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
const int N = 50;
int col[N], row[N], udg[N], dg[N];
int cnt;
int n;
int path[N];
void dfs(int u){//u表示当前扫描到第u行。
if (u == n + 1) {
cnt ++;
if (cnt > 3) return ;
for (int i = 1; i <= n; i ++ ) cout << path[i] << ' ';
cout << endl;
}
for (int i = 1; i <= n; i ++ )
if (!col[i] && !udg[i - u + n] && !dg[i + u]){
path[u] = i;
col[i] = udg[i - u + n] = dg[i + u] = 1;
dfs(u + 1);
col[i] = udg[i - u + n] = dg[i + u] = 0;
path[u] = 0;
}
}
int main(){
cin >> n;
dfs(1);
cout << cnt << endl;
return 0;
}