八皇后問題，一個古老而著名的問題，是回溯算法的典型案例。該問題由國際西洋棋棋手馬克斯·貝瑟爾於 1848 年提出：在 8×8 格的西洋棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處於同一行、同一列或同一斜線上，問有多少種擺法。高斯認為有 76種方案。1854 年在柏林的象棋雜誌上不同的作者發表了 40 種不同的解，後來有人用圖論的方法解出 92種結果。計算機發明後，有多種計算機語言可以編程解決此問題。
相信大家都玩過 死亡八皇后遊戲，下面是我玩在線遊戲錄的屏。
二、問題分析目的：8×8 格的西洋棋上擺放八個皇后
規則：任意兩個皇后都不能處於同一行、同一列或同一斜線上
由於任意皇后不能同行，因此每一行最多放一個皇后；由於行數等於皇后數，因此每一行至少要一個皇后。
結論：每一行一定是放一個皇后
三、實現邏輯① 首先把第一個皇后放在 8×8 格西洋棋的第1行第1列
② 接下來放第二個皇后，嘗試放在第二行第一列，然後判斷是否滿 足規則，如果不滿足，繼續嘗試放在第二列、第三列...嘗試把所有的列的位置全部放完，找到一個合適的放置位置。
③ 繼續放第三個皇后，放置過程和第②步同理。
. ...
④ 依次類推，放第四個、第五個、第六個、第七個、第八個皇后
⑤ 通過以上過程得到一個正確的擺放方案時：
嘗試把第八個皇后移動擺放位置，看有沒有其它擺放方式；
嘗試把第七個皇后移動擺放位置，看有沒有其它擺放方式；
嘗試把第六個皇后移動擺放位置，看有沒有其它擺放方式；
. ...
依次類推，把第五個、第四個、第三個、第二個皇后移動位置，看有沒有其它擺放方式。
這樣就得到了把第一個皇后放在第一行第一列所有可能性
⑥ 然後回頭將第一個皇后放到第二列，繼續循環執行上面的步驟 ①、②、③ 、④ 、⑤
在此過程中使用到了回溯算法的思想，從一條路往前走，能進則進，不能進則退回來，換一條路再試。八皇后問題就是回溯算法的典型，第一步按照順序放一個皇后，然後第二步符合要求放第2個皇后，如果沒有位置符合要求，那麼就要改變第一個皇后的位置，重新放第2個皇后的位置，直到找到符合條件的位置就可以了。
回溯在 迷宮搜索問題 中使用很常見，就是這條路走不通，然後返回到前一個路口，繼續走下一條路。
四、擺放圖示在這裡只演示把第一個皇后放在第一行第一列的情況：
第一種：
第二種：
第三種：
第四種：
五、代碼實現使用一個一維數組表示皇后的位置，其中數組的下標表示皇后所在的行，也就是第幾個皇后，數組元素的值表示皇后所在的列。
package com.study.algorithm;
public class EightQueens { static final int COUNT = 8;
static int[] array = new int[COUNT]; static int sum = 0;
public static void main(String[] args) { putQueen(0); System.out.println("八皇后總共有" + sum + "種擺放方案"); }
public static void putQueen(int n) { if (n == COUNT) { System.out.print((sum + 1) + "、八皇后的擺放位置是："); for (int i = 0; i < COUNT; i++) { int pos = array[i] + 1; System.out.print(pos + " "); } System.out.println(); System.out.print("擺放位置如下圖所示："); printPlace(); return; } else { for (int i = 0; i < COUNT; i++) { array[n] = i; if (checkPlace(n)) { putQueen(n + 1); } } } }
public static void printPlace() { System.out.println(); sum++; for (int i = 0; i < COUNT; i++) { System.out.print(" "); for (int j = 0; j < COUNT; j++) { System.out.print("---"); } System.out.println(); for (int k = 0; k < COUNT; k++) { if (k == array[i]) { System.out.print("|" + "♛"); } else { System.out.print("| " + " "); } } System.out.println("|"); } System.out.print(" "); for (int i = 0; i < COUNT; i++) { System.out.print("---"); } System.out.println(); }
public static boolean checkPlace(int n) { for (int i = 0; i < n; i++) { if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) { return false; } } return true; }}代碼執行結果：
總共有 92 種擺放方案，由於篇幅有些，在此只截取了兩種方案。
由於水平有限，內容難免有不足，懇請各位大佬不吝賜教！
公眾號： 程序猿編程
長按下圖二維碼關注，獨自前進，走得快；結伴而行，走得遠；在這裡除了肝出來的文章，還有一步一個腳印學習的點點滴滴。
原創不易，順便點個贊、點一下「在看」，和揚帆一起成長吧！搬磚的路上我們一起努力