51. N 皇后

解题思路：

约束条件：不能同行、不能同列、不能同斜线
搜索皇后的位置，可以抽象为一棵树。

const isValid = (row, col, chessboard, n) => {
    // 检查列
    for (let i = 0; i < row; i++) {
        if (chessboard[i][col] === 'Q') {
            return false;
        }
    }
    // 检查上方 45度角是否有皇后
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    // 检查上方 135度角是否有皇后
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}
const transformChessBoard = (chessBoard) => {
    let chessBoardBack = []
    chessBoard.forEach(row => {
        chessBoardBack.push(row.join(""))
    })
    return chessBoardBack
}
var solveNQueens = function (n) {
    const res = [];
    const chessboard = new Array(n).fill(0).map(() => new Array(n).fill("."));
    const backtracking = (n, row, chessboard) => {
        if (row === n) {
            res.push(transformChessBoard(chessboard));
            return;
        }
        for (let col = 0; col < n; col++) {
            if (isValid(row, col, chessboard, n)) {
                chessboard[row][col] = 'Q';
                backtracking(n, row + 1, chessboard);
                chessboard[row][col] = '.';
            }
        }
    }
    backtracking(n, 0, chessboard);
    return res;
};

解题思路：

利用二重回溯来解决

1. 第一次return是因为递归里面收集到了结果，所以返回true。
2. 第二次return是遍历全部情况后，仍然没有一种解，那就返回false。
3. 第三次return是整个数独已经被填满了，才会走到这里，所以返回true。

const isValid = (row, col, val, board) => {
    const len = board.length;
    // 检查行
    for (let i = 0; i < len; i++) {
        if (board[row][i] === val) {
            return false
        }
    }
    // 检查列
    for (let i = 0; i < len; i++) {
        if (board[i][col] === val) {
            return false
        }
    }
    // 检查方框
    let startRow = Math.floor(row / 3) * 3
    let startCol = Math.floor(col / 3) * 3
    for (let i = startRow; i < startRow + 3; i++) {
        for (let j = startCol; j < startCol + 3; j++) {
            if (board[i][j] === val) {
                return false
            }
        }
    }
    return true
}
var solveSudoku = function (board) {
    const backtracking = (board) => {
        for (let i = 0; i < board.length; i++) {
            for (let j = 0; j < board[0].length; j++) {
                if (board[i][j] !== ".") {
                    continue;
                }
                for (let val = 1; val <= 9; val++) {
                    if (isValid(i, j, `${val}`, board)) {
                        board[i][j] = `${val}`;
                        const result = backtracking(board);
                        if (result) {
                            return true;
                        }
                        board[i][j] = ".";
                    }
                }
                return false;
            }
        }
        return true;
    }
    backtracking(board);
    return board;
};