使用回溯重复的8个皇后问题

Question

我一直在研究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]);
                }
           }
     }
}

Answer 1

使用递归来解决这些问题的目的是,它们允许你用"我现在已经放置了k个皇后来思考;如果皇后的总数是n,我怎么能放置其余的？" 所以递归函数应该有两个参数:目标皇后数和到目前为止放置的皇后数.在编写函数时,您的目标首先是尝试不同的方式来放置第k个女王.但是当你选择了一个可能的位置并发现它有效时,你需要放置剩下的n - k - 1个皇后.我们应该怎么做？答案:递归!使用参数k - 1调用该函数(从其自身内部)以指示您要放置剩余的k - 1个皇后.无论何时耗尽所有可能性(或发现没有可能),只需从函数返回 - 然后您将返回上一个函数调用(例如,尝试放置第k个女王的函数).

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

至于回溯,这是通过确保用k + 1调用的函数在返回之前从板上移除第k + 1个后置函数来实现的; 这本质上说,"现在,我们已经(不成功)尝试放置皇后的剩余的所有方式- 基于已经被放置k个皇后的位置,他们都没有成功,所以请调整第一的位置ķ皇后(将由使用k调用的函数和调用该函数的函数完成,等等)并重试."