N皇后II

难度：困难

题目描述

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

示例1

::: left :::

输入：n = 4 输出：2

示例2

输入：n = 1 输出：1

题解

使用回溯法，定义列表元素 $ilist$ ，用 $ilist.Count$ 来接受最终结果

步骤如下：

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

想法代码

public class Solution
{
    IList<IList<string>> ilist = new List<IList<string>>();

    public static void Main(string[] args)
    {
        int n = 4;
        Solution solution = new Solution();
        int res = solution.TotalNQueens(n);
        Console.WriteLine(res);
    }
    public int TotalNQueens(int n)
    {
        char[][] board = new char[n][];
        for (int i = 0; i < n; i++)
            board[i] = new char[n];

        foreach (var ch in board)
            Array.Fill(ch, '.');

        BackTrack(n, 0, board);
        return ilist.Count;
    }

    public void BackTrack(int n, int row, char[][] board)
    {
        if (row == n)
        {
            ilist.Add(ToIList(board));
            return;
        }

        for (int col = 0; col < n; col++)
        {
            if (isValid(row, col, n, board))
            {
                board[row][col] = 'Q';
                BackTrack(n, row + 1, board);
                board[row][col] = '.';
            }
        }
    }

    public List<string> ToIList(char[][] board)
    {
        List<string> list = new List<string>();
        System.Text.StringBuilder sb = new System.Text.StringBuilder();
        foreach (var chess in board)
        {
            foreach (var ch in chess)
                sb.Append(ch);
            list.Add(sb.ToString());
            sb.Clear();
        }
        return list;
    }

    public bool isValid(int row, int col, int n, char[][] board)
    {
        for (int i = 0; i < n; i++)
        {
            if (board[i][col] == 'Q')
                return false;
        }

        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
        {
            if (board[i][j] == 'Q')
                return false;
        }

        for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++)
        {
            if (board[i][j] == 'Q')
                return false;
        }
        return true;
    }
}