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

Question

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

到目前为止，我使用递归回溯方法使“Solve”部分正常工作，每当它设法解决递归时，就会返回true。

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

然而，我在第一步很挣扎，这是我的布尔递归回溯算法变成一个递归算法，它保留了一个可能解决方案的计数。这对于检查我生成的板是否是唯一的至关重要。

更重要的是，我意识到我以前在实现一些递归排序时遇到过这个问题：如何将布尔递归函数转换为返回某种计数（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。