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;}
}

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