数独dfs（java）

Amber ·

更新时间:2024-11-14

· 895 次阅读

数独：
如下图所示，玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个同色九宫内的数字均含1-9，不重复。数独的答案都是唯一的，所以，多个解也称为无解。本图的数字据说是芬兰数学家花了3个月的时间设计出来的较难的题目。但对会使用计算机编程的你来说，恐怕易如反掌了。本题的要求就是输入数独题目，程序输出数独的唯一解。我们保证所有已知数据的格式都是合法的，并且题目有唯一的解。格式要求，输入9行，每行9个数字，0代表未知，其它数字为已知。输出9行，每行9个数字表示数独的解。
在这里插入图片描述
利用dfs解决此类问题，具体看代码注释，如下：

import java.util.Scanner;
public class Sd {
    //数独游戏（深搜法）
    public void dfs(char [][]a,int b,int c)
    {
        if (b==9)//出口
        {
            for (int i=0;i<=8;i++)//打印输出
                System.out.println(a[i]);
            System.exit(0);//退出程序
        }
        if (a[b][c]=='0')
        {
            for (int i=1;i<=9;i++)
            {
                if (check(a,b,c,i))
                {
                    char []temp=String.valueOf(i).toCharArray();
                    a[b][c]=temp[0];//(char)('0'+k)//给当前状态赋值
                    dfs(a,b+(c+1)/9,(c+1)%9);//状态转移
                }
            }
            a[b][c]='0';//回溯
        }
        else
        {
            dfs(a,b+(c+1)/9,(c+1)%9);//状态转移
        }
    }
    public boolean check(char [][]a,int x,int y,int c)//检查在这个点放值是否合适
    {
        for (int i=0;i<=8;i++)//检验每一行每一列
        {
            if (a[x][i]==(char)('0'+c)||a[i][y]==(char)('0'+c))
                return false;
        }
        for (int i=(x/3)*3;i<=(x/3+1)*3;i++)//检验每一个小九宫格
            for (int j=(y/3)*3;j<=(y/3+1)*3;j++)
            {
                if (a[x][y]==(char)('0'+c))
                    return false;
            }
            return true;
    }
    public static void main(String[] args) {
        Scanner a=new Scanner(System.in);
        char [][]b=new char[9][9];
        for (int i=0;i<9;i++)//字符数组的输入
            b[i]=a.nextLine().toCharArray();
        Sd c=new Sd();
        c.dfs(b,0,0);
    }
}

结果如下：
在这里插入图片描述