寒光博客

[LanQiao]数独游戏 dfs(深度优先搜索)
题目描述 如下图所示,玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个同...
扫描右侧二维码阅读全文
04
2019/08

[LanQiao]数独游戏 dfs(深度优先搜索)

题目描述

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

测试样例

输入:

005300000
800000020
070010500
400005300
010070006
003200080
060500009
004000030
000009700

输出

145327698
839654127
672918543
496185372
218473956
753296481
367542819
984761235
521839764

输入

800000000
003600000
070090200
050007000
000045700
000100030
001000068
008500010
090000400

输出

812753649
943682175
675491283
154237896
369845721
287169534
521974368
438526917
796318452


数独游戏的话使用(DFS)深度优先搜索的方法是比较方便的,可以搜出数独的唯一合法的解。 一条路走到黑 无死角搜索。 记得回溯

package BlueCup.Seven_recursion;

import java.util.Scanner;

public class Dfs1数独 {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        char[][] table = new char[9][];
        for (int i = 0; i < 9; i++) {
            table[i] = cin.nextLine().toCharArray();
        }
        dfs(table, 0, 0);
    }
    private static void print(char[][] table) {
        for (int i = 0; i < 9; i++) {
            System.out.println(new String(table[i]));
        }
    }
    public static void dfs(char[][] t, int x, int y) {
        if (x==9){//超出边界
            print(t);
            System.exit(0);//完全结束递归
        }
        if (t[x][y] == '0') {
            for (int i = 1; i <= 9; i++) {
                boolean res = check(t, x, y, i);//检查是否重复 行列矩形内
                if (res) {
                    t[x][y] = (char) ('0' + i);
                    dfs(t, x + (y + 1) / 9, (y + 1) % 9);//状态转移
                }
            }
            t[x][y] = '0';//回溯
        } else {
            dfs(t, x + (y + 1) / 9, (y + 1) % 9);//状态转移
        }
    }

    private static boolean check(char[][] t, int x, int y, int i) {
        for (int j = 0; j < 9; j++) {
            int tmp = i + '0';//没有和i重复
            if (t[x][j] == tmp || t[j][y] == tmp) {//行列
                return false;
            }
            for (int k = (x/3)*3; k <(x/3+1)*3 ; k++) {//小矩形
                for (int l = (y/3)*3; l <(y/3+1)*3 ; l++) {
                    if(t[k][l]==tmp)return false;
                }
            }
        }
        return true;
    }
}

GitHub

本文作者:Author:     文章标题:[LanQiao]数独游戏 dfs(深度优先搜索)
本文地址:https://dxoca.cn/Algorithm/217.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:October 26th, 2019 at 12:33 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment

4 comments

  1. 程志辉 QQ浏览器 8.1 Android 9 中国 湖北

    JAVA不会,回头用JS试试看好了,上面还是没看懂思路啊,我的思路是一行行遍历一列列遍历填,但是这样效率估计会很低.......

    1. Dxoca Google Chrome 74.0.3724.8 Windows 10 中国 青海 黄南藏族自治州
      @程志辉

      我不会告诉你这是我第一次玩数独

    2. Dxoca Google Chrome 74.0.3724.8 Windows 10 中国 青海 黄南藏族自治州
      @程志辉

      而且 这是递归嘛qwq

    3. Dxoca Google Chrome 74.0.3724.8 Windows 10 中国 青海 黄南藏族自治州
      @程志辉

      一样是 一行一行遍历 或者说状态转移 不过 这个转移算法很妙
      dfs(t, x + (y + 1) / 9, (y + 1) % 9)
      y是8的倍数 才会让 换行qwq 0~8嘛 刚好一行