八皇后問題性锭，是一個古老而著名的問題赠潦，是回溯算法的典型案例。該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8×8格的國際象棋上擺放八個皇后草冈，使其不能互相攻擊祭椰，即任意兩個皇后都不能處于同一行、同一列或同一斜線上疲陕，問有多少種擺法。 高斯認為有76種方案钉赁。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解蹄殃，后來有人用圖論的方法解出92種結果。計算機發(fā)明后你踩，有多種計算機語言可以解決此問題诅岩。
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ù)試探下一列
}
// 執(zhí)行到這一步芭挽，表示 第 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
