傳送門：51. N皇后巫玻。
n 皇后問(wèn)題研究的是如何將 n 個(gè)皇后放置在 n×n 的棋盤上蔬浙，并且使皇后彼此之間不能相互攻擊岂津。
img上圖為 8 皇后問(wèn)題的一種解法。
給定一個(gè)整數(shù) n芬首，返回所有不同的 n 皇后問(wèn)題的解決方案赴捞。
每一種解法包含一個(gè)明確的 n 皇后問(wèn)題的棋子放置方案，該方案中
'Q'和'.'分別代表了皇后和空位郁稍。示例:
輸入: 4 輸出: [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ] 解釋: 4 皇后問(wèn)題存在兩個(gè)不同的解法螟炫。
分析：對(duì)于某些計(jì)算問(wèn)題而言，回溯法是一種可以找出所有（或一部分）解的一般性算法艺晴，尤其適用于約束滿足問(wèn)題（在解決約束滿足問(wèn)題時(shí)昼钻，我們逐步構(gòu)造更多的候選解，并且在確定某一部分候選解不可能補(bǔ)全成正確解之后放棄繼續(xù)搜索這個(gè)部分候選解本身及其可以拓展出的子候選解封寞，轉(zhuǎn)而測(cè)試其他的部分候選解）然评。
回溯法采用試錯(cuò)的思想，它嘗試分步的去解決一個(gè)問(wèn)題狈究。在分步解決問(wèn)題的過(guò)程中碗淌，當(dāng)它通過(guò)嘗試發(fā)現(xiàn)現(xiàn)有的分步答案不能得到有效的正確的解答的時(shí)候，它將取消上一步甚至是上幾步的計(jì)算抖锥，再通過(guò)其它的可能的分步解答再次嘗試尋找問(wèn)題的答案亿眠。回溯法通常用最簡(jiǎn)單的遞歸方法來(lái)實(shí)現(xiàn)磅废，在反復(fù)重復(fù)上述的步驟后可能出現(xiàn)兩種情況：
- 找到一個(gè)可能存在的正確的答案
- 在嘗試了所有可能的分步方法后宣告該問(wèn)題沒(méi)有答案
在最壞的情況下纳像，回溯法會(huì)導(dǎo)致一次復(fù)雜度為指數(shù)時(shí)間的計(jì)算。
八皇后問(wèn)題是應(yīng)用回溯法求解的典型案例拯勉。
這篇文章給以 LeetCode 第 51 題為背景竟趾，示例了 n 皇后問(wèn)題的求解憔购。
我們介紹 3 種解法，其核心思想是遞歸回溯算法岔帽。這 3 種解法的不同之處玫鸟，就在于判斷皇后棋子是否可以擺放上，其中用到的方法都很基礎(chǔ)犀勒，我個(gè)人認(rèn)為都不難理解屎飘，并且都應(yīng)該掌握。
解法 1 ：在嘗試擺放皇后棋子之前贾费，判斷當(dāng)前考慮的這個(gè)位置是否可以放置皇后棋子钦购。
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 皇后問(wèn)題
public class Solution3 {
private List<List<String>> res;
private boolean[][] solution; // true 就表示當(dāng)前位置放置了皇后，false 就表示沒(méi)有放置皇后
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 處理成為一個(gè)棋盤 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)行考慮肮雨，棋盤要重置
}
// 如果每一列都不能放置遵堵，那么這個(gè)方法就自動(dòng)退出了箱玷，當(dāng)前錯(cuò)誤的棋盤擺放就不會(huì)被保存
}
}
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)前位置是不是危險(xiǎn)的
// 從之前遞歸的寫(xiě)法來(lái)看锡足，一定是處于不同行的，所以要接著判斷壳坪，屬于不同的列舶得，不同的主對(duì)角線和副對(duì)角線
// 判斷在 (2,3) 之前的那些行，在 3 這一列上是否有皇后爽蝴，即 (0,3)沐批、 (1,3)
for (int r = i; r >= 0; r--) {
if (solution[r][j]) {
return false;
}
}
// 判斷在 (2,3) 之前的那些行，在它的主對(duì)角線上是否有皇后（向右上方走）
for (int r = i, c = j; r >= 0 && c < n; r--, c++) {
if (solution[r][c]) {
return false;
}
}
// 判斷在 (2,3) 之前的那些行蝎亚，在它的副對(duì)角線上是否有皇后（向左上方走）
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);
}
}
}
}
- 我個(gè)人覺(jué)得這種解法使用了典型的回溯方法的套路发框。我們看遞歸方法
private void nQueens(int row, int n, boolean[][] solution)：
我們觀察這個(gè)方法是如何調(diào)用自己的：在一個(gè)循環(huán)中遞歸調(diào)用自己躺彬，而僅僅只是參數(shù)不同刨沦，在調(diào)用自己前設(shè)置狀態(tài)堕扶，在調(diào)用自己后取消狀態(tài)。是不是非常像回溯法解決排列問(wèn)題窃蹋。
解法 2：使用三個(gè)一維數(shù)組記錄了是否可以擺放皇后棋子铣减。
下面這種解法她君，在主對(duì)角線和副對(duì)角線上是否可以擺放元素使用了并不太難的技巧，使得求解更加簡(jiǎn)潔葫哗。
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 皇后問(wè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ì)算出對(duì)角線數(shù)組元素的個(gè)數(shù)為 2*n-1
// 這里要?jiǎng)邮钟眉埞P計(jì)算一下犁河，并不難
dia1 = new boolean[2 * n - 1];
dia2 = new boolean[2 * n - 1];
// 表示一行數(shù)據(jù)鳖枕，第 0 個(gè)數(shù)字表示"第 0 行的皇后應(yīng)該擺放在哪個(gè)索引位置"
LinkedList<Integer> row = new LinkedList<>();
putQueen(n, 0, row);
return res;
}
// 在一個(gè) n 皇后問(wèn)題中，嘗試在第 index 行如何擺放一個(gè)皇后
// 我們將它設(shè)計(jì)成一個(gè)遞歸調(diào)用的函數(shù)桨螺，所以要想清楚兩個(gè)步驟
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)的步驟是一一對(duì)應(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 ：使用一個(gè)二維數(shù)組記錄了每添加一個(gè)皇后灭翔，棋盤中被已經(jīng)存在的皇后可以攻擊到的范圍魏烫。
下面的這種寫(xiě)法可能看起來(lái)篇幅比較長(zhǎng)，但是其中用到的使用方向數(shù)組進(jìn)行狀態(tài)設(shè)置的技巧還是可以參考的肝箱。
另外哄褒，還要注意，下面的這個(gè)方法涉及到二維數(shù)組的復(fù)制煌张，Java 中并不支持直接對(duì)二維數(shù)組進(jìn)行深復(fù)制呐赡，因此最簡(jiǎn)單的做法，就是將二維數(shù)組中的元素一個(gè)一個(gè)進(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 個(gè)方向都應(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 開(kāi)始档玻， 從 0 開(kāi)始也可以怀泊，只不過(guò)重復(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)前沒(méi)有放置皇后
boolean[][] marked = new boolean[n][n];
// n 皇后問(wèn)題的一個(gè)解
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 開(kāi)始計(jì)算）考慮误趴，這一行的 n 個(gè)元素霹琼，搜索皇后應(yīng)該擺放在哪里
// 皇后擺放的位置應(yīng)該在 marked 數(shù)組中標(biāo)記為 false 的地方，此時(shí)已經(jīng)擺放皇后的情況位于 solution 數(shù)組中
// 所有已經(jīng)得到的 n 皇后問(wè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]) { // 如果沒(méi)有標(biāo)記過(guò)凉当，表示當(dāng)前位置是安全的枣申，可以放置皇后
// 注意：對(duì)于二維數(shù)組的復(fù)制，不能簡(jiǎn)單實(shí)用 clone() 或者 System.arraycopy() 或者 Arrays.copyOf() 方法
// 應(yīng)該對(duì)它們?cè)谝痪S數(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ù)制一個(gè) 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é)完）
