N-Queen

发表于   |  

#51 N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
   "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
   "Q...",
  "...Q",
  ".Q.."]
]

感觉题目说的不清不楚的，至少我看完上面的题目描述，我不知道我应该做什么。
将n个皇后棋子布置在一个n*n的棋盘上，使两个皇后之间无法互相攻击，及每一行，每一列，每一斜线上都只有唯一一个棋子存在(注意有两条斜线)。
以行作为回溯单位

//to do

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
public List<List<String>> solveNQueens(int n) {
       boolean[][] board = new boolean[n][n];
       List<List<String>> list = new ArrayList<List<String>>();
       if (n == 2 || n == 3)
           return list;
       setQueen(0, 0, board, n, list);
       return list;
   }
   
   public boolean setQueen(int row, int col, boolean[][] board, int n, List<List<String>> list) {
       while (row < n && col < n) {
           if (check(row, col, board, n)) {
               board[row][col] = true;
               //最后一行时，将目前方案放入list
               if (row == n -1) {
                   List<String> oneRes = new ArrayList<String>();
                   for (int i = 0; i < n; i++) {
                       StringBuilder sb = new StringBuilder();
                       for (int j = 0; j < n; j++) {
                           if (board[i][j])
                               sb.append("Q");
                           else
                               sb.append(".");
                       }
                       oneRes.add(sb.toString());
                   }
                   list.add(oneRes);
                   board[row][col] = false;
                   return true;
               }
               setQueen(row+1, 0, board, n, list);
               board[row][col] = false;
               col++;
    
           }
           else {
               if (col < n-1)
                   col++;
               else
                   return false;
           }
       }
       return false;
   }
   
   public boolean check(int row, int col, boolean[][] board, int n) {
       //同列有无皇后
       for (int i = 0; i < row; i++) {
           if (board[i][col] == true)
               return false;
       }
       //同行有无皇后
       for (int i = 0; i < col; i++) {
           if (board[row][i] == true)
               return false;
       }
       //往左上方向
       for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
           if (board[i][j] == true)
               return false;
       }
       //往右上方向
       for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
           if (board[i][j] == true)
               return false;
       }
       return true;
   }