Java: 如何实现N-Queens？

Question

我正在研究 N-Queens 以自行实现它，并且遇到了以下规则的实现：

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. 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.

例如， 4 皇后难题存在两种截然不同的解决方案：

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

和实现（思路是记住繁忙的列和对角线并递归尝试将皇后放入下一行）：

public class Solution {

    private void helper(int r, boolean[] cols, boolean[] d1, boolean[] d2, 
                        String[] board, List<String[]> res) {
        if (r == board.length) res.add(board.clone()); //HERE
        else {
            for (int c = 0; c < board.length; c++) {
                int id1 = r - c + board.length, id2 = 2*board.length - r - c - 1;//HERE
                if (!cols[c] && !d1[id1] && !d2[id2]) {
                    char[] row = new char[board.length];
                    Arrays.fill(row, '.'); row[c] = 'Q';
                    board[r] = new String(row);
                    cols[c] = true; d1[id1] = true; d2[id2] = true;
                    helper(r+1, cols, d1, d2, board, res);
                    cols[c] = false; d1[id1] = false; d2[id2] = false;
                }
            }
        }
    }

    public List<String[]> solveNQueens(int n) {
        List<String[]> res = new ArrayList<>();
        helper(0, new boolean[n], new boolean[2*n], new boolean[2*n], 
            new String[n], res);
        return res;
    }
}

我的问题是（位于评论的位置：//HERE），初始化的原因是什么以及以下是如何工作的：id1 = r - c + board.length, id2 = 2*board.length - r - c - 1;（r、id1 和 id2 代表什么？），以下是什么意思：if (r == board.length) res.add(board.clone());？例子真的很有帮助。

在此先感谢您并将接受 answer/up 投票。

编辑

输入 n 为 4，想 System.out.print 形式为 :

的答案

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

我该怎么做？

Answer 1

谨记

the idea is to remember the busy columns and diagonals and recursively try to put the queen into the next row

r 是当前行，从 0 (helper(0, ...)) 开始并在每次递归 (helper(r+1, ...)) 中递增。

id1 和 id2 是标识 \ 和 / 对角线的数字。例如，主 \ 对角线上的字段 0,0-1,1-2,2-...-7,7 都具有相同的 id1 8.

cols、d1 和 d2 正在跟踪到目前为止棋盘上哪些列和对角线受到皇后的威胁。如果您在 0,0 处放置一个皇后，则 cols[0]（第 0 列）、d1[8]（第 8 \ 对角线）和 d2[15]（15-第 / 个对角线）都是 true.

这是一个递归函数（调用自身）。为了使函数既是递归的又不是无用的，它总是需要有两种不同的情况：基本情况（也称为终止情况）和一般情况（也称为递归情况）。第一个告诉你什么时候停止；第二个告诉你如何继续前进。第一个告诉你最简单的情况；第二个告诉你如何把一个复杂的案例分解成一个更简单的案例。

if (r == board.length) res.add(board.clone()); 是这里的终止案例。它说："if we've reached the past the last row, this board as it stands now is a solution; add it to the list of results (instead of processing the next row, which wouldn't even exist)".

clone 用于添加当前板的快照而不是对当前板本身的引用（否则你最终会得到一堆对最后尝试的板的引用）。

编辑：对我来说 id1 和 id2 的推导有点直观，所以我不确定我是否可以解释它。只需尝试为不同的字段计算它，您就会看到它们如何为电路板大小 8 给出从 1 到 15 的数字。这是它们的样子（在 JavaScript 中，所以我可以在这里显示；单击蓝色 "Run code snippet" 按钮）：

function drawTable(id, size, cb) {
  var $table = $('#' + id);
  var $tr = $('<tr>').appendTo($table);
  $('<th>').text(id).appendTo($tr);
  for (var c = 0; c < size; c++) {
    $('<th>').text(c).appendTo($tr);
  }
  for (var r = 0; r < size; r++) {
    var $tr = $('<tr>').appendTo($table);
    $('<th>').text(r).appendTo($tr);
    for (var c = 0; c < size; c++) {
      var n = cb(r, c, size);
      var $td = $('<td>').text(n).attr('data-d', n).appendTo($tr);
    }
  }
}

var size = 8
drawTable('id1', size, function(r, c, size) { return r - c + size; });
drawTable('id2', size, function(r, c, size) { return 2 * size - r - c - 1; });

th, td {
  text-align: center;
  border: 1px solid black;
  width: 2em;
}
table {
  border-collapse: collapse;
}
#id1 td[data-d="8"] {
  background-color: yellow;
}
#id2 td[data-d="15"] {
  background-color: yellow;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<table id="id1"></table>
<br>
<table id="id2"></table>

黄色单元格显示第 8 个 id1 和第 15 个 id2 - 字段 0,0 的对角线。您不需要检查行，因为程序只会将一个皇后放入每一行，然后继续下一个。

Java: 如何实现N-Queens？

Java: How to implement N-Queens?

java

algorithm

n-queens