1
2
3
4
5
6
7
8
9
10
11
12
  // 準備棋盤
  private char[][] board;
  // 4乘4大小的棋盤
  private int N = 4;
  public Queen() {
    // 建立棋盤
    board = new char[N][N];
    // 預設字元陣列都是點.
    for (int i = 0; i < board.length; i++) {
      Arrays.fill(board[i],'.');
    }
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  // 參數 列row與欄column，檢查是否能放皇后
  public boolean isValidate(int row, int col) {
    // 檢查每一列row，在同一欄是否有皇后
    for (int i = 0; i <= row; i++) {
      if (board[i][col] == 'Q') {
        return false;
      }
    }
    // i與j的初始值是(row - 1, col - 1)，假設(row=3,col=3)
    // 就會變成(2,2)，也就是上面左斜，持續減1
    // (3,3) -> (2,2) -> (1,1) -> (0,0)
    // 由於遞迴只會造成上面的列數要檢查，所以不考慮下面的列
    // 不能減到超出棋盤邊界，不能為-1
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] == 'Q') {
        return false;
      }
    }

    // i與j的初始值是(row - 1, col + 1)，假設(row=3,col=0)
    // 就會變成(2,1)，也就是上面右斜，持續往上右斜檢查
    // (3,0) -> (2,1) -> (1,2)
    // 由於遞迴只會造成上面的列數要檢查，所以不考慮下面的列
    // 不能減到超出棋盤邊界，不能為-1，也不能col + 1，加到超出board.length
    for (int i = row - 1, j = col + 1; i >=0 && j < board.length; i--, j++) {
      if (board[i][j] == 'Q') {
        return false;
      }
    }
    return true;
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  // 參數 i為列row，針對每一列row，放皇后
  public void dfs(int i, List<List<String>> result) {
  	// 如果 i == 4，代表上一次遞迴是dfs(3)
  	// dfs(3) row=3 i=3，代表第3列的皇后成功放置了，才會呼叫dfs(4)
  	// 注意！不是i == board.length - 1，沒有減1
  	// 把第0-3列的所有皇后放法存在List中，並離開遞迴，返回dfs(3)
    if (i == board.length) {
      List<String> list = new ArrayList<String>();
      for (char[] row: board) {
      	// 把字串陣列轉成String存到List中
        list.add(new String(row)) ;
      }
      result.add(list);
      return;  // 返回dfs(3)
    }
    // j代表column，對每一欄嘗試放置皇后
    for (int j = 0; j < board[0].length; j++) {
      // 檢查欄 左斜 右斜 是否有放其它皇后
      if (isValidate(i, j)) {
      	// 放皇后
        board[i][j] = 'Q';
        // dfs(下一列row) 下一列放皇后
        dfs(i + 1, result);
        // 找到皇后放置的方法，dfs(4)會回到此處dfs(3)，清空皇后
        // 一路返回dfs(2) -> 清空皇后 -> dfs(1) -> 清空皇后 -> dfs(0) -> 清空皇后
        // 清空皇后後，再尋找新的放置皇后的路徑。
        // 撤銷皇后也會回到此處
        board[i][j] = '.';
      }
    }
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Queen {
  // 準備棋盤
  private char[][] board;
  // 4乘4大小的棋盤
  private int N = 4;
  public Queen() {
    // 建立棋盤
    board = new char[N][N];
    // 預設字元陣列都是點.
    for (int i = 0; i < board.length; i++) {
      Arrays.fill(board[i],'.');
    }
  }

  // 參數 i為列row，針對每一列row，放皇后
  public void dfs(int i, List<List<String>> result) {
  	// 如果 i == 4，代表上一次遞迴是dfs(3)
  	// dfs(3) row=3 i=3，代表第3列的皇后成功放置了，才會呼叫dfs(4)
  	// 注意！不是i == board.length - 1，沒有減1
  	// 把第0-3列的所有皇后放法存在List中，並離開遞迴，返回dfs(3)
    if (i == board.length) {
      List<String> list = new ArrayList<String>();
      for (char[] row: board) {
      	// 把字串陣列轉成String存到List中
        list.add(new String(row)) ;
      }
      result.add(list);
      return;  // 返回dfs(3)
    }
    // j代表column，對每一欄嘗試放置皇后
    for (int j = 0; j < board[0].length; j++) {
      // 檢查欄 左斜 右斜 是否有放其它皇后
      if (isValidate(i, j)) {
      	// 放皇后
        board[i][j] = 'Q';
        // dfs(下一列row) 下一列放皇后
        dfs(i + 1, result);
        // 找到皇后放置的方法，會回到此處dfs(3)，清空皇后
        // 一路返回dfs(2) -> 清空皇后 -> dfs(1) -> 清空皇后 -> dfs(0) -> 清空皇后
        // 清空皇后後，再尋找新的放置皇后的路徑。
        // 撤銷皇后也會回到此處
        board[i][j] = '.';
      }
    }
  }

  // 參數 列row與欄column，檢查是否能放皇后
  public boolean isValidate(int row, int col) {
    // 檢查每一列row，在同一欄是否有皇后
    for (int i = 0; i <= row; i++) {
      if (board[i][col] == 'Q') {
        return false;
      }
    }
    // i與j的初始值是(row - 1, col - 1)，假設(row=3,col=3)
    // 就會變成(2,2)，也就是上面左斜，持續減1
    // (3,3) -> (2,2) -> (1,1) -> (0,0)
    // 由於遞迴只會造成上面的列數要檢查，所以不考慮下面的列
    // 不能減到超出棋盤邊界，不能為-1
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] == 'Q') {
        return false;
      }
    }

    // i與j的初始值是(row - 1, col + 1)，假設(row=3,col=0)
    // 就會變成(2,1)，也就是上面右斜，持續往上右斜檢查
    // (3,0) -> (2,1) -> (1,2)
    // 由於遞迴只會造成上面的列數要檢查，所以不考慮下面的列
    // 不能減到超出棋盤邊界，不能為-1，也不能col + 1，加到超出board.length
    for (int i = row - 1, j = col + 1; i >=0 && j < board.length; i--, j++) {
      if (board[i][j] == 'Q') {
        return false;
      }
    }
    return true;
  }

  public static void main(String[] args) {
    Queen queen = new Queen();
    List<List<String>> result = new ArrayList<>();
    // 從第0列 row = 0 放置皇后
    queen.dfs(0, result);
    System.out.println(result);
  }
}