java - 解决 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”。现在，SolveNQ() 不是应该在每次返回 true 时打印解决方案吗？什么时候返回false？这是如何运作的？我是初学者，有人可以一步一步向我解释这一点吗？预先感谢您。

Answer 1

SolveNQ 执行打印，但不会递归调用； SolveQUtil(SolveNQ 调用)是递归的，并且不打印任何内容。