I'm studying N-Queens to implement it on my own, and came across the following implementation with the rules:
我正在研究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.
n-queens难题是将n个皇后放置在n×n棋盘上的问题,使得没有两个皇后互相攻击。给定整数n,返回n-queens拼图的所有不同解。
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
每个解决方案都包含n-queens位置的独特电路板配置,其中“Q”和“。”两者分别表示女王和空白。
For example, There exist two distinct solutions to the 4-queens puzzle:
例如,4皇后拼图有两种截然不同的解决方案:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
And implementation (the idea is to remember the busy columns and diagonals and recursively try to put the queen into the next row):
和实现(想法是记住繁忙的列和对角线,并递归尝试将女王放入下一行):
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;
}
}
And my question is (located where commented: //HERE), what's the reason for initializing and how are the following working the way they are: id1 = r - c + board.length, id2 = 2*board.length - r - c - 1; (what do r, id1, and id2 represent?), and what's the following meant for: if (r == board.length) res.add(board.clone());? Examples would really help.
我的问题是(位于注释:// HERE),初始化的原因是什么,以及如何按照它们的方式工作:id1 = r - c + board.length,id2 = 2 * board.length - r - c - 1; (r,id1和id2代表什么?),以下是什么意思:if(r == board.length)res.add(board.clone());?例子真的有帮助。
Thank you in advance and will accept answer/up vote.
提前谢谢你,并接受回答/投票。
EDIT
With input n as 4, would like to System.out.print the answer in the form of :
输入n为4时,想以System.out.print的形式给出答案:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
How can I do so?
我怎么能这样做?
1 个解决方案
#1
2
Keeping in mind
牢记
the idea is to remember the busy columns and diagonals and recursively try to put the queen into the next row
我的想法是记住繁忙的列和对角线,然后递归尝试将女王放入下一行
r is the current row, which starts at 0 (helper(0, ...)) and increments in each recursion (helper(r+1, ...)).
r是当前行,从0开始(helper(0,...))并在每次递归中递增(helper(r + 1,...))。
id1 and id2 is a number that identifies \ and / diagonals. For example, the fields on the main \ diagonal 0,0-1,1-2,2-...-7,7 all have the same id1 of 8.
id1和id2是一个标识\和/ diagonals的数字。例如,主\对角线0,0-1,1-2,2 -...- 7,7上的字段都具有相同的id1为8。
cols, d1 and d2 are tracking which columns and diagonals are threatened by the queens so far on the board. If you place a queen at 0,0, then cols[0] (0-th column), d1[8] (8-th \ diagonal) and d2[15] (15-th / diagonal) are all true.
cols,d1和d2正在追踪到目前为止在棋盘上哪些列和对角线受到皇后的威胁。如果你将一个女王放在0,0,那么cols [0](第0列),d1 [8](第8个\对角线)和d2 [15](第15个/对角线)都是真的。
This is a recursive function (calls itself). In order for a function to be both recursive and not useless, it always needs to have two different cases: a base case (also called the terminating case), and a general case (also called the recursive case). The first tells you when to stop; the second tells you how to keep going. The first tells you the simplest case; the second tells you how to break a complex case into a simpler one.
这是一个递归函数(调用自身)。为了使函数既递归又无用,它总是需要有两种不同的情况:基本情况(也称为终止情况)和一般情况(也称为递归情况)。第一个告诉你何时停止;第二个告诉你如何继续前进。第一个告诉你最简单的情况;第二个告诉你如何将复杂的案例分解为更简单的案例。
if (r == board.length) res.add(board.clone()); is the terminating case here. It says: "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)".
if(r == board.length)res.add(board.clone());这是终止案例。它说:“如果我们已经到了最后一行,那么现在这个板子就是一个解决方案;将它添加到结果列表中(而不是处理下一行,甚至不存在)”。
clone is used so that a snapshot of the current board is added instead of the reference to the current board itself (otherwise you'd end up with a bunch of references to the last board attempted).
使用clone,以便添加当前板的快照而不是对当前板本身的引用(否则您最终会得到一堆对最后一块板的引用)。
EDIT: To me the derivation of id1 and id2 is kind of intuitive, so I am not sure I can explain it. Just try to calculate it for different fields, and you'll see how they both give a number from 1 to 15 for board size 8. Here's what they look like (in JavaScript, so I can show it here; click the blue "Run code snippet" button):
编辑:对我来说,id1和id2的推导是直观的,所以我不确定我能解释它。只是尝试为不同的字段计算它,你会看到它们如何给出板大小为8的1到15的数字。这是它们的样子(在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>Yellow cells show you 8th id1 and 15th id2 - the diagonals for the field 0,0. You don't need to check the rows, because the program only ever puts one queen into each row, then goes on to the next one.
黄色单元格显示第8个id1和第15个id2 - 字段0,0的对角线。您不需要检查行,因为程序只会在每行中放入一个后跟,然后转到下一行。
#1
2
Keeping in mind
牢记
the idea is to remember the busy columns and diagonals and recursively try to put the queen into the next row
我的想法是记住繁忙的列和对角线,然后递归尝试将女王放入下一行
r is the current row, which starts at 0 (helper(0, ...)) and increments in each recursion (helper(r+1, ...)).
r是当前行,从0开始(helper(0,...))并在每次递归中递增(helper(r + 1,...))。
id1 and id2 is a number that identifies \ and / diagonals. For example, the fields on the main \ diagonal 0,0-1,1-2,2-...-7,7 all have the same id1 of 8.
id1和id2是一个标识\和/ diagonals的数字。例如,主\对角线0,0-1,1-2,2 -...- 7,7上的字段都具有相同的id1为8。
cols, d1 and d2 are tracking which columns and diagonals are threatened by the queens so far on the board. If you place a queen at 0,0, then cols[0] (0-th column), d1[8] (8-th \ diagonal) and d2[15] (15-th / diagonal) are all true.
cols,d1和d2正在追踪到目前为止在棋盘上哪些列和对角线受到皇后的威胁。如果你将一个女王放在0,0,那么cols [0](第0列),d1 [8](第8个\对角线)和d2 [15](第15个/对角线)都是真的。
This is a recursive function (calls itself). In order for a function to be both recursive and not useless, it always needs to have two different cases: a base case (also called the terminating case), and a general case (also called the recursive case). The first tells you when to stop; the second tells you how to keep going. The first tells you the simplest case; the second tells you how to break a complex case into a simpler one.
这是一个递归函数(调用自身)。为了使函数既递归又无用,它总是需要有两种不同的情况:基本情况(也称为终止情况)和一般情况(也称为递归情况)。第一个告诉你何时停止;第二个告诉你如何继续前进。第一个告诉你最简单的情况;第二个告诉你如何将复杂的案例分解为更简单的案例。
if (r == board.length) res.add(board.clone()); is the terminating case here. It says: "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)".
if(r == board.length)res.add(board.clone());这是终止案例。它说:“如果我们已经到了最后一行,那么现在这个板子就是一个解决方案;将它添加到结果列表中(而不是处理下一行,甚至不存在)”。
clone is used so that a snapshot of the current board is added instead of the reference to the current board itself (otherwise you'd end up with a bunch of references to the last board attempted).
使用clone,以便添加当前板的快照而不是对当前板本身的引用(否则您最终会得到一堆对最后一块板的引用)。
EDIT: To me the derivation of id1 and id2 is kind of intuitive, so I am not sure I can explain it. Just try to calculate it for different fields, and you'll see how they both give a number from 1 to 15 for board size 8. Here's what they look like (in JavaScript, so I can show it here; click the blue "Run code snippet" button):
编辑:对我来说,id1和id2的推导是直观的,所以我不确定我能解释它。只是尝试为不同的字段计算它,你会看到它们如何给出板大小为8的1到15的数字。这是它们的样子(在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>Yellow cells show you 8th id1 and 15th id2 - the diagonals for the field 0,0. You don't need to check the rows, because the program only ever puts one queen into each row, then goes on to the next one.
黄色单元格显示第8个id1和第15个id2 - 字段0,0的对角线。您不需要检查行,因为程序只会在每行中放入一个后跟,然后转到下一行。