[Java] 數(shù)獨(dú)生成和求解

skinner 發(fā)布于2019-08-14 15:20 / 2871人閱讀

摘要：首先在二維數(shù)組第一行隨機(jī)填充個(gè)數(shù)字，然后將這個(gè)數(shù)字隨機(jī)分布到整個(gè)二維數(shù)組中，然后使用求解數(shù)獨(dú)的算法對(duì)此時(shí)的數(shù)組進(jìn)行求解，得到一個(gè)完整的數(shù)獨(dú)，然后按照用戶輸入的提示數(shù)量進(jìn)行隨機(jī)挖洞，得到最終的數(shù)獨(dú)題目。

思路 1.生成數(shù)獨(dú)

數(shù)獨(dú)的生成總體思路是挖洞法。
首先在二維數(shù)組第一行隨機(jī)填充1-9 9個(gè)數(shù)字，然后將這9個(gè)數(shù)字隨機(jī)分布到整個(gè)二維數(shù)組中，然后使用求解數(shù)獨(dú)的算法對(duì)此時(shí)的數(shù)組進(jìn)行求解，得到一個(gè)完整的數(shù)獨(dú)，然后按照用戶輸入的提示數(shù)量進(jìn)行隨機(jī)挖洞，得到最終的數(shù)獨(dú)題目。
這種方法理論上可以隨機(jī)生成(81!/72! = 9.5e+16)種不同的數(shù)獨(dú)題目，足夠人類玩上幾百年了。

2.求解數(shù)獨(dú)

求解數(shù)獨(dú)使用的是計(jì)算機(jī)最擅長(zhǎng)的暴力搜索中的回溯法。并結(jié)合人求解數(shù)獨(dú)的思維過(guò)程增加了一點(diǎn)改進(jìn)。
在每一層搜索中，首先計(jì)算每個(gè)格子可以填充的值的個(gè)數(shù)（我命名為不確定度），如果有格子不確定度為1，則直接填上數(shù)字就好，否則對(duì)不確定度最小的格子使用可能的數(shù)字逐個(gè)填充，并進(jìn)入下一次遞歸。如果發(fā)現(xiàn)不確定度為0的格子，做說(shuō)明之前的過(guò)程有問(wèn)題，需要進(jìn)行回溯。

代碼

package sudo;

import java.util.Scanner;
/**
 * @description 數(shù)獨(dú)生成和求解
 * @limit 支持從1-80的數(shù)字提示數(shù)量
 * @method 深度優(yōu)先搜索/回溯法
 * @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
    
    /**
     * 構(gòu)造函數(shù)
     * 初始化變量
     */
    public Sudo(){
        lef = 0;
        for(int i=0;i<9;++i){
            for(int j=0;j<9;++j){
                data[i][j] = 0;
            }
        }
    }
    /**
     * 生成數(shù)獨(dú)
     * 方法：挖洞法
     */
    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個(gè)數(shù)字放在二維數(shù)組中隨機(jī)位置*/
        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;
        }
        /*通過(guò)9個(gè)數(shù)字求出一個(gè)可行解*/
        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("-----------------");
    }
    /**
     * 計(jì)算某格子的可填數(shù)字個(gè)數(shù)，即不確定度
     * @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調(diào)用的深度優(yōu)先搜索
     * @return 是否有解的boolean標(biāo)識(shí)
     */
    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的程序運(yùn)行結(jié)果。