51. N 皇后

原题链接：LeetCode 51. N 皇后

题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n* *皇后问题的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

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

示例 2：

**输入：**n = 1 输出：[["Q"]]

提示：

- `1 <= n <= 9`

难度： Hard

题解代码

javascript

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
    const init = Array(n).fill('.')
    const board = []   
    for (let i = 0; i < n; i++) {
        board.push([...init])
    }
    const ret = []
    backTrack(board, ret, 0)
    return ret
};

function backTrack(board, ret, row) {
    if (row === board.length) {
        return ret.push(board.map(item => {
            return item.join('')
        }))
    }
    const height = board[row].length
    for (let i = 0; i < height; i++) {
        if (!isValid(board, row, i)) continue
        board[row][i] = 'Q'
        backTrack(board, ret, row + 1)
        board[row][i] = '.'
    }
}

function isValid(board, row, col) {
    const width = board[0].length
    const height = board.length
    // 当前列
    for (let i = 0; i < height; i++) {
        if (board[i][col] === 'Q') return false
    }
    // 右上
    for (let i = row - 1, j = col + 1; i >= 0 && j < width; i--, j++) {
        if (board[i][j] === 'Q') return false
    }
    // 左上
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] === 'Q') return false
    }
    return true
}

51. N 皇后 #

题目描述 #

题解代码 #

51. N 皇后

题目描述

题解代码