题目描述
给定一个 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 个棋子,请你找出所有满足上述条件的棋子放置方案。
输入格式
共一行,一个整数 N。
输出格式
共四行,前三行每行输出一个整数序列,用来描述一种可行放置方案,序列中的第 i 个数表示第 i 行的棋子应该摆放的列的位置。
这三行描述的方案应该是整数序列字典序排在第一、第二、第三的方案。
第四行输出一个整数,表示可行放置方案的总数。
数据范围
6≤N≤13
输入样例:
6
输出样例:
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
前提知识
如何标记一个二维数组每一条主对角线和副对角线呢?
对于坐标(x,y),y-x唯一标记了每一条主对角线(注意可能是负值,所以后面加了个n,保证为正值),y+x唯一标记了每一条副对角线;
思路
我们在判断每一皇后的位置是否合法时,可以直接根据皇后的坐标计算出其所在的列,主对角线和副对角线,然后判断所在列和对角线有没有被占用,如果没有被占用,则进入下一状态;直到行进行到第n+1行时,到达递归边界,输出结果;
注意事项
1、解法一没有用额外的标记数组,虽然省了空间,但是每一次判断都需要计算,所以超时了;
2、解法二用了额外的标记数组,直接判断即可,不用计算,但如果使用标记数组一定要记得状态回滚;
3、本题让输出前3个较小的答案,递归的过程就是结果集由小到大遍历的过程,所以直接输出前3个即可;
算法1
C++ 代码
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 15;
int C[N];//存放每一行皇后的列下标
int tot = 0;//存放总的方案数
void DFS(int cur, int n){
//递归边界,找到一个合法的
if(cur == n + 1){
tot++;
//递归的过程就是结果集由小到大的遍历
if(tot <= 3){
for(int i = 1; i <= n; i++){
if(i != 1) printf(" ");
printf("%d", C[i]);
}
printf("\n");
}
}
else{
//尝试把第cur行的皇后放在第j列
for(int j = 1; j <= n; j++){
int ok = 1;
C[cur] = j;
//检查是否和前面行的皇后冲突
for(int i = 1; i < cur; i++){
if(C[cur] == C[i] || cur - C[cur] == i - C[i] || cur + C[cur] == i + C[i]){
ok = 0; break;
}
}
if(ok) DFS(cur + 1, n);//如果合法,继续递归
}
}
}
int main(){
int n;
scanf("%d", &n);
DFS(1, n);
printf("%d\n", tot);
return 0;
}
算法2
C++ 代码
#include <iostream>
using namespace std;
const int N = 15;
int C[N], Z[N * 2], F[N * 2];//C标记列是否放满, Z标记主对角线,F标记副对角线
int tot = 0, path[N];//存放总的方案数
void DFS(int row, int n){
//递归边界,找到一个合法的
if(row == n + 1){
tot++;
//递归的过程就是结果集由小到大的遍历
if(tot <= 3){
for(int i = 1; i <= n; i++){
if(i != 1) printf(" ");
printf("%d", path[i]);
}
printf("\n");
}
}
else{
//尝试把第cur行的皇后放在第j列
for(int col = 1; col <= n; col++){
if(!C[col] && !Z[col - row + n] && !F[col + row]){
path[row] = col;
C[col] = Z[col - row + n] = F[col + row] = 1;//准备进入下一状态
DFS(row + 1, n);
C[col] = Z[col - row + n] = F[col + row] = 0;//状态回滚
}
}
}
}
int main(){
int n;
scanf("%d", &n);
DFS(1, n);
printf("%d\n", tot);
return 0;
}