使用回溯解决 java 数独

Question

我正在尝试使用 java 编写数独解算器。我为此使用了一种常见的回溯算法。但是程序运行不正常(returning null)

这是代码

public class Sudoku {

    int[][] board;                                                              //Sudoku board


    public Sudoku() {                                                           //constructor
        this.board = new int[9][9];             
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
                board[i][j]=0;
    }

    public Sudoku(int[][] board){                                               //constructor
        this.board=board;
    }


    public int[][] Solve(int[][] board){
        int i, j, k,l,val;                                                      //iterators 
        int empty=1;                                                            //empty flag
        int[][] temp=new int[9][9];                                             //temporary array for backtracking
        temp=board;
        for(i=0;i<9;i++)                                                        //check if any empty space available
            for(j=0;j<9;j++){
                if(board[i][j]==0){
                    empty=0;
                    break;
                }
            }
        if(empty==1)return board;
        for(i=0;i<9;i++)
            outerLoop:
            for(j=0;j<9;j++){
                if(board[i][j]>0)continue;
                for(val=1;val<10;val++){                                        //try values
                    for(k=0;k<9;k++){
                        if(board[i][k]==val)break;                              //check row consistancy 
                        if(board[k][j]==val)break;                              //check column consistancy     
                    }
                    for(k=(i/3)*3;k<(i/3+1)*3;k++)                              //check latin square consistancy
                        for(l=(j/3)*3;l<((j/3+1)*3);l++)
                            if(board[k][l]==val)break;                      
                    temp[i][j]=val;                                             //put consistant value
                    Solve(temp);                                                //recursive call for backtrack
                }
        }
        return null;                                                            
    }


    public static void main(String[] args) {
        // TODO code application logic here
        int[][] board={ {5,3,0,0,7,0,0,0,0},
                        {6,0,0,1,9,5,0,0,0},
                        {0,9,8,0,0,0,0,6,0},
                        {8,0,0,0,6,0,0,0,3},
                        {4,0,0,8,0,3,0,0,1},
                        {7,0,0,0,2,0,0,0,6},
                        {0,6,0,0,0,0,2,8,0},
                        {0,0,0,4,1,9,0,0,5},
                        {0,0,0,0,8,0,0,7,9}};
        Sudoku s=new Sudoku(board);
        int[][] temp=new int[9][9];
        temp=s.Solve(board);
        for(int i=0;i<9;i++){
            System.out.println("");
            for(int j=0;j<9;j++){
                System.out.print(temp[i][j]);
                System.out.print(",");
            }
        }
    }    
}

由于 netbeans 的建议，我放置了 null return 语句，但它应该永远不会 return null。我找不到错误。在此先感谢您的工业帮助。

Answer 1

我将重点介绍您的 Solve(int[][]) 方法：

public int[][] Solve(int[][] board){

根据 Java 命名约定，方法应为驼峰式：solve(int[][] board)

    int i, j, k,l,val;

除非必要，否则不应在方法的开头定义迭代器。它给了他们一个 'false sense of purpose'，使代码更难解释。

    int empty=1;

这应该是一个布尔值，因为它只持有 1 或 0 的值。布尔值在这里会更易读：boolean empty = false;

    int[][] temp=new int[9][9];                                             
    temp=board;

此外，我建议将您的代码分解为 'paragraphs' 或相关操作。当您从定义转向一些初始逻辑时，这将是一个新段落的好地方。

    for(i=0;i<9;i++)                                                        
        for(j=0;j<9;j++){
            if(board[i][j]==0){
                empty=true;
                break;
            }
        }
    if(!empty)return board;

这应该是一个单独的段落，因为它处理单个任务，即检查棋盘是否已解决。我还更新了它以显示布尔值如何更好地阅读。

    for(i=0;i<9;i++)
        outerLoop:
        for(j=0;j<9;j++){
            if(board[i][j]>0)continue;
            for(val=1;val<10;val++){                                        
                for(k=0;k<9;k++){
                    if(board[i][k]==val)break;                               
                    if(board[k][j]==val)break;                                  
                }
                for(k=(i/3)*3;k<(i/3+1)*3;k++)                              
                    for(l=(j/3)*3;l<((j/3+1)*3);l++)
                        if(board[k][l]==val)break;                      
                temp[i][j]=val;                                             
                Solve(temp);                                                
            }
    }
    return null;                                                            
}

您的代码有两个 return 语句，一个用于完成电路板，一个用于捕获逻辑错误。错误出在您的递归调用中。仅调用 Solve(temp); 不会保留您对数据所做的任何更改。递归函数仅在您使用递归调用生成的新信息时才有效。因此，要修复您的错误，return 您的递归调用：

return Solve(temp);

使用回溯解决 java 数独

Sudoku solving in java using backtrack

java

algorithm

artificial-intelligence