Решение вопроса о возвращении N Queens

Question

В настоящее время я пытаюсь узнать топи c Backtracking в Java. Это действительно очень смущает меня, потому что я застрял. Задача состоит в том, чтобы найти способы размещения N Queens на шахматной доске NxN, чтобы ни одна из Queen не могла атаковать друг друга. Королева может атаковать в той же строке, той же колонке и по диагонали. Мой код выглядит так:

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 вызывает и который не печатает что-либо, является рекурсивным.