网站建设学习视频,网络营销赚钱,wordpress 慢集市,国外域名注册做违法网站总时间限制: 10000ms 内存限制: 65536kB
描述
在国际象棋棋盘上放置八个皇后#xff0c;要求每两个皇后之间不能直接吃掉对方。
输入
无输入。 输出 按给定顺序和格式输出所有八皇后问题的解#xff08;见Sample Output#xff09;。
样例输入
(null)样例输出
No. 1
…总时间限制: 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的国际象棋棋盘上放置八个皇后使得任何一个皇后都无法直接吃掉其他的皇后为了达到此目的任两个皇后都不能处于同一条横行、纵行或斜线上。
突破口
任两个皇后都不能处于同一条横行、纵行或斜线上
同一行和同一列两者总有一个是不会重复的看你以什么作为递归的传入条件。困难点在与斜线上——所谓斜线上包括以上一个皇后所在的位置为交点 k 1 k1 k1和 k − 1 k-1 k−1这两条斜线。 其中 k 1 k1 k1的斜线可用 y 1 − x 1 y 2 − x 2 y_1-x_1 y_2-x_2 y1−x1y2−x2来判断 k − 1 k-1 k−1的斜线可用 y 1 x 1 y 2 x 2 y_1x_1 y_2x_2 y1x1y2x2来判断
Code
#include bits/stdc.h
using namespace std;arraypairint, int, 8 record {};
arrayint, 8 yR {0};
arrayarraybool, 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(x1, 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分钟)
