N皇后

难度：困难

题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例1

::: left :::

输入：n = 4 输出：[[".Q..","…Q","Q…","..Q."],["..Q.","Q…","…Q",".Q.."]]

示例2

输入：n = 1 输出：[["Q"]]

题解

使用回溯法，定义列表元素 $res$ 来接受最后的结果

步骤如下：

• 定义一个二位数组 $board$ ，大小为 $n$ ，遍历每一个二维数组元素，将所有的元素的初始值都定义为"."，之后进行回溯
  • 如果行 $row$ 的值等于 $board$ 的长度，那么直接将结果添加到 $res$ 中
  • 如果行 $row$ 的值小于 $board$ 的长度，执行如下操作
    • 定义 $n$ 为列数，对行内的每一个元素进行循环，如果当前行有"Q"，那么直接跳出本次循环，如果当前元素的左上或右上有"Q"，那么直接跳出本次循环
    • 对当前元素赋值为"Q"，并继续进行回溯，如果最后的结果无法成立，那么回退此次操作
    • 最后将结果传入到 $res$ 中，即可得到最终结果

想法代码

class Solution
{
    List<IList<string>> res;

    public static void Main(String[] args)
    {
        Solution solution = new Solution();
        int n = 4;
        IList<IList<string>> result = solution.SolveNQueens(n);
        foreach (var a in result)
        {
            foreach (var b in a)
            {
                Console.WriteLine("\"" + b + "\" ");
            }
            Console.WriteLine();
        }
    }

    public IList<IList<string>> SolveNQueens(int n)
    {
        res = new List<IList<string>>();
        char[][] board = new char[n][];
        for (int i = 0; i < n; ++i) board[i] = new char[n];
        foreach (char[] chars in board)
        {
            Array.Fill(chars, '.');
        }
        backTrack(board, 0);
        return res;
    }
    private void backTrack(char[][] board, int row)
    {
        if (row == board.Length)
        {
            res.Add(charToString(board));
            return;
        }
        int n = board[row].Length;
        for (int col = 0; col < n; ++col)
        {
            if (!isValid(board, row, col)) continue;
            board[row][col] = 'Q';
            backTrack(board, row + 1);
            board[row][col] = '.';
        }
    }
    private bool isValid(char[][] board, int row, int col)
    {
        int rows = board.Length;
        foreach (char[] chars in board)
        {
            if (chars[col] == 'Q')
            {
                return false;
            }
        }
        for (int i = row - 1, j = col + 1; i >= 0 && j < rows; i--, j++)
        {
            if (board[i][j] == 'Q') return false;
        }
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
        {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }
    private List<string> charToString(char[][] array)
    {
        List<string> result = new List<string>();
        foreach (char[] chars in array) result.Add(new String(chars));
        return result;
    }
}