解决N个皇后区的回溯问题

Question

我目前正在尝试学习Java中的回溯主题。这真的让我感到困惑，因为我被困住了。问题是找到将N个皇后区放置在NxN国际象棋棋盘中的方法，以使任何一个皇后区都不能互相攻击。女王可以在同一行，同一列和对角线进攻。我的代码是这样的：

import java.util.Scanner;

class Main {
    public static void putZero(int[][] board,int n){
         for(int i = 0;i<n;i++){
            for(int j=0;j<n;j++){
                board[i][j]=0;
            }
        }
    }
    public static void printBoard(int[][] board,int n){
        for(int i = 0;i<n;i++){
            for(int j=0;j<n;j++){
                System.out.print(board[i][j]);
            }
            System.out.print("\n");
        }
         System.out.print("\n\n\n");
    }
    public static void SolveNQ(int n){
        int[][] board = new int[n][n];
        putZero(board,n);
        if(SolveQUtil(board,0,n)==true){
            printBoard(board,n);
        }
    }
    public static boolean isSafe(int row, int col, int[][] board,int n){
        int i,j;
        for(i=0;i<col;i++){
           if(board[row][i]==1)
            return false;
        } 
        for(i=row,j = col; i >= 0 && j >= 0; i--, j--){
        if(board[i][j]==1)
        return false;
        }
         for (i = row, j = col; j >= 0 && i < n; i++, j--) 
            if (board[i][j] == 1) 
                return false;

        return true;
    }
    public static boolean SolveQUtil(int[][] board, int col, int n){
        if(col>=n){
            return true;
        } 
        else 
        for(int i=0;i<n;i++){
        if(isSafe(i,col,board,n)==true){
                board[i][col]=1;
        boolean a = SolveQUtil(board,col+1,n);
        if(a==true)
                return true;
        else 
            board[i][col]=0;
        }  
    }   
        return false;

    }
     public static void main(String[] args){
        Scanner scan = new Scanner(`enter code here`System.in);
        int n = scan.nextInt();;
        SolveNQ(n);
     }
}

它正在产生我想要的结果，但是我不明白这是如何工作的。在我的方法SolveQUtil（）中，该方法再次被调用，这是“递归的”。调用col = 0时，由于不存在皇后，因此Q1放置在[0,0]。但是当col = 1递归调用时，它将搜索合适的位置并返回'true'。现在，难道不是每次返回true时SolveNQ（）都要打印解决方案吗？什么时候返回假？怎么运作的？我是初学者，有人可以逐步向我解释一下吗？预先谢谢你。

Answer 1

SolveNQ，它执行打印，不会递归调用； SolveQUtil称为SolveNQ，并且它执行not打印任何内容，是递归的。