N皇后

[louzhedong]

习题

出处：LeetCode 算法第51题

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

上图为 8 皇后问题的一种解法。

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

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

示例:

输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

思路

采用回溯法，遍历所有的可能性，输出结果

解答

/**
 * @param {number} n
 * @return {string[][]}
 */

function isSafe(array, n, x, y) {
  for (var i = 0; i < n; i++) {
    for (var j = 0; j < y; j++) {
      if (array[i][j] == 'Q' && (x + j == y + i || x + y == i + j || x == i)) {
        return false;
      }
    }
  }

  return true;
}

function solve(array, col, result, n) {
  if (col == n) {
    var temp = [];
    for (var i = 0; i < n; i++) {
      temp.push(array[i].join(''));
    }
    result.push(temp);
    return;
  }

  for (var i = 0; i < n; i++) {
    if (isSafe(array, n, i, col)) {
      array[i][col] = 'Q';
      solve(array, col + 1, result, n);
      array[i][col] = '.'
    }
  }
}

var solveNQueens = function (n) {
  var result = [];
  var array = [];
  for (var i = 0; i < n; i++) {
    array[i] = [];
    for (var j = 0; j < n; j++) {
      array[i][j] = '.';
    }
  }
  solve(array, 0, result, n);

  return result;
};

console.log(solveNQueens(4));