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());?例子真的很有帮助。

在此先感谢您，并将接受回答/赞成票。

编辑

输入 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());是这里的终止案例。它说:“如果我们已经到达最后一行，这个板现在是一个解决方案；将它添加到结果列表(而不是处理下一行，它甚至不存在)”。

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

编辑:对我来说 id1 的推导和 id2有点直观，所以我不确定我能解释清楚。只需尝试为不同的字段计算它，您就会看到它们如何给出一个来自 1 的数字。至 15板尺寸8 .这是它们的样子(在 JavaScript 中，所以我可以在这里显示它；单击蓝色的“运行代码片段”按钮):

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 .您不需要检查行，因为程序只会将一个皇后放入每一行，然后继续到下一个。