使用回溯递归的 8 皇后问题
我一直在研究 8 个皇后问题，但我陷入了困境。我不想要代码。我希望得到指导和指导，以便了解如何使用回溯递归自己解决这个问题。
该程序应该通过以 ASCII 格式绘制皇后位置来枚举 N 皇后问题的所有解决方案，如两个解决方案 此处。
到目前为止，我的伪代码是：
void queen(int n){
for( int i = 0; i < n; i++){
place queen[ i ] on row i;
for(int j = 0 ; j < n ; j++){
if( queen[ i ] is not in the same column as queen[0] through queen[ i - 1 ] &&
queen[ i ] is not on the same major diagonal with queen[0] through queen[ i -1 ] &&
queen[ i ] is not on the same minor diagonal with queen[0] through queen[ i -1 ] ) {
print 'Q ';
}
else{
print '* ';
}
System.out.println();
}
System.out.println();
}
}
我的伪代码中没有任何回溯递归，因为我不知道该怎么做。
非常感谢任何帮助。请不要提供代码。
（针对 Nemo 的更新）：
solver(int n, Board b){
for(int i = 0; i < b.length; i++){
place queen in column i;
for(int j = 0; j < b.length; j++){
change b;
solver(n+1,changed b);
}
}
}
正确吗？
（更新 2）：
solver8(board /* with queens presented in first 7 columns */){
// place a queen in the 8th column;
for(each possible placement of the queen in column 8
or in other words int i = 0; i < board.length; i++ ){
place the queen and print the board
}
}
solver7(board /* with queens presented in first 6 columns */){
// place a queen in the 7th column;
for(each possible placement of the queen in column 7
or in other words int i = 0; i < board.length; i++ ){
solver8(board with queens placed in first 7 columns);
}
}
solver6(board /* with queens presented in first 5 columns */ ){
// place a queen in the 6th column;
for(each possible placement of the queen in column 6
or in other words int i = 0; i < board.length; i++ ){
solver7(board with queens presented in first 6 columns);
}
}
依此类推，直到
solver1(1, empty board){
for(int i = 0; i < board.length; i++){
place queen in row[i] of column 1;
solver2(board with queen in row[i] of column 1);
}
}
更新 3（已编辑）：
private int numberOfQueens = 8;
solver(int n, Board b){
for(int r = 0; r < b.length; r++){
place queen in row[r] of column[n];
if(n == numberOfQueens){
print the board;
return;
}
else{
solver(n+1, board with queen in row[r] of column[n]);
}
}
}
}
I've been working on the 8 queens problem but I got stuck. I don't want code. I would love guidance and directions in order to understand how to solve this problem myself using backtracking recursion.
The program should enumerate all solutions to the N-queens problem by drawing the location of the queens in ASCII like the two solutions here.
My pseudocode so far is:
void queen(int n){
for( int i = 0; i < n; i++){
place queen[ i ] on row i;
for(int j = 0 ; j < n ; j++){
if( queen[ i ] is not in the same column as queen[0] through queen[ i - 1 ] &&
queen[ i ] is not on the same major diagonal with queen[0] through queen[ i -1 ] &&
queen[ i ] is not on the same minor diagonal with queen[0] through queen[ i -1 ] ) {
print 'Q ';
}
else{
print '* ';
}
System.out.println();
}
System.out.println();
}
}
There is no any backtracking recursion in my pseudocode because I don't know how to do it.
Any help is greatly appreciated.No code, please.
(Update in response to Nemo):
solver(int n, Board b){
for(int i = 0; i < b.length; i++){
place queen in column i;
for(int j = 0; j < b.length; j++){
change b;
solver(n+1,changed b);
}
}
}
Is it correct?
(Update 2):
solver8(board /* with queens presented in first 7 columns */){
// place a queen in the 8th column;
for(each possible placement of the queen in column 8
or in other words int i = 0; i < board.length; i++ ){
place the queen and print the board
}
}
solver7(board /* with queens presented in first 6 columns */){
// place a queen in the 7th column;
for(each possible placement of the queen in column 7
or in other words int i = 0; i < board.length; i++ ){
solver8(board with queens placed in first 7 columns);
}
}
solver6(board /* with queens presented in first 5 columns */ ){
// place a queen in the 6th column;
for(each possible placement of the queen in column 6
or in other words int i = 0; i < board.length; i++ ){
solver7(board with queens presented in first 6 columns);
}
}
and so on until
solver1(1, empty board){
for(int i = 0; i < board.length; i++){
place queen in row[i] of column 1;
solver2(board with queen in row[i] of column 1);
}
}
Update 3 (Edited):
private int numberOfQueens = 8;
solver(int n, Board b){
for(int r = 0; r < b.length; r++){
place queen in row[r] of column[n];
if(n == numberOfQueens){
print the board;
return;
}
else{
solver(n+1, board with queen in row[r] of column[n]);
}
}
}
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
使用递归来解决此类问题的目的是，它们允许您思考“我现在已经放置了 k 个皇后；如果皇后总数为 <，我该如何放置剩余的皇后呢？” em>n？”因此，递归函数应该采用两个参数：目标皇后数量和目前放置的皇后数量。编写函数时，您的首要目标是尝试放置第 k 个皇后的不同方法。但是，当您选择了可能的位置并发现它有效时，您需要放置剩余的n - k - 1个皇后。我们怎样才能做到这一点？答案是：递归！使用参数 k - 1 调用该函数（从其自身内部）以指示您要放置剩余的 k - 1 皇后。每当您穷尽所有可能性（或发现没有一个是可能的）时，只需从该函数返回 - 然后您将返回到上一个函数调用（例如，尝试放置第 k 个皇后的函数调用） 。
编辑：您还需要创建一个二维数组来表示板的当前状态；该数组必须作为附加参数发送给递归函数，或者保留为包含该方法的类的字段。
至于回溯，只需确保使用 k + 1 调用的函数在返回之前从棋盘上删除 k + 1 皇后即可完成；这实质上是说“我们现在（不成功）尝试了所有放置剩余皇后的方法 - 基于已放置的 k 个皇后的位置。没有一个成功，所以请调整前 k 个皇后的位置（这将由使用 k 调用的函数以及调用该函数的函数等来完成）并尝试再次。”
The purpose of using recursion for these kinds of problems is that they allow you to think in terms of "I have now placed k queens; how can I place the remaining ones if the total number of queens is n?" So the recursive function should take two parameters: the target number of queens, and the number of queens placed so far. When writing the function, your goal is first and foremost to try out different ways of placing the k th queen. But when you have selected a possible placement and found it to be valid, you need to place the remaining n - k - 1 queens. How can we do this? The answer: recursion! Call the function (from within itself) with the parameter k - 1 to indicate that you want to place the remaining k - 1 queens. Whenever you exhaust all possibilities (or find that none are possible), simply return from the function - you will then get back to the previous function call (e.g. the one that tries to place the k th queen).
Edit: You will also need to create a two-dimensional array to represent the current state of your board; this array must either be sent as an additional parameter to the recursive function, or be kept as a field of the class that contains the method.
As for the backtracking, that is accomplished simply by making sure that the function that gets called with k + 1 removes the k + 1 th queen from the board before returning; this essentially says "We've now (unsuccessfully) tried all ways of placing the remainder of the queens - based on the positions of the k queens that have already been placed. None of them succeeded, so please adjust the positions of the first k queens (which will be done by the function that was called with k, and the function which called that function, and so on) and try again."
一般来说，递归回溯搜索看起来像这样：
请注意，对于给定的有效深度为
d-1的s，可能有多种方法将其增强为状态在深度d内有效。这个想法是给每个人打电话给你自己。对于这个问题，“状态”就是董事会。深度“d-1”可能意味着前 d-1 列已填充。合法的增强状态是那些在 d 列中有女王的状态，这样她就不会被捕获。
[更新]
这是另一种看待它的方式。倒推问题。
假设我要求您编写一个名为
solver8()的简单函数。此函数将棋盘作为输入，前 7 列中已存在皇后。它所要做的就是拿起该棋盘，找到所有方法将皇后添加到第 8 列，然后打印出这些棋盘。你认为你能写出这个函数吗？好的;写下来。现在假设我要求您编写一个几乎同样简单的函数，名为
solver7()。此函数将棋盘作为输入，前 6 列中已存在皇后。它所要做的就是获取该棋盘，找到将皇后添加到第 7 列的所有方法，并将每个棋盘作为参数传递给solver8()。你能写出这个函数吗？现在假设我要求您编写另一个名为
solver6()的函数。作为输入，它需要一个棋盘，其中前 5 列中有皇后。它所要做的就是获取该棋盘，找到将皇后添加到第 6 列的所有方法，然后将每个棋盘传递给solver7()。依此类推，直到到达
solver1()。这个例子需要一个空棋盘，找到在第一列中放置皇后的所有方法，并将每个棋盘传递给solver2()。您刚刚编写了 8 个函数，它们一起解决了 8 个皇后问题。如果这没有意义，请将其写为 8 个函数，然后盯着它看，直到你明白为止。
现在，如果您查看所有这些函数，您会发现它们非常相似。因此，您不必编写solver8，solver7，solver6，...，solver1，而是编写一个函数：
...这样solver(1, b)与solver1(b)相同，solver(2, b)是与solver2(b)相同，...，solver(8, b)与solver8(b)相同。例如，您将只让solver(2, ...) 调用solver(3, ...)，而不是solver2(...) 调用solver3(...)。一个函数而不是 8 个函数，但做同样的事情。
您很快就会发现，如果您从只需要完全填充的板并将其打印出来的
solver9()开始，并且具有solver8()就这么称呼吧。Generally speaking, a recursive backtracking search looks something like this:
Note that for a given
svalid up to depthd-1, there could be multiple ways to augment it into a state valid up to depthd. The idea is to call yourself with each of them.For this problem, the "state" is the board. The depth "d-1" might mean the first d-1 columns are populated. The legal augmented states would be those with a queen in column d such that she cannot be captured.
[update]
Here is another way to look at it. Work the problem backwards.
Suppose I ask you to write a simple function called
solver8(). This function takes as input a board with queens already present in the first 7 columns. All it has to do is take that board, find all ways to add a queen to the 8th column, and print out those boards. Do you think you could write this function? Good; write it.Now suppose I ask you to write an almost-as-simple function called
solver7(). This function takes as input a board with queens already present in the first 6 columns. All it has to do is take that board, find all ways to add a queen to the 7th column, and pass each of those boards as an argument tosolver8(). Could you write this function?Now suppose I ask you to write another function called
solver6(). As input, it takes a board with queens present in the first 5 columns. All it has to do is take that board, find all ways to add a queen to the 6th column, and then pass each of those boards tosolver7().And so on, until we get to
solver1(). This one takes an empty board, finds all ways to place a queen in the first column, and passes each of those boards tosolver2().You have just written 8 functions that together solve the 8 queens problem. If this does not make sense, write it out as 8 functions and stare at it until you do.
Now, if you look at all of these functions, you will find they are pretty similar. So instead of writing solver8, solver7, solver6, ..., solver1, you write a single function:
...such that solver(1, b) is the same as solver1(b), solver(2, b) is the same as solver2(b), ..., and solver(8, b) is the same as solver8(b). And instead of solver2(...) calling solver3(...), for instance, you will just have solver(2, ...) calling solver(3, ...). One function instead of 8, but doing the same thing.
You will pretty quickly discover that the final code is cleaner if you start with a
solver9()that just takes a fully populated board and prints it out, and havesolver8()call that.在
使用递归的 8 皇后问题上查看这个漂亮的动画。另外，请查看：
8 个皇后问题 - Java/C++。查看
逻辑的解释这里。See this nice animation here on
8 queen's problem using recursion.Also, check out :
8 queens problem - Java/C++.Check out the
logicexplained here.将第一个皇后放入 [0][0] 中，然后为第二个皇后找到一个位置。假设您发现一个转到下一个，依此类推。假设您的第五个皇后不能放置在第五列或第五行的任何位置（无论您遵循哪个）。返回到 4 号并找到另一个位置。然后再去 5 号。假设您在 8 号，并且没有空位。转到第七层，那里仍然没有任何东西。你会继续回去，直到第二个，然后再次找到第二个位置，然后去第三个。有道理吗...
Put the first queen in [0][0], then find a spot for the second. lets say you found one go to the next, so on and so forth. Assumingly your 5th queen cant be placed anywhere in the 5th column or row (whichever you follow). Go back to the 4th and find another spot to that. Than go to the 5th again.Lets say you are in the 8th one and there are no spots available. Go to 7th and still nothing back there. You will kep on going back until the 2nd and find a spot to the 2nd again, and go to the 3rd. Does it make sense...
希望这个解决方案能够帮助
要点是
1.递归简单到低于
2.IsValidposition
2.1 十字皇后在同一列中找到，如
2.2 十字皇后在对角线上找到，如
或
代码：
92 8 皇后问题的可能解决方案：
Hope this Solution helps
Main Points are
1.Recursion simple to under
2.IsValid position
2.1 cross Queen found in same column like
2.2 cross Queen found diagonally like
or
Code :
92 Possible Solutions to 8 Queens Problem: