☆打卡算法☆LeetCode 51、N皇后 算法解析

示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：
输入： n = 1
输出： [["Q"]]

public class Solution {
    List<IList<string>> res;
    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 &amp;&amp; j < rows; i--, j++){
            if (board[i][j] == 'Q') return false;
        }
        for (int i = row - 1, j = col - 1; i >= 0 &amp;&amp; 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;
    }
}