八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。计算机发明后,有多种计算机语言可以解决此问题。
import java.util.ArrayDeque;
/**
* 任意两个皇后不能在同一行、同一列、同一斜线上
* Created by lenovo on 2018/7/28.
*/
public class Queen {
static int n; // 皇后数量,即棋盘的 长宽
static boolean[] visitedColumn; // visitedColumn[0] = true, 表示第 0 列已被访问过 , 保证各皇后不在同一列
static int[] rowColumn; // rowColumn[i] = j 表示第 i 行的皇后在第 j 列
static int count = 0;
static ArrayDeque<String> stack = new ArrayDeque<>();
static boolean dfs(int x) {
// x 表示 第 x 行
if (x == n) return true;
for (int y = 0; y < n; y++) {
// y 代表 第 y 列,对第 y 列 进行试探
if (visitedColumn[y] == false && isNotDuijiao(x, y)) {
// 未访问过的列 & 列 != 已经放置的皇后的斜线上, 满足条件
visitedColumn[y] = true;
rowColumn[x] = y;
stack.push("(" + x + "," + y + ")");
if (dfs(x + 1)) {
// 递归试探下一行, 如果最终返回 true ,表示得到正确结果,逆向打印栈中路径
printStack();
count++;
}
// 回退
visitedColumn[y] = false;
stack.pop();
}
// 继续试探下一列
}
// 执行到这一步,表示 第 x 行所有的列试探结束,返回false
return false;
}
/**
* 判断试探的坐标 x,y 和 x 行之前排布的皇后是否成对角线
*
* @param x
* @param y
* @return
*/
private static boolean isNotDuijiao(int x, int y) {
int j = 0;
for (int i = 0; i < x; i++) {
j = rowColumn[i];
if (x - i == y - j || (x - i + y - j) == 0) return false; // 是对角线,返回 false
}
return true;
}
// 双栈打印路径
private static void printStack() {
ArrayDeque<String> tempStack = new ArrayDeque<>();
while (!stack.isEmpty()) {
tempStack.push(stack.pop());
}
while (!tempStack.isEmpty()) {
String pop = tempStack.pop();
System.out.print(pop + "——>");
stack.push(pop);
}
System.out.println();
}
public static void main(String[] args) {
n = 8;
visitedColumn = new boolean[n];
rowColumn = new int[n];
for (int i = 0; i < n; i++) {
visitedColumn[i] = false;
}
dfs(0);
System.out.println(count);
}
}
输出
(0,6)——>(1,1)——>(2,5)——>(3,2)——>(4,0)——>(5,3)——>(6,7)——>(7,4)——>
(0,6)——>(1,2)——>(2,0)——>(3,5)——>(4,7)——>(5,4)——>(6,1)——>(7,3)——>
(0,6)——>(1,2)——>(2,7)——>(3,1)——>(4,4)——>(5,0)——>(6,5)——>(7,3)——>
(0,6)——>(1,3)——>(2,1)——>(3,4)——>(4,7)——>(5,0)——>(6,2)——>(7,5)——>
(0,6)——>(1,3)——>(2,1)——>(3,7)——>(4,5)——>(5,0)——>(6,2)——>(7,4)——>
(0,6)——>(1,4)——>(2,2)——>(3,0)——>(4,5)——>(5,7)——>(6,1)——>(7,3)——>
(0,7)——>(1,1)——>(2,3)——>(3,0)——>(4,6)——>(5,4)——>(6,2)——>(7,5)——>
(0,7)——>(1,1)——>(2,4)——>(3,2)——>(4,0)——>(5,6)——>(6,3)——>(7,5)——>
(0,7)——>(1,2)——>(2,0)——>(3,5)——>(4,1)——>(5,4)——>(6,6)——>(7,3)——>
(0,7)——>(1,3)——>(2,0)——>(3,2)——>(4,5)——>(5,1)——>(6,6)——>(7,4)——>
92
网友评论