程序员面试金典---15

八皇后

直接上代码：

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
    // 创建一个长度为n的一维数组，其元素值为'.'，然后再利用map()方法将其转化成一个n * n的二维数组board。我们可以把它看成 n x n 的棋盘，初始化所有位置都是没有皇后的状态。
    const board = new Array(n).fill('.').map(x =>new Array(n).fill('.'))
    // 创建一个空数组来存放结果，以便在检查完所有可能的组合后将解决方案添加到该数组中。
    const res = [] // 结果数组
	// isValid函数用于检查当前位置(row, col)是否可以放置皇后。通过循环遍历之前的各行、列、对角线上是否已经存在皇后，如果存在则返回false，否则返回true。
    function isValid(row, col){
        for(let i = 0;i < row;i++){
            for(let j = 0;j < n; j++){
                if(board[i][j] == 'Q' && (j == col || i + j === row + col || i - j === row - col)){
                    return false
                }
            }
        }
        return true
    }
	
    function hepler(row){
        // 如果当前row等于n，说明已经找到了一个可行解，将其转换成字符串格式并添加到数组res中保存。递归出口
        if(row == n){
            const stringBoard = board.slice();
            for(let i = 0; i < n;i++){
                stringBoard[i] = stringBoard[i].join('')
            }
            res.push(stringBoard)
            return
        }
        // 如果当前位置(row, col)能够放置皇后，就将该位置设置为'Q'，然后递归地调用helper函数，查找下一行。如果无法放置，则试图在本行的其他位置寻找可行的位置。
        for(let col = 0; col < n; col++){
            if(isValid(row, col)){
                board[row][col] = 'Q'
                hepler(row + 1)
                board[row][col] = '.'
            }
        }
    }
    hepler(0)
    return res
};