javascript 解法, 执行用时: 84 ms, 内存消耗: 46 MB, 提交时间: 2023-03-21 10:16:03

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
    //存放列，对角线是否已经放置皇后的数组；
    let cols=[],diag1=[],diag2=[];
    //棋盘数组；
    let mat=new Array(n).fill("").map(()=>new Array(n).fill("."));
    //结果数组，可能有多种方案；
    let res=[];
    //回溯函数，如果方案可行，会运行到最后一行（row==n）;
    let back_tracking=function(row=0){
        if(row==n){
            //如果结果可行，复制一份；
            let ans=mat.slice();
            ans=ans.map(it=>it.join(""));
            res.push(ans);
            return;
        }
        for(let col=0;col<n;col++){
            //判断当前位置是否可以放置皇后；
            if(cols.includes(col)||diag1.includes(row-col)||diag2.includes(row+col)) continue;
            mat[row][col]="Q";
            cols.push(col);
            diag1.push(row-col);
            diag2.push(row+col);
            //执行回溯；
            back_tracking(row+1);
            //执行回溯后恢复现场；
            mat[row][col]=".";
            cols.pop();
            diag1.pop();
            diag2.pop();
        }
    }
    back_tracking();
    return res;
};

golang 解法, 执行用时: 8 ms, 内存消耗: 3.2 MB, 提交时间: 2023-03-21 10:15:42

func solveNQueens(n int) [][]string {
    cols:=map[int]bool{}
    l2r:=map[int]bool{}
    r2l:=map[int]bool{}
    ans:=[][]string{}
    matrix:=[][]byte{}
    for i:=0;i<n;i++{
        tmp:=make([]byte,n)
        for j:=0;j<n;j++{
            tmp[j]='.'
        }
        matrix=append(matrix,tmp)
    }
    var back_tracking func(int)
    back_tracking=func(i int){
        if i==n{
            tmp:=[]string{}
            for _,row:=range matrix{
                tmp=append(tmp,string(row))
            }
            ans=append(ans,tmp)
            return
        }
        for j:=0;j<n;j++{
            if _,ok:=cols[j];ok{
                continue
            }
            if _,ok:=l2r[i-j];ok{
                continue
            }
            if _,ok:=r2l[i+j];ok{
                continue
            }
            matrix[i][j]='Q'
            cols[j]=true
            l2r[i-j]=true
            r2l[i+j]=true
            back_tracking(i+1)
            matrix[i][j]='.'
            delete(cols,j)
            delete(l2r,i-j)
            delete(r2l,i+j)
        }
    }
    back_tracking(0)
    return ans
}

python3 解法, 执行用时: 80 ms, 内存消耗: 15.2 MB, 提交时间: 2023-03-21 10:14:22

class Solution(object):
    def solveNQueens(self, n):
        # 生成N*N的棋盘，填充棋盘，每个格子默认是“。”表示没有放置皇后
        arr = [["." for _ in range(n)] for _ in range(n)]
        res = []
        # 检查当前的行和列是否可以放置皇后
        def check(x,y):
            # 检查竖着的一列是否有皇后
            for i in range(x):
                if arr[i][y]=="Q":
                    return False
            # 检查左上到右下的斜边是否有皇后        
            i,j = x-1,y-1
            while i>=0 and j>=0:
                if arr[i][j]=="Q":
                    return False
                i,j = i-1,j-1
            # 检查左下到右上的斜边是否有皇后    
            i,j = x-1,y+1
            while i>=0 and j<n:
                if arr[i][j]=="Q":
                    return False
                i,j = i-1,j+1
            return True
        def dfs(x):
            # x是从0开始计算的
            # 当x==n时所有行的皇后都放置完毕，此时记录结果
            if x==n:
                res.append( ["".join(arr[i]) for i in range(n)] )
                return 
            # 遍历每一列    
            for y in range(n):
                # 检查[x,y]这一坐标是否可以放置皇后
                # 如果满足条件，就放置皇后，并继续检查下一行
                if check(x,y):
                    arr[x][y] = "Q"
                    dfs(x+1)
                    arr[x][y] = "."
        dfs(0)
        return res

