java - 数独 - 递归回溯可能的解决方案计数器

Question

我正在研究一个小的个人数独游戏并试图扩展它。

到目前为止，我使用递归回溯方法使“求解”部分正常工作，该方法在设法求解递归时返回 true。

现在我正在尝试构建一个独特的解决方案板生成器，并且我在网上找到了很多关于如何实现它的信息。

但是，我在第一步上苦苦挣扎，这是我的 boolean 递归回溯算法到一个递归算法，该算法对可能的解决方案进行计数。这对于检查我生成的板是否是唯一的至关重要。

更重要的是，我意识到在实现一些递归排序之前我一直在努力解决这个问题:How to transform a boolean recursive function into a recursive function that returns some kind of count (int/long)，不失去功能？是否有任何可遵循的准则或技术？

附件是到目前为止的工作代码。

import java.util.Scanner;

public class Sudoku {

    int[][] board;

    public Sudoku(){}

    public Sudoku(int n){
        this.board=new int[n][n];
    }

    /* Creates an NxN game.board in a two-dimensional array*/
    public static int[][] createBoard(int n)
    {
        int[][] board = new int[n][n];
        for (int i=0; i<board.length; i++)
            for (int j=0; j<board[i].length; j++)
                board[i][j]=0;
        return board;
    }

    /* prints the game.board*/
    public static void printBoard(int[][] b)
    {
        int buffer=(int)Math.sqrt(b.length);
        // fitting the bottom line into any size of game.board
        String btm=new String(new char[buffer*buffer*3+buffer+1]).replace("\0", "_");

        for (int i=0; i<b.length; i++)
        {
            if (i%buffer==0)
                System.out.println(btm);
            for (int j=0; j<b[i].length; j++)
            {
                if (j%buffer==0)
                    System.out.print("|");
                if (b[i][j]==0)
                    System.out.print(" _ ");
                else
                    System.out.print(" " + b[i][j] + " ");
            }
            System.out.println("|");
        }
        System.out.println(btm);
    }

    /* returns true if a number can be inserted in a row, otherwise returns false. */
    public static boolean checkLegalRow(int[][] b, int row, int num)
    {
        for (int i=0; i<b.length; i++)
        {
            if (b[row][i]==num)
                return false;
        }
        return true;
    }
    /* returns true if a number can be inserted in a column, otherwise returns false.*/
    public static boolean checkLegalCol(int[][] b, int col, int num)
    {
        for (int i=0; i<b.length; i++)
        {
            if (b[i][col]==num)
                return false;
        }
        return true;
    }

    /*returns true if number can be inserted in its local box.*/
    public static boolean checkLegalBox(int[][] b, int row, int col, int num)
    {
        int buffer=(int)Math.sqrt(b.length);
        for (int i=0, adjRow=row-(row%buffer); i<buffer; i++, adjRow++)
        {
            for (int j=0, adjCol=col-(col%buffer); j<buffer; j++, adjCol++)
            {
                if (b[adjRow][adjCol]==num)
                    return false;
            }
        }
        return true;
    }

