LeetCode 面试题 08.12. 八皇后

一、题目

  设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。

  注意：本题相对原题做了扩展

示例:

输入： 4
输出： [[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释: 4 皇后问题存在如下两个不同的解法。
[
[“.Q…”, // 解法 1
“…Q”,
“Q…”,
“…Q.”],
[“…Q.”, // 解法 2
“Q…”,
“…Q”,
“.Q…”]
]

  点击此处跳转题目。

二、C# 题解

  经典的 n 皇后题目，使用递归求解如下：

public class Solution {
    public IList<IList<string>> SolveNQueens(int n) {
        IList<IList<string>> ans = new List<IList<string>>();
        Partition(ans, new int[n], 0, 0, n);
        return ans;
    }

    // 递归方法，pos[i] 记录第 i 行皇后的位置
    public void Partition(IList<IList<string>> ans, int[] pos, int i, int j, int n) {
        if (i == n) {
            // 递归出口
            ans.Add(Generate(pos));
            return;
        }
        if (j == n) return;
        if (Check(pos, i, j, n)) {
            // 如果可以放下皇后
            pos[i] = j;                       // 放皇后
            Partition(ans, pos, i + 1, 0, n); // 继续下一行
        }
        Partition(ans, pos, i, j + 1, n); // 继续该行下一个进行判断
    }

    // 检查当前位置 i,j 是否能放皇后
    public bool Check(int[] pos, int i, int j, int n) {
        for (int k = 0; k < i; k++) {
            int difX = j - pos[k], difY = i - k;             // x 差值和 y 差值
            if (difX == 0) return false;                     // 竖向判断
            if (difX == difY || difX == -difY) return false; // 横向判断
        }
        return true;
    }

    // 依据下标位置生成字符串结果
    public IList<string> Generate(int[] pos) {
        IList<string> ans = new List<string>();
        StringBuilder sb  = new StringBuilder(new string('.', pos.Length));
        for (int i = 0; i < pos.Length; i++) {
            sb[pos[i]] = 'Q';
            ans.Add(sb.ToString());
            sb[pos[i]] = '.';
        }
        return ans;
    }
}
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

• 时间：116 ms，击败 100.00% 使用 C# 的用户
• 内存：46.79 MB，击败 95.65% 使用 C# 的用户