0051. N-Queens (H)

佚名 4年前 (2020-07-02) 算法 671人围观抢沙发百度已收录

N-Queens (H)

题目

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Example:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

题意

在 n * n 的棋盘上放置n个皇后，使得每一行、每一列、每一条对角线有且只有一个皇后。记录每一种放置方法。

思路

问题实质上可以抽象为对 1 ~ n 这n个自然数进行全排列，排列中数字i所处的位置下标代表行号，i代表列号，那么得到的排列组合必定满足每行每列不重复，只要再对对角线位置进行判断即可。使用回溯法。

代码实现

Java

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        generate(new int[n], new boolean[n], 0, ans);
        return ans;
    }

    // queen记录已经放置的皇后的行列坐标，occupied记录指定列是否已经放置皇后
    private void generate(int[] queen, boolean[] occupied, int row, List<List<String>> ans) {
        // 所有行放置完毕，保存当前放置方法
        if (row == queen.length) {
            List<String> list = new ArrayList<>();
            for (int i = 0; i < queen.length; i++) {
                StringBuilder line = new StringBuilder();
                for (int j = 0; j < queen.length; j++) {
                    line.append(j == queen[i] ? 'Q' : '.');
                }
                list.add(line.toString());
            }
            ans.add(list);
            return;
        }

        // 遍历当前行的所有列，寻找可放置的位置
        for (int col = 0; col < queen.length; col++) {
            // 当前列还未放置皇后
            if (!occupied[col]) {
                // 判断位置(row, col)在对角线方向上是否已放置皇后
                boolean isValid = true;
                for (int preRow = 0; preRow < row; preRow++) {
                    if (Math.abs(preRow - row) == Math.abs(queen[preRow] - col)) {
                        isValid = false;
                        break;
                    }
                }
				
                // 位置有效，则向下一行递归
                if (isValid) {
                    occupied[col] = true;
                    queen[row] = col;
                    generate(queen, occupied, row + 1, ans);
                    occupied[col] = false;
                }
            }
        }
    }
}

JavaScript

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
  let board = new Array(n).fill(0).map((value, index) => index)
  let solutions = []
  dfs(board, 0, solutions)
  return solutions
}

let dfs = function (board, index, solutions) {
  if (index === board.length) {
    solutions.push(board.map(v => build(v, board.length)))
    return
  }

  for (let i = index; i < board.length; i++) {
    let isValid = true
    for (let j = 0; j < index; j++) {
      if (index - j === Math.abs(board[j] - board[i])) {
        isValid = false;
        break;
      }
    }
    if (isValid) {
      [board[index], board[i]] = [board[i], board[index]]
      dfs(board, index + 1, solutions);
      [board[index], board[i]] = [board[i], board[index]]
    }
  }
}

let build = function (index, len) {
  let arr = new Array(len).fill('.')
  arr[index] = 'Q'
  return arr.join('')
}