    /*allows user input for a sudoku game.board*/
    public static void fillInBoardConsole(int[][] b)
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Please enter a row: ");
        int r=sc.nextInt();
        System.out.print("Please enter a column: ");
        int c=sc.nextInt();
        System.out.print("Please enter a number from 1 to "+b.length+": ");
        int num=sc.nextInt();
        while (num>b.length || num<1)
        {
            System.out.print("Please enter a number from 1 to "+b.length+": ");
            num=sc.nextInt();
        }
        b[r][c]=num;
        sc.close();
    }

    /* returns true if all the conditions for sudoku legal move are met: there is no 
 * number on the same row, column, box, and the cell isn't taken*/
    public static boolean legalMove(int[][] b, int row, int col, int num)
    {
        return checkLegalRow(b,row,num) && checkLegalCol(b,col,num) && checkLegalBox(b,row,col,num) && b[row][col]==0;
    }

    /* returns true if the initial board setting is legal*/
    public static boolean initialLegal(int[][] b)
    {
        int num;
        for (int i=0; i<b.length; i++)
        {
            for (int j=0; j<b[i].length; j++)
            {
                if (b[i][j]!=0)
                {
                    num=b[i][j];
                    b[i][j]=0;
                    if (!(checkLegalRow(b,i,num) && checkLegalCol(b,j,num) && checkLegalBox(b,i,j,num)))
                    {
                        b[i][j]=num;
                        return false;
                    }
                    else
                        b[i][j]=num;
                }
            }
        }
        return true;
    }

    /* using backtrack algorithm and recursion to solve the sudoku*/
    public static boolean solveBacktrack(int[][] b, int row, int col)
    { 
        /*If the cell is already taken by a number:
         * case 1: if its the last cell (rightmost, lowest) is already taken, sudoku solved
         * case 2: if its the rightmost cell not on the if it is the rightmost column but not 
         * the lowest row, go to the leftmost cell in next row
         * case 3: if it's a regular cell, go for the next cell*/
        if (b[row][col]!=0)
        {
            if (col==b.length-1) 
                if (row==b.length-1)
                {
                    //printgame.board(b); // case 1
                    return true; 
                }
                else 
                    return solveBacktrack(b,row+1,0); // case 2
            else
                return solveBacktrack(b,row,col+1); // case 3
        }

        boolean solved=false;

        for (int k=1; k<=b.length; k++) //iterates through all numbers from 1 to N
        {
            // If a certain number is a legal for a cell - use it
            if (legalMove(b,row,col,k)) 
            {
                b[row][col]=k;
                if (col==b.length-1) // if it's the rightmost column
                {
                    if (row==b.length-1) // and the lowest row - the sudoku is solved
                    {
                        //printgame.board(b);
                        return true;
                    }
                    else
                        solved=solveBacktrack(b,row+1,0); // if its not the lowest row - keep solving for next row
                }
                else // keep solving for the next cell
                    solved=solveBacktrack(b,row,col+1);
            }
            if (solved)
                return true;
            else //if down the recursion sudoku isn't solved-> remove the number (backtrack)
            {
                b[row][col]=0;
            }
        }
        return solved;
    }

    /*  public static long solveCountSolutions(int[][]b, int row, int col, long counter)
    {   

    }
     */ 


    public static void main(String[] args)
    {
        Sudoku game = new Sudoku(9);
        game.board[0][2]=5;game.board[0][1]=3; game.board[0][0]=1;
        game.board[8][2]=4;game.board[8][4]=3;game.board[8][6]=6;
        printBoard(game.board);
        if (initialLegal(game.board))
            System.out.println(solveBacktrack(game.board,0,0));
        else
            System.out.println("Illegal setting");
        printBoard(game.board);
    }
}

Answer 1

这样的函数可以通过在找到解决方案时不退出递归来实现，而是将该解决方案转储到外部结构(如果您只需要计数，请在函数外部的某处创建一个计数器，但对它可见，并在找到解决方案后增加它)，然后继续搜索，就像你已经走到了死胡同一样。符合这一点的东西(抽象代码):

static int solutions=0;
bool recursiveSolver(TYPE data) {
    TYPE newData;
    while (!nextChoice(data)) {
        if (solved(data)) {
            // return true; not now, we count instead
            solutions++;
        }
        newData=applyNextChoice(data); // for recursion
        if (recursiveSolver(newData)) { 
           return true; // will never hit, but checking is needed for solver to work
        }
    } 
    // all choices checked, no solution
    return false;
}

applyNextChoice() 是数独游戏中“选择下一个数字，放入此单元格”的占位符。 TYPE 是表示不完整解决方案的任何结构的占位符，在您的情况下是组合的 int[][] b, int row, int col。