java - 使用回溯递归的 8 皇后问题

Question

我一直在研究 8 皇后问题，但我被卡住了。我不要代码。我希望得到指导和指导，以便了解如何使用回溯递归自行解决此问题。

程序应该像两个解决方案一样，通过在 ASCII 中绘制皇后的位置来枚举 N 皇后问题的所有解决方案 here .

到目前为止我的伪代码是:

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]);
                }
           }
     }
}

Answer 1

对此类问题使用递归的目的是，它们允许您根据“我现在已经放置了k个皇后；如果总共有皇后区是 n？”所以递归函数应该有两个参数:目标皇后数和目前放置的皇后数。编写函数时，您的首要目标是尝试放置第 k 个皇后的不同方法。但是当您选择了一个可能的放置并发现它有效时，您需要放置剩余的 n - k - 1 个皇后。我们应该怎么做？答案是:递归!使用参数 k - 1 调用函数(从自身内部)以指示您要放置剩余的 k - 1 个皇后。每当您用尽所有可能性(或发现不可能)时，只需从该函数返回 - 然后您将返回到上一个函数调用(例如，尝试放置第 k 个皇后的函数调用) .

编辑:您还需要创建一个二维数组来表示板的当前状态；此数组必须作为附加参数发送给递归函数，或者作为包含该方法的类的字段保留。

至于回溯，只需确保使用 k + 1 调用的函数在之前从棋盘上移除第 k + 1 个皇后即可实现返回；这基本上是说“我们现在(未成功)尝试了所有放置其余皇后的方法 - 基于已经放置的 k 个皇后的位置。他们都没有成功，所以请调整前 k 个皇后的位置(这将由用 k 调用的函数以及调用该函数的函数等完成)并尝试又来了。”