[Java] 数独生成和求解

摘要：首先在二维数组第一行随机填充个数字，然后将这个数字随机分布到整个二维数组中，然后使用求解数独的算法对此时的数组进行求解，得到一个完整的数独，然后按照用户输入的提示数量进行随机挖洞，得到最终的数独题目。

数独的生成总体思路是挖洞法。
首先在二维数组第一行随机填充1-9 9个数字，然后将这9个数字随机分布到整个二维数组中，然后使用求解数独的算法对此时的数组进行求解，得到一个完整的数独，然后按照用户输入的提示数量进行随机挖洞，得到最终的数独题目。
这种方法理论上可以随机生成(81!/72! = 9.5e+16)种不同的数独题目，足够人类玩上几百年了。

求解数独使用的是计算机最擅长的暴力搜索中的回溯法。并结合人求解数独的思维过程增加了一点改进。
在每一层搜索中，首先计算每个格子可以填充的值的个数（我命名为不确定度），如果有格子不确定度为1，则直接填上数字就好，否则对不确定度最小的格子使用可能的数字逐个填充，并进入下一次递归。如果发现不确定度为0的格子，做说明之前的过程有问题，需要进行回溯。

package sudo;

import java.util.Scanner;
/**
 * @description 数独生成和求解
 * @limit 支持从1-80的数字提示数量
 * @method 深度优先搜索/回溯法
 * @author chnmagnus
 */
public class Sudo {
    
    private int[][] data = new int[9][9]; //muti_array
    private int lef; //the number of zero in array
    private int tip; //the number of nozero_digit in array
    
    /**
     * 构造函数
     * 初始化变量
     */
    public Sudo(){
        lef = 0;
        for(int i=0;i<9;++i){
            for(int j=0;j<9;++j){
                data[i][j] = 0;
            }
        }
    }
    /**
     * 生成数独
     * 方法：挖洞法
     */
    public void genSudo(){
        System.out.println("Please input the number of digits provided:");
        Scanner scan = new Scanner(System.in);
        tip = scan.nextInt();
        scan.close();
        /*将1-9 9个数字放在二维数组中随机位置*/
        lef = 81 - 9; 
        for(int i=0;i<9;++i){
            data[0][i] = i+1;
        }
        for(int i=0;i<9;++i){
            int ta = (int)(Math.random()*10)%9;
            int tb = (int)(Math.random()*10)%9;
            int tem = data[0][ta];
            data[0][ta] = data[0][tb];
            data[0][tb] = tem;
        }
        for(int i=0;i<9;++i){
            int ta = (int)(Math.random()*10)%9;
            int tb = (int)(Math.random()*10)%9;
            int tem = data[0][i];
            data[0][i] = data[ta][tb];
            data[ta][tb] = tem;
        }
        /*通过9个数字求出一个可行解*/
        solveSudo();
        lef = 81 - tip;
        for(int i=0;i0)
                    System.out.print(data[i][j]+" ");
                else
                    System.out.print("* ");
            }
            System.out.print("
");
        }
        System.out.println("-----------------");
    }
    /**
     * 计算某格子的可填数字个数，即不确定度
     * @param r
     * @param c
     * @param mark
     * @return 不确定度
     */
    private int calcount(int r,int c,int[] mark){
        for(int ti=0;ti<10;++ti) 
            mark[ti] = 0;
        for(int i=0;i<9;++i){
            mark[data[i][c]] = 1;
            mark[data[r][i]] = 1;
        }
        int rs = (r/3)*3;
        int cs = (c/3)*3;
        for(int i=0;i<3;++i){
            for(int j=0;j<3;++j){
                mark[data[rs+i][cs+j]] = 1;
            }
        }
        int count = 0;
        for(int i=1;i<=9;++i){
            if(mark[i]==0)
                count++;
        }
        return count;
    }
    /**
     * 供solve调用的深度优先搜索
     * @return 是否有解的boolean标识
     */
    private boolean dfs(){
        if(lef==0) return true;
        int mincount = 10;
        int mini = 0,minj = 0;
        int[] mark = new int[10];
        /*找到不确定度最小的格子*/
        for(int i=0;i<9;++i){
            for(int j=0;j<9;++j){
                if(data[i][j]!=0) continue;
                
                int count = calcount(i,j,mark);
                if(count==0) return false;
                if(count
演示
以下四幅图分别是输出为0，20，60的程序运行结果。