Leetcode(52) N-Queens II

发表于 | 分类于

Description

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

img

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

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

解法

与N皇后问题1基本一样，采用回溯法解题，只是在搜寻到一种情况之后对计数器做自加操作记录解的个数，这里就不重复描述啦。

具体代码如下：

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
class Solution {
    int res;

    public int totalNQueens(int n) {
        res = 0;
        //jpos[i]中存第i行中皇后摆放的纵坐标
        int[] jpos = new int[n];
        searchline(0, n, jpos);
        return res;
    }

    void searchline(int k, int n, int[] jpos) {
        //终止条件
        if (k == n) {
            res++;
            return;
        }
        //依次选择j列的位置进行当前行的摆放
        for (int j = 0; j < n; j++) {
            jpos[k] = j;
            //合法则对下一行进行搜索
            if (canplace(k, jpos)) {
                searchline(k + 1, n, jpos);
            }
            //回溯还原
            jpos[k] = 0;

        }
    }

    //判断第k行的插入是否可行
    Boolean canplace(int k, int[] jpos) {
        for (int i = 0; i < k; i++) {
            if (jpos[i] == jpos[k] || Math.abs(jpos[i] - jpos[k]) == Math.abs(k - i)) {
                return false;
            }
        }
        return true;
    }
}