java 解法, 执行用时: 2 ms, 内存消耗: 41.8 MB, 提交时间: 2023-03-21 10:12:40

class Solution {
    private char[][] array; // 棋盘，放置所有皇后
    private int[] rowIndex; // 每个皇后的列坐标，主要用于位置校验。

    private List<List<String>> res = new ArrayList<>();


    public List<List<String>> solveNQueens(int n) {
        array = new char[n][n];
        rowIndex = new int[n];
        check(n, 0);
        return res;
    }

    // 摆放
    // n：皇后位数
    // index：当前皇后
    private void check(int n, int index) {
        if (index == n) {
            List<String> list = new ArrayList<>();
            for (char[] c : array) {
                list.add(new String(c));
            }
            res.add(list);
            return;
        }
        Arrays.fill(array[index], '.');
        for (int i = 0; i < n; i++) {
            rowIndex[index] = i; // 当前皇后所在棋盘中的列坐标
            array[index][i] = 'Q'; // 放置当前皇后在index行，i列
            if (!judge(index)) {
                array[index][i] = '.'; // 校验不通过
                continue;
            }
            check(n, index + 1); // 递归进行下一位皇后的放置
            array[index][i] = '.';
        }
    }

    // 校验皇后们的位置是否合法：
    // 每个新来的皇后都与之前的皇后进行校验
    // index：1，代表第二个皇后， 她将与（第一个）皇后进行位置校验，检验通过说明当前皇后们摆放是合法的。
    // index：2，代表第三个皇后，此时前两位皇后的位置已经校验完成，她将与前面（第一个、第二个）皇后进行位置校验。
    private boolean judge(int index) {
        int n = array.length;
        for (int i = 0; i < index; i++) {
            if (rowIndex[i] == rowIndex[index] 
                    || Math.abs(rowIndex[index] - rowIndex[i]) == Math.abs(index - i)) {
                return false;
            }
        }
        return true;
    }
}

python3 解法, 执行用时: 36 ms, 内存消耗: 15.4 MB, 提交时间: 2023-03-21 10:12:27

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def generateBoard():
            board = list()
            for i in range(n):
                row[queens[i]] = "Q"
                board.append("".join(row))
                row[queens[i]] = "."
            return board

        def solve(row: int, columns: int, diagonals1: int, diagonals2: int):
            if row == n:
                board = generateBoard()
                solutions.append(board)
            else:
                availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2))
                while availablePositions:
                    position = availablePositions & (-availablePositions)
                    availablePositions = availablePositions & (availablePositions - 1)
                    column = bin(position - 1).count("1")
                    queens[row] = column
                    solve(row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1)

        solutions = list()
        queens = [-1] * n
        row = ["."] * n
        solve(0, 0, 0, 0)
        return solutions

python3 解法, 执行用时: 40 ms, 内存消耗: 15.5 MB, 提交时间: 2023-03-21 10:12:03

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def generateBoard():
            board = list()
            for i in range(n):
                row[queens[i]] = "Q"
                board.append("".join(row))
                row[queens[i]] = "."
            return board

        def backtrack(row: int):
            if row == n:
                board = generateBoard()
                solutions.append(board)
            else:
                for i in range(n):
                    if i in columns or row - i in diagonal1 or row + i in diagonal2:
                        continue
                    queens[row] = i
                    columns.add(i)
                    diagonal1.add(row - i)
                    diagonal2.add(row + i)
                    backtrack(row + 1)
                    columns.remove(i)
                    diagonal1.remove(row - i)
                    diagonal2.remove(row + i)
                    
        solutions = list()
        queens = [-1] * n
        columns = set()
        diagonal1 = set()
        diagonal2 = set()
        row = ["."] * n
        backtrack(0)
        return solutions