OpenJudge | 八皇后问题

总时间限制: 10000ms 内存限制: 65536kB

描述

在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。

输入

无输入。
输出
按给定顺序和格式输出所有八皇后问题的解（见Sample Output）。

样例输入

(null)

样例输出

No. 1
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 
No. 2
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 1 0 0 0 0 0 
No. 3
1 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 1 
0 0 1 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 1 0 0 0 0 
0 1 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
No. 4
1 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 
No. 5
0 0 0 0 0 1 0 0 
1 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 1 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 
0 0 1 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 1 0 0 0 0 
No. 6
0 0 0 1 0 0 0 0 
1 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 0 
0 0 0 0 0 1 0 0 
No. 7
0 0 0 0 1 0 0 0 
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 
0 0 0 1 0 0 0 0 
0 1 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 0 
0 0 0 0 0 1 0 0 
No. 8
0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
No. 9
0 0 0 0 1 0 0 0 
1 0 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 0 
...以下省略

提示

此题可使用函数递归调用的方法求解。

来源

计算概论05

解析

何为八皇后

八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

突破口

任两个皇后都不能处于同一条横行、纵行或斜线上

1. 同一行和同一列两者总有一个是不会重复的，看你以什么作为递归的传入条件。
2. 困难点在与斜线上——所谓斜线上，包括以上一个皇后所在的位置为交点$k=1$和$k=-1$这两条斜线。
   其中，$k=1$的斜线可用$y_1-x_1=y_2-x_2$来判断，$k=-1$的斜线可用$y_1+x_1=y_2+x_2$来判断

Code

#include <bits/stdc++.h>
using namespace std;array<pair<int, int>, 8> record = {};
array<int, 8> yR = {0};
array<array<bool, 8>, 8> res;bool judge(int x, int y) {if(yR[y] == 1) return false;for(int i = 0; i < x; i++) {if(record[i].first - record[i].second == x - y) return false;}for(int i = 0; i < x; i++) {if(record[i].first + record[i].second == x + y) return false;}return true;
}void dfs(int x, int *count) {if(x >= 8) {printf("No. %d\n", ++(*count));for(int i = 0; i < 8; ++i) {for(int j = 0; j < 8; ++j) {printf("%d ", res[i][j]);}printf("\n");}return;}for(int y = 0; y < 8; ++y) {if(judge(x, y) == 0) continue;record[x].first = x;record[x].second = y;res[y][x] = 1;yR[y] = 1;dfs(x+1, count);res[y][x] = 0;yR[y] = 0;}}int main() {int count = 0;for(int i = 0; i < 8; i++) {res[i].fill(0);}	dfs(0, &count);
}

鸣谢

连烟的递归从入门到精通

4. DFS、回溯算法(26分钟)