当前位置 博文首页 > 用心编码：8 皇帝问题（皇帝还是比较牛逼） - 算法
一、问题描述
有一个 8 * 8 的棋盘，和 8 个皇后，皇后的攻击规则：任意一个皇后可以攻击同一行、同一列、正反对角线上的皇后。问题：如何摆放8个皇后，可以让她们互相不攻击。
提示：一行或一列只能放一个皇后。
二、解题思路
采用深度优先遍历方式，从第0行开始，逐行查看每一列中那些位置可以摆放皇后，也就是每一行需要扫描8列，而且还需要判断当前位置和摆放过皇后的位置是否符合规则。
三、DFS（深度优先搜索）
套路：
// 参数n：问题规模
void dfs(int n){
// dfs 出口
if(){
...
return;
}
// dfs body
处理当前内容
// dfs 递归
处理当前内容与子问题的关系
}二叉树遍历
package com.daxiong.day6;
/**
* 1
* 2 3
* 4 5 6 7
* */
public class TowTree {
private static int[] tree = {0,1,2,3,4,5,6,7}; // 第0为站位，不参与实际问题
public static void main(String[] args) {
dfs(1);
}
// 二叉树前序遍历
public static void dfs(int root){
if(root*2 >= 8){
System.out.println(tree[root]);
return;
}
System.out.println(tree[root]);
dfs(root*2); // 左子树
dfs(root*2+1); // 右子树
}
}
四、代码实现
package com.daxiong.day6;
/**
* 8 皇后问题
* */
public class EightQueen {
// 8 个皇后
private static int SIZE = 8;
// 存放规则:索引(0-7)表示行，索引对应的值(0-8)表示该行可以存放皇后的列值,以此构建一个类似二位数组
private static int[] queen = new int[SIZE];
// 方案数
private static int step = 0;
public static void main(String[] args) {
dfs(0);
}
/**
* @fun 判断当前行可以存放皇后的列
* @param key : 当前行(可以看作坐标中的 X1)
* @param value : 当前行对应的列值(可以看作坐标中X1对应的值Y1)
* @return : 当前行对应的列是否可以存放皇后
*/
public static boolean isOk(int key, int value) {
for (int i = 0; i < key; i++) {
if (i == key || queen[i] == value || (i - key == queen[i] - value) || (key - i == queen[i] - value)) {
return false;
}
}
return true;
}
/**
* @fun dfs,深度遍历递归函数
* @param row : 行扫描,问题规模
*/
public static void dfs(int row) {
if (row == SIZE) {
step++;
print(step);
return;
}
for (int i = 0; i < SIZE; i++) {
if (isOk(row, i)) {
queen[row] = i;
dfs(row + 1);
}
}
}
/**
* @fun 打印 8 皇后可行方案
* @param step : 第几个方案
*/
public static void print(int step) {
System.out.println("方案(" + step + "):");
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
if (queen[i] == j) { // 皇后位置
System.out.print(" @ ");
} else { // 非皇后
System.out.print(" * ");
}
}
System.out.println();
}
}
}
五、答案
共有 92 中方案：
方案(1):
@ * * * * * * *
* * * * @ * * *
* * * * * * * @
* * * * * @ * *
* * @ * * * * *
* * * * * * @ *
* @ * * * * * *
* * * @ * * * *
方案(2):
@ * * * * * * *
* * * * * @ * *
* * * * * * * @
* * @ * * * * *
* * * * * * @ *
* * * @ * * * *
* @ * * * * * *
* * * * @ * * *
方案(3):
@ * * * * * * *
* * * * * * @ *
* * * @ * * * *
* * * * * @ * *
* * * * * * * @
* @ * * * * * *
* * * * @ * * *
* * @ * * * * *
方案(4):
@ * * * * * * *
* * * * * * @ *
* * * * @ * * *
* * * * * * * @
* @ * * * * * *
* * * @ * * * *
* * * * * @ * *
* * @ * * * * *
方案(5):
* @ * * * * * *
* * * @ * * * *
* * * * * @ * *
* * * * * * * @
* * @ * * * * *
@ * * * * * * *
* * * * * * @ *
* * * * @ * * *
方案(6):
* @ * * * * * *
* * * * @ * * *
* * * * * * @ *
@ * * * * * * *
* * @ * * * * *
* * * * * * * @
* * * * * @ * *
* * * @ * * * *
方案(7):
* @ * * * * * *
* * * * @ * * *
* * * * * * @ *
* * * @ * * * *
@ * * * * * * *
* * * * * * * @
* * * * * @ * *
* * @ * * * * *
方案(8):
* @ * * * * * *
* * * * * @ * *
@ * * * * * * *
* * * * * * @ *
* * * @ * * * *
* * * * * * * @
* * @ * * * * *
* * * * @ * * *
方案(9):
* @ * * * * * *
* * * * * @ * *
* * * * * * * @
* * @ * * * * *
@ * * * * * * *
* * * @ * * * *
* * * * * * @ *
* * * * @ * * *
方案(10):
* @ * * * * * *
* * * * * * @ *
* * @ * * * * *
* * * * * @ * *
* * * * * * * @
* * * * @ * * *
@ * * * * * * *
* * * @ * * * *
方案(11):
* @ * * * * * *
* * * * * * @ *
* * * * @ * * *
* * * * * * * @
@ * * * * * * *
* * * @ * * * *
* * * * * @ * *
* * @ * * * * *
方案(12):
* @ * * * * * *
* * * * * * * @
* * * * * @ * *
@ * * * * * * *
* * @ * * * * *
* * * * @ * * *
* * * * * * @ *
* * * @ * * * *
方案(13):
* * @ * * * * *
@ * * * * * * *
* * * * * * @ *
* * * * @ * * *
* * * * * * * @
* @ * * * * * *
* * * @ * * * *
* * * * * @ * *
方案(14):
* * @ * * * * *
* * * * @ * * *
* @ * * * * * *
* * * * * * * @
@ * * * * * * *
* * * * * * @ *
* * * @ * * * *
* * * * * @ * *
方案(15):
* * @ * * * * *
* * * * @ * * *
* @ * * * * * *
* * * * * * * @
* * * * * @ * *
* * * @ * * * *
* * * * * * @ *
@ * * * * * * *
方案(16):
* * @ * * * * *
* * * * @ * * *
* * * * * * @ *
@ * * * * * * *
* * * @ * * * *
* @ * * * * * *
* * * * * * * @
* * * * * @ * *
方案(17):
* * @ * * * * *
* * * * @ * * *
* * * * * * * @
* * * @ * * * *
@ * * * * * * *
* * * * * * @ *
* @ * * * * * *
* * * * * @ * *
方案(18):
* * @ * * * * *
* * * * * @ * *
* @ * * * * * *
* * * * @ * * *
* * * * * * * @
@ * * * * * * *
* * * * * * @ *
* * * @ * * * *
方案(19):
* * @ * * * * *
* * * * * @ * *
* @ * * * * * *
* * * * * * @ *
@ * * * * * * *
* * * @ * * * *
* * * * * * * @
* * * * @ * * *
方案(20):
* * @ * * * * *
* * * * * @ * *
* @ * * * * * *
* * * * * * @ *
* * * * @ * * *
@ * * * * * * *
* * * * * * * @
* * * @ * * * *
方案(21):
* * @ * * * * *
* * * * * @ * *
* * * @ * * * *
@ * * * * * * *
* * * * * * * @
* * * * @ * * *
* * * * * * @ *
* @ * * * * * *
方案(22):
* * @ * * * * *
* * * * * @ * *
* * * @ * * * *
* @ * * * * * *
* * * * * * * @
* * * * @ * * *
* * * * * * @ *
@ * * * * * * *
方案(23):
* * @ * * * * *
* *
