傳送門：51. N皇后氨鹏。
n 皇后問題研究的是如何將 n 個皇后放置在 n×n 的棋盤上蟹漓，并且使皇后彼此之間不能相互攻擊。
img上圖為 8 皇后問題的一種解法胃榕。
給定一個整數(shù) n蕉朵，返回所有不同的 n 皇后問題的解決方案梨州。
每一種解法包含一個明確的 n 皇后問題的棋子放置方案非剃，該方案中
'Q'和'.'分別代表了皇后和空位寥殖。示例:
輸入: 4 輸出: [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ] 解釋: 4 皇后問題存在兩個不同的解法慈参。
分析：對于某些計(jì)算問題而言呛牲，回溯法是一種可以找出所有（或一部分）解的一般性算法，尤其適用于約束滿足問題（在解決約束滿足問題時懂牧，我們逐步構(gòu)造更多的候選解侈净，并且在確定某一部分候選解不可能補(bǔ)全成正確解之后放棄繼續(xù)搜索這個部分候選解本身及其可以拓展出的子候選解，轉(zhuǎn)而測試其他的部分候選解）僧凤。
回溯法采用試錯的思想畜侦，它嘗試分步的去解決一個問題。在分步解決問題的過程中躯保，當(dāng)它通過嘗試發(fā)現(xiàn)現(xiàn)有的分步答案不能得到有效的正確的解答的時候旋膳，它將取消上一步甚至是上幾步的計(jì)算，再通過其它的可能的分步解答再次嘗試尋找問題的答案途事⊙榘茫回溯法通常用最簡單的遞歸方法來實(shí)現(xiàn)，在反復(fù)重復(fù)上述的步驟后可能出現(xiàn)兩種情況：
- 找到一個可能存在的正確的答案
- 在嘗試了所有可能的分步方法后宣告該問題沒有答案
在最壞的情況下尸变，回溯法會導(dǎo)致一次復(fù)雜度為指數(shù)時間的計(jì)算义图。
八皇后問題是應(yīng)用回溯法求解的典型案例。
這篇文章給以 LeetCode 第 51 題為背景召烂，示例了 n 皇后問題的求解碱工。
我們介紹 3 種解法，其核心思想是遞歸回溯算法。這 3 種解法的不同之處怕篷，就在于判斷皇后棋子是否可以擺放上历筝，其中用到的方法都很基礎(chǔ)，我個人認(rèn)為都不難理解廊谓，并且都應(yīng)該掌握梳猪。
解法 1 ：在嘗試擺放皇后棋子之前，判斷當(dāng)前考慮的這個位置是否可以放置皇后棋子蒸痹。
Java 代碼：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
// https://leetcode-cn.com/problems/n-queens/description
// 只用一張棋盤擺放的方法完成了 n 皇后問題
public class Solution3 {
private List<List<String>> res;
private boolean[][] solution; // true 就表示當(dāng)前位置放置了皇后春弥，false 就表示沒有放置皇后
public List<List<String>> solveNQueens(int n) {
res = new ArrayList<>();
solution = new boolean[n][n];
nQueens(0, n, solution);
return res;
}
private void nQueens(int row, int n, boolean[][] solution) {
if (row == n) {
// 將 solution 處理成為一個棋盤 generateChessboard
List<String> board = generateChessboard(solution, n);
res.add(board);
return;
}
// 站在當(dāng)前這一行（索引為 row），去一列一列檢查是否可以放皇后
for (int i = 0; i < n; i++) {
if (notInDanger(row, i, n, solution)) {
solution[row][i] = true;
nQueens(row + 1, n, solution);
solution[row][i] = false;// 因?yàn)橄乱涣械姆胖门c上一列應(yīng)該是在同樣的環(huán)境下進(jìn)行考慮电抚，棋盤要重置
}
// 如果每一列都不能放置惕稻，那么這個方法就自動退出了，當(dāng)前錯誤的棋盤擺放就不會被保存
}
}
private List<String> generateChessboard(boolean[][] solution, int n) {
List<String> res = new ArrayList<>();
StringBuilder stringBuilder;
for (int i = 0; i < n; i++) {
stringBuilder = new StringBuilder();
for (int j = 0; j < n; j++) {
if (solution[i][j]) {
stringBuilder.append("Q");
} else {
stringBuilder.append(".");
}
}
res.add(stringBuilder.toString());
}
return res;
}
// i蝙叛，j 表示當(dāng)前嘗試放置皇后棋子的坐標(biāo)
private boolean notInDanger(int i, int j, int n, boolean[][] solution) {
// 設(shè)置一些標(biāo)志俺祠，看看當(dāng)前位置是不是危險的
// 從之前遞歸的寫法來看，一定是處于不同行的借帘，所以要接著判斷蜘渣，屬于不同的列，不同的主對角線和副對角線
// 判斷在 (2,3) 之前的那些行肺然，在 3 這一列上是否有皇后蔫缸，即 (0,3)、 (1,3)
for (int r = i; r >= 0; r--) {
if (solution[r][j]) {
return false;
}
}
// 判斷在 (2,3) 之前的那些行际起，在它的主對角線上是否有皇后（向右上方走）
for (int r = i, c = j; r >= 0 && c < n; r--, c++) {
if (solution[r][c]) {
return false;
}
}
// 判斷在 (2,3) 之前的那些行拾碌，在它的副對角線上是否有皇后（向左上方走）
for (int r = i, c = j; r >= 0 && c >= 0; r--, c--) {
if (solution[r][c]) {
return false;
}
}
// 全部判斷完以后，才表示安全
return true;
}
public static void main(String[] args) {
Solution3 solution = new Solution3();
List<List<String>> solveNQueens = solution.solveNQueens(8);
int solveSize = solveNQueens.size();
System.out.println("一共有 " + solveSize + " 種解街望。");
for (int i = 0; i < solveNQueens.size(); i++) {
System.out.println("第 " + (i + 1) + " 種解：");
for (String line : solveNQueens.get(i)) {
System.out.println(line);
}
}
}
}
- 我個人覺得這種解法使用了典型的回溯方法的套路校翔。我們看遞歸方法
private void nQueens(int row, int n, boolean[][] solution)：
我們觀察這個方法是如何調(diào)用自己的：在一個循環(huán)中遞歸調(diào)用自己，而僅僅只是參數(shù)不同灾前，在調(diào)用自己前設(shè)置狀態(tài)防症，在調(diào)用自己后取消狀態(tài)。是不是非常像回溯法解決排列問題哎甲。
解法 2：使用三個一維數(shù)組記錄了是否可以擺放皇后棋子蔫敲。
下面這種解法，在主對角線和副對角線上是否可以擺放元素使用了并不太難的技巧炭玫，使得求解更加簡潔奈嘿。
Java 代碼：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
// https://leetcode-cn.com/problems/n-queens/description
// 劉宇波老師介紹的 n 皇后問題的解法
public class Solution2 {
private List<List<String>> res;
private boolean[] col;
private boolean[] dia1;
private boolean[] dia2;
public List<List<String>> solveNQueens(int n) {
res = new ArrayList<>();
col = new boolean[n];
// 可以用歸納法計(jì)算出對角線數(shù)組元素的個數(shù)為 2*n-1
// 這里要動手用紙筆計(jì)算一下，并不難
dia1 = new boolean[2 * n - 1];
dia2 = new boolean[2 * n - 1];
// 表示一行數(shù)據(jù)吞加，第 0 個數(shù)字表示"第 0 行的皇后應(yīng)該擺放在哪個索引位置"
LinkedList<Integer> row = new LinkedList<>();
putQueen(n, 0, row);
return res;
}
// 在一個 n 皇后問題中裙犹，嘗試在第 index 行如何擺放一個皇后
// 我們將它設(shè)計(jì)成一個遞歸調(diào)用的函數(shù)酝惧，所以要想清楚兩個步驟
private void putQueen(int n, int index, LinkedList<Integer> row) {
if (index == n) {
res.add(generateBoard(n, row));
}
for (int i = 0; i < n; i++) { // i 表示列數(shù)，index 表示行數(shù)
if (!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]) {
// 設(shè)置狀態(tài)
row.addLast(i);
col[i] = true;
dia1[index + i] = true;
dia2[index - i + n - 1] = true;
putQueen(n, index + 1, row);
// 重置狀態(tài)（與前面設(shè)置狀態(tài)的步驟是一一對應(yīng)的）
col[i] = false;
dia1[index + i] = false;
dia2[index - i + n - 1] = false;
row.removeLast();
}
}
}
private List<String> generateBoard(int n, LinkedList<Integer> row) {
List<String> board = new ArrayList<>();
for (int i = 0; i < n; i++) {
char[] charArray = new char[n];
Arrays.fill(charArray, '.');
charArray[row.get(i)] = 'Q';
board.add(new String(charArray));
}
return board;
}
public static void main(String[] args) {
Solution2 solution = new Solution2();
List<List<String>> solveNQueens = solution.solveNQueens(8);
int solveSize = solveNQueens.size();
System.out.println("一共有 " + solveSize + " 種解伯诬。");
for (int i = 0; i < solveNQueens.size(); i++) {
System.out.println("第 " + (i + 1) + " 種解：");
for (String line : solveNQueens.get(i)) {
System.out.println(line);
}
}
}
}
解法 3 ：使用一個二維數(shù)組記錄了每添加一個皇后，棋盤中被已經(jīng)存在的皇后可以攻擊到的范圍巫财。
下面的這種寫法可能看起來篇幅比較長盗似，但是其中用到的使用方向數(shù)組進(jìn)行狀態(tài)設(shè)置的技巧還是可以參考的。
另外平项，還要注意赫舒，下面的這個方法涉及到二維數(shù)組的復(fù)制，Java 中并不支持直接對二維數(shù)組進(jìn)行深復(fù)制闽瓢，因此最簡單的做法接癌，就是將二維數(shù)組中的元素一個一個進(jìn)行復(fù)制。
Java 代碼：
import java.util.ArrayList;
import java.util.List;
// https://leetcode-cn.com/problems/n-queens/description/
// 這一版使用了遞歸回溯的思想完成
// 使用 marked 數(shù)組把皇后四面八方的攻擊范圍都給標(biāo)記上了
public class Solution {
// x-1,y-1 x-1,y x-1,y+1
// x,y-1 x,y x,y+1
// x+1,y-1 x+1,y x+1,y+1
private static int[] dx = new int[]{-1, -1, -1, 0, 0, 1, 1, 1};
private static int[] dy = new int[]{-1, 0, 1, -1, 1, -1, 0, 1};
private int n;
// 當(dāng)前坐標(biāo) x,y 放上了皇后以后扣讼，它的 8 個方向都應(yīng)該被標(biāo)記不能放置其它皇后
// 標(biāo)記 marked 數(shù)組缺猛，給皇后的四面八方都標(biāo)記上
private void put_down_the_queen(int x, int y, boolean[][] marked) {
marked[x][y] = true;
// 從 1 開始， 從 0 開始也可以椭符，只不過重復(fù)了 marked[x][y] = true;
for (int i = 1; i < n; i++) {
for (int j = 0; j < 8; j++) {
// 不要忘記乘以 i
int new_x = x + i * dx[j];
int new_y = y + i * dy[j];
// 只要都在棋盤內(nèi)
if (new_x >= 0 && new_x < n && new_y >= 0 && new_y < n) {
marked[new_x][new_y] = true;
}
}
}
}
public List<List<String>> solveNQueens(int n) {
this.n = n;
List<List<String>> res = new ArrayList<>();
// 默認(rèn)值是 false 荔燎，表示當(dāng)前沒有放置皇后
boolean[][] marked = new boolean[n][n];
// n 皇后問題的一個解
char[][] solution = new char[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
solution[i][j] = '.';
}
}
generate(0, n, marked, solution, res);
return res;
}
// 在第 k 行（從 0 開始計(jì)算）考慮，這一行的 n 個元素销钝，搜索皇后應(yīng)該擺放在哪里
// 皇后擺放的位置應(yīng)該在 marked 數(shù)組中標(biāo)記為 false 的地方有咨，此時已經(jīng)擺放皇后的情況位于 solution 數(shù)組中
// 所有已經(jīng)得到的 n 皇后問題的解位于 res 中
private void generate(int k, int n, boolean[][] marked, char[][] solution, List<List<String>> res) {
if (k == n) {
res.add(transform2str(solution));
return;
}
for (int i = 0; i < n; i++) {
if (!marked[k][i]) { // 如果沒有標(biāo)記過，表示當(dāng)前位置是安全的蒸健，可以放置皇后
// 注意：對于二維數(shù)組的復(fù)制座享，不能簡單實(shí)用 clone() 或者 System.arraycopy() 或者 Arrays.copyOf() 方法
// 應(yīng)該對它們在一維數(shù)組上使用
boolean[][] temp_mark = copyNewArr(marked);
solution[k][i] = 'Q';
put_down_the_queen(k, i, marked);
generate(k + 1, n, marked, solution, res);
marked = temp_mark;
solution[k][i] = '.';
}
}
}
// 復(fù)制一個 marked 數(shù)組
private boolean[][] copyNewArr(boolean[][] marked) {
boolean[][] res = new boolean[n][n];
for (int i = 0; i < n; i++) {
System.arraycopy(marked[i],0,res[i],0,n);
}
return res;
}
private List<String> transform2str(char[][] solution) {
List<String> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
res.add(new String(solution[i]));
}
return res;
}
public static void main(String[] args) {
Solution solution = new Solution();
List<List<String>> solveNQueens = solution.solveNQueens(8);
int solveSize = solveNQueens.size();
System.out.println("一共有 " + solveSize + " 種解。");
for (int i = 0; i < solveNQueens.size(); i++) {
System.out.println("第 " + (i + 1) + " 種解：");
for (String line : solveNQueens.get(i)) {
System.out.println(line);
}
}
}
}
（本節(jié)完）
