我一直在研究八皇后问题,但卡住了。我不需要代码,我希望得到指导和方向以便理解如何使用回溯递归来解决这个问题。
该程序应通过绘制皇后的位置来枚举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]);
}
}
}
}