Java使用递归回溯解决数独Sudoku问题

不念不忘少年蓝@ 2023-10-05 19:49 13阅读 0赞

[https://codepumpkin.com/sudoku-solver-using-backtracking/][https_codepumpkin.com_sudoku-solver-using-backtracking]

数独是一个基于逻辑的组合数字放置难题。给定部分填充的9×9 2D阵列网格\[9\] \[9\]，目标是为空单元格分配数字（从1到9），以便大小为3×3的每一行，每一列和每个子网格都恰好包含一个从1到9的数字实例。

![sudoku Solver][]

数独可以使用递归回溯算法解决。  
  
什么是回溯算法？  
在回溯算法中，您尝试一次构建一个解决方案。如果在某些步骤上可以清楚地知道当前的路径无法导致解决方案，则请返回上一步（回溯）并选择其他路径。  
简而言之，一旦在某个步骤中用尽了所有选项，便会返回。想一想迷宫或迷宫–您如何找到一条从入口到出口的路？一旦达到死胡同，就必须回溯。但是回溯到哪里？到上一个选择点。  
回溯也称为深度优先搜索。  
递归回溯算法解决数独问题的方法  
1.像所有其他回溯问题一样，我们可以通过将数字分配给空单元格来解决数独问题。  
2.在分配编号之前，我们需要确认当前行，当前列和当前3X3子网格中没有相同的编号。  
3.如果在相应的行，列或子网格中不存在数字，则可以分配该数字，然后递归检查此分配是否导致解决方案。  
如果分配没有解决方案，则我们尝试为当前的空单元格输入下一个数字。  
如果没有数字（1到9）导致解，则返回false。

![Sudoku Solver using backtracking][]

Java程序实现  
数独，9×9 int数组用于存储数独的所有元素。  
实例变量sudoku可以使用以下两个构造函数中的任何一个进行初始化。  
完全解决数独数组的所有单元格都必须分配有效值。  
数独解决方案在其任何单元格中具有UNASSIGNED即0值，被认为是不完整或错误的。

class Sudoku
    {
        private int[][] sudoku;
        private static final int UNASSIGNED = 0;
         
        public Sudoku()
        {
            sudoku = new int[9][9];
        }
         
        public Sudoku(int sudoku[][])
        {
            this.sudoku= sudoku;
        }
         
        //TO-DO Methods
        //private boolean containsInRow(int row,int number){...}
        //private boolean containsInCol(int col,int number){...}
        //private boolean containsInBox(int row, int col,int number){...}
        //private boolean isAllowed(int row, int col,int number){...}
        //public void displaySudoku(){...}
        //public boolean solveSudoku(){...}
    }

以下三种方法用于检查当前行，当前列和当前3X3子网格中是否存在数字。

private boolean containsInRow(int row,int number)
    {
    	for(int i=0;i<9;i++)
    	{
    		if(sudoku[row][i]==number)
    		{
    			return true;
    		}
    	}
    	return false;
    }
     
    
     
    private boolean containsInCol(int col,int number)
    {
    	for(int i=0;i<9;i++)
    	{
    		if(sudoku[i][col]==number)
    		{
    			return true;
    		}
    	}
    	return false;
    }
     
     
    private boolean containsInBox(int row, int col,int number)
    {
    	int r = row - row%3;
    	int c = col - col%3;
    	for(int i = r ; i< r+3 ; i++)
    	{
    		for(int j = c; j < c+3 ; j++)
    		{
    			if(sudoku[i][j]==number)
    			{
    				return true;
    			}
    		}
    		 
    	}
    	return false;
    }

isAllowed（）方法使用上述三种方法来检查在单元格中分配数字是否安全。如果上述三种方法中的任何一个返回 true，则表示该单元格中不允许使用  
特定数字。

private boolean isAllowed(int row, int col,int number)
    {
        return !(containsInRow(row, number) || containsInCol(col, number) || containsInBox(row, col, number));
    }

resolveSudoku（）  
方法开始从左上方的单元格遍历到右侧。  
它逐行检查每行中的单元格，并选择具有UNASSIGNED值的第一个单元格。  
它检查从1到9的允许数字，将第一个可能的选项分配给单元格，然后  
为下一个UNASSIGNED单元格  
再次调用  
resolveSudoku（）  
方法。  
它递归地遵循相同的过程。  
这个过程一直持续到找到某个不允许数字的单元格，函数将返回false为止。  
如果函数返回false，则控件将回溯到先前分配的单元格，并在那里尝试另一个数字。  
如果找到任何允许的号码，则将这个新号码分配给单元格，然后过程再次继续。  
但是，如果没有其他可能的数目，它将再次回到先前分配的单元，并且过程继续。  
此过程一直持续到找到正确的解决方案或到达找不到解决方案的阶段为止。

public boolean solveSudoku()
    {
    	for(int row=0;row<9;row++)
    	{
    		for(int col=0;col<9;col++)
    		{
    			if(sudoku[row][col]==UNASSIGNED)
    			{
    				for(int number=1;number<=9;number++)
    				{
    					if(isAllowed(row, col, number))
    					{
    						sudoku[row][col] = number;
    						if(solveSudoku())
    						{
    							return true;
    						}
    						else
    						{
    							sudoku[row][col] = UNASSIGNED;
    						}
    					}
    				}
    				return false;
    			}
    		}
    	}
    	return true;
    }

**displaySudoku（）方法用于以数独形式显示9×9数组。**

public void displaySudoku()
    {
        for(int i=0;i<9;i++)
        {
            if(i%3==0 && i!=0)
            {
                System.out.println("----------------------------------\n");
            }
            for(int j=0;j<9;j++)
            {
                if(j%3==0 && j!=0)
                {
                    System.out.print(" | ");
                }
                System.out.print(" " + sudoku[i][j] + " ");
     
            }
     
            System.out.println();
        }
        System.out.println("\n\n__________________________________________\n\n");
    }

[Download Complete Java Program »][Download Complete Java Program]

[https_codepumpkin.com_sudoku-solver-using-backtracking]: https://codepumpkin.com/sudoku-solver-using-backtracking/
[sudoku Solver]: https://img-blog.csdnimg.cn/img_convert/9e998da50011e814ef1950ef0b127232.png
[Sudoku Solver using backtracking]: https://img-blog.csdnimg.cn/img_convert/09af15fb2097fdaf3308a005e871614a.gif
[Download Complete Java Program]: https://github.com/codepumpkin/Data-Structures-And-Algorithms/blob/master/src/com/codepumpkin/algorithms/recursion/SudokuSolver.java