文档章节

数独解题程序

悠悠然然
 悠悠然然
发布于 2014/02/08 10:51
字数 1803
阅读 7.4K
收藏 10

一个假期过去,明显编程水平大降,键盘都敲不好了,于是就想着恢复一下。怎么恢复呢?写个数独解题程序吧。

public class Sudoku {
    int[][] data = new int[9][9];//填好的数字
    List<Integer>[][] dataLeft = new ArrayList[9][9];//每个位置可能的数字

    public Sudoku(int data[][]) {
        this();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (data[i][j] != 0) {
                    putNumber(i, j, data[i][j]);
                }
            }
        }
    }

    public Sudoku() {
        //初始化数据
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                data[i][j] = 0;
                dataLeft[i][j] = new ArrayList<Integer>();
                for (int k = 1; k <= 9; k++) {
                    dataLeft[i][j].add(k);
                }
            }
        }
    }

    public void putNumber(int x, int y, Integer n) {
        data[x][y] = n;//此点位置赋值
        dataLeft[x][y].clear();//可能数字清空;
        //清理水平和竖直
        for (int i = 0; i < 9; i++) {
            if (i != x) {
                dataLeft[i][y].remove(n);
            }
            if (i != y) {
                dataLeft[x][i].remove(n);
            }
        }
        //清理小空格
        int startX = x / 3;
        int startY = y / 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i + startX * 3 != x && j + startY * 3 != y) {
                    dataLeft[i + startX * 3][j + startY * 3].remove(n);
                }
            }
        }
    }

    public void compute() {
        int count = 0;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (dataLeft[i][j].size() == 1) {
                    putNumber(i, j, dataLeft[i][j].get(0));
                    count++;
                }
            }
        }
        if (count == 0) {
            System.out.println("Compute completed.");
        } else {
            compute();
        }
    }

    public void print() {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.printf("%d ", data[i][j]);
            }
            System.out.println();
        }
    }
}

编写测试的入口方法:

public class Test {
    public static void main(String[] args) {
      int[][]data={
              {6,0,5,0,0,2,0,0,8},
              {0,4,0,3,8,0,0,5,0},
              {3,0,0,0,6,0,7,0,2},
              {0,5,0,0,0,3,0,4,0},
              {0,6,1,0,0,4,8,7,0},
              {0,2,0,0,7,8,0,6,0},
              {1,0,9,0,2,0,0,0,4},
              {0,7,0,0,4,1,0,2,0},
              {2,0,0,9,0,0,5,0,7}};
        Sudoku sudoku=new Sudoku(data);
        sudoku.compute();
        sudoku.print();
    }
}
下面是运行结果:
Compute completed.
6 9 5 7 1 2 4 3 8 
7 4 2 3 8 9 1 5 6 
3 1 8 4 6 5 7 9 2 
8 5 7 6 9 3 2 4 1 
9 6 1 2 5 4 8 7 3 
4 2 3 1 7 8 9 6 5 
1 3 9 5 2 7 6 8 4 
5 7 6 8 4 1 3 2 9 
2 8 4 9 3 6 5 1 7
事实证明,简单的数独确实是可以算出来的。

这时,再给一个复杂的算一下:

public class Test1 {
    public static void main(String[] args) {
      int[][]data={
              {0,0,0,0,0,8,1,0,0},
              {7,0,0,9,0,0,0,0,6},
              {0,0,8,0,3,0,7,0,0},
              {4,0,0,0,0,9,3,0,0},
              {8,0,0,0,7,0,0,0,5},
              {0,0,3,0,2,5,0,0,9},
              {0,0,4,0,6,0,2,0,0},
              {5,0,0,0,0,2,0,0,7},
              {0,0,2,1,0,0,0,0,0}};
        Sudoku sudoku=new Sudoku(data);
        sudoku.compute();
        sudoku.print();
    }
}

计算结果如下:

Compute completed.
0 0 0 0 0 8 1 0 0 
7 0 0 9 0 0 0 0 6 
0 0 8 0 3 0 7 0 0 
4 0 0 0 0 9 3 0 0 
8 0 0 0 7 0 0 0 5 
0 0 3 0 2 5 0 0 9 
0 0 4 0 6 0 2 0 0 
5 0 0 0 0 2 0 0 7 
0 0 2 1 0 0 0 0 0

呵呵,显而易见,它的计算能力太差了,已经无法计算了。

吃过饭之后,再对数独程序进行增强。增强之后,成为下面的样子:

public class Sudoku {
    int[][] data = new int[9][9];//填好的数字
    List<Integer>[][] dataLeft = new ArrayList[9][9];//每个位置可能的数字


    public Sudoku(int data[][]) {
        this();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (data[i][j] != 0) {
                    putNumber(i, j, data[i][j]);
                }
            }
        }
    }


    public Sudoku() {
        //初始化数据
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                data[i][j] = 0;
                dataLeft[i][j] = new ArrayList<Integer>();
                for (int k = 1; k <= 9; k++) {
                    dataLeft[i][j].add(k);
                }
            }
        }
    }


    public void putNumber(int x, int y, Integer n) {
        data[x][y] = n;//此点位置赋值
        dataLeft[x][y].clear();//可能数字清空;
        //清理水平和竖直
        for (int i = 0; i < 9; i++) {
            if (i != x) {
                dataLeft[i][y].remove(n);
            }
            if (i != y) {
                dataLeft[x][i].remove(n);
            }
        }
        //清理小空格
        int startX = x / 3;
        int startY = y / 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i + startX * 3 != x && j + startY * 3 != y) {
                    dataLeft[i + startX * 3][j + startY * 3].remove(n);
                }
            }
        }
    }


    public void compute() {
        int count = 0;
        //计算某个位置只有一个数字的情况
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (dataLeft[i][j].size() == 1) {//如果只有一个可能的数字,那就是它了
                    putNumber(i, j, dataLeft[i][j].get(0));
                    count++;
                }
            }
        }
        if (count == 0) {//如果没有唯一一个数的,则查找只出现过一次的
            count += computeRow();
            count += computeColumn();
            count += computeBox();
        }


        if (count > 0) {
            compute();
        }
    }


    public int computeRow() {
        int c = 0;
        for (int i = 0; i < 9; i++) {//行
            int[] count = new int[9];
            for (int j = 0; j < 9; j++) {//列
                for (int num : dataLeft[i][j]) {
                    count[num - 1]++;//统计个数
                }
            }
            for (int k = 0; k < 9; k++) {
                if (count[k] == 1) {//如果区域内的某个数字可能次数为1
                    for (int j = 0; j < 9; j++) {
                        if (dataLeft[i][j].contains(k + 1)) {
                            putNumber(i, j, k + 1);
                            c++;
                        }
                    }
                }
            }
        }
        return c;
    }




    public int computeBox() {
        int c = 0;
        for (int dx = 0; dx < 3; dx++) {
            for (int dy = 0; dy < 3; dy++) {
                //9个小格子
                int[] count = new int[9];
                List<Point>[] points = new ArrayList[9];
                for (int i = 0; i < 9; i++) {
                    points[i] = new ArrayList<Point>();
                }
                for (int i = 0; i < 3; i++) {//行
                    for (int j = 0; j < 3; j++) {//列
                        for (int num : dataLeft[dx * 3 + i][dy * 3 + j]) {
                            count[num - 1]++;//统计个数
                            points[num - 1].add(new Point(dx * 3 + i, dy * 3 + j));
                        }
                    }
                }
                for (int k = 0; k < 9; k++) {
                    if (count[k] == 0) {//如果没有


                    } else if (count[k] == 1) {//如果区域内的某个数字可能次数为1
                        putNumber(points[k].get(0).x, points[k].get(0).y, k + 1);
                    } else {//如果出现次数大于1
                        Point point = points[k].get(0);
                        boolean sameRow = true;
                        boolean sameColumn = true;
                        for (int i = 1; i < points[k].size(); i++) {
                            Point p = points[k].get(i);
                            if (p.x != point.x) {
                                sameRow = false;
                            }
                            if (points[k].get(i).y != point.y) {
                                sameColumn = false;
                            }
                        }
                        if (sameRow) {// 且在一行上,则可以进行区块排除
                            cleanRow(point.x, dy, k + 1);
                        }
                        if (sameColumn) {// 且在一列上,则可以进行区块排除
                            cleanColumn(dx, point.y, k + 1);
                        }
                    }
                }
            }
        }


        return c;
    }


    private void cleanColumn(int dx, int y, Integer n) {
        for (int i = 0; i < 3; i++) {
            if (i != dx) {
                for (int j = 0; j < 3; j++) {
                    dataLeft[i * 3 + j][y].remove(n);
                }
            }
        }
    }


    private void cleanRow(int x, int dy, Integer n) {
        for (int i = 0; i < 3; i++) {
            if (i != dy) {
                for (int j = 0; j < 3; j++) {
                    dataLeft[x][i * 3 + j].remove(n);
                }
            }
        }
    }
    public int computeColumn() {
        int c = 0;
        for (int i = 0; i < 9; i++) {//行
            int[] count = new int[9];
            for (int j = 0; j < 9; j++) {//列
                for (int num : dataLeft[j][i]) {
                    count[num - 1]++;//统计个数
                }
            }
            for (int k = 0; k < 9; k++) {
                if (count[k] == 1) {//如果区域内的某个数字可能次数为1
                    for (int j = 0; j < 9; j++) {
                        if (dataLeft[j][i].contains(k + 1)) {
                            putNumber(j, i, k + 1);
                            c++;
                        }
                    }
                }
            }
        }
        return c;
    }


    public void print() {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.printf("%d ", data[i][j]);
            }
            System.out.println();
        }
    }

    class Point {
        private final int x;
        private final int y;


        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

再次计算上面算不出来的数独:

Compute completed.
2 4 6 7 5 8 1 9 3 
7 3 5 9 4 1 8 2 6 
1 9 8 2 3 6 7 5 4 
4 5 7 6 1 9 3 8 2 
8 2 9 4 7 3 6 1 5 
6 1 3 8 2 5 4 7 9 
9 8 4 5 6 7 2 3 1 
5 6 1 3 8 2 9 4 7 
3 7 2 1 9 4 5 6 8

Yeah,居然算出了,这个大大超出我的意料。

至此,一般难度的数独及相当难度的数独都可以算出了,后续又增加了区块排除法,智力稍微又强大了一些,但是非常难的需要应用复杂逻辑推理的还是解不开。

小结:

代码有一定的优化,先用效率高的算法进行快速计算,效率高的算法没有进展,再用效率低的算法计算。

相对来说,其算法不一定相当优化,但是实现还是非常简单的,主要是采用逻辑计算方法。已实现的逻辑有:

a.基础摒除法

b.唯余解法

c.区块摒除法

我的区分逻辑与非逻辑的方法很简单:落子为安为逻辑,落子不安为暴力

由于没有进行过深入测试,欢迎验证其正确性。

© 著作权归作者所有

悠悠然然

悠悠然然

粉丝 2481
博文 185
码字总数 363246
作品 14
杭州
架构师
私信 提问
加载中

评论(3)

悠悠然然
悠悠然然 博主
呵呵,只是用来练脑的,采用逻辑方法来解比较简单或比较中级的难度的题,只要打印结果包含0,就是说明解不出了。真正求解数独,还是暴力方法更简单些。
悠悠然然
悠悠然然 博主

引用来自“夜色无边”的评论

我写过一个用回溯法做的,一直循环到最后一个格的

Oh,欢迎分享~~
我这个目前只支持两个规则:
规则1:如果一行、一列、一个9宫中一个数字只能出现在一个位置,则设置其位置;
规则2:如果一行、一列、一个9宫中,某个位置只能放一个数字,则设置其位置;
真正的解题方案还有许多复杂的规则的。
所以只能说是解解普通难度的。骨灰级的,还要再增加规则才可以。
夜色无边
夜色无边
我写过一个用回溯法做的,一直循环到最后一个格的
数独游戏--qtsudoku

使用QT C++框架来开发的传统数独游戏,在Windows,Linux,Wince和Symbian上分别编译发布。 主要功能需求 支持标准数独,锯齿数独,对角线数独, 杀手数独的题目生成与解题 支持网络对战(游戏服...

匿名
2010/03/02
4K
0
标准数独游戏--KLSudoku

因为自己喜欢玩传统的标准数独,所以借学习CSharp的机会来编写一个标准传统数独的题目生成和解题的游戏软件,并且力求它可以为你增加更多的解题乐趣。 KLSudoku所有 源码免费开放,但是请先阅...

匿名
2010/03/02
2.9K
0
自己做的数独软件,带解题技巧

奕数独2.0采用C++和Java开发,有8种类型的数独,自带多种解题技巧。目前可以支持Android2.3以上版本。 云盘下载地址:http://pan.baidu.com/s/1jGMfa4Y,多个市场均可以下载。...

天下伯爵
2014/11/27
437
1
JAVA代码—算法基础:数独问题(Sodoku Puzzles)

数独问题(Sodoku Puzzles) 数独游戏(日语:数独 すうどく)是一种源自18世纪末的瑞士的游戏,后在美国发展、并在日本得以发扬光大的数学智力拼图游戏。 拼图是九宫格(即3格宽×3格高)的...

seagal890
2018/03/24
0
0
验证数独棋盘

原题   Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.   The Sudoku board could be partially filled, where empty cells are filled with the charact......

一贱书生
2016/12/14
87
0

没有更多内容

加载失败,请刷新页面

加载更多

WPF中的StaticResource和DynamicResource有什么区别?

在WPF中使用画笔,模板和样式等资源时,可以将它们指定为StaticResources <Rectangle Fill="{StaticResource MyBrush}" /> 或者作为DynamicResource <ItemsControl ItemTemplate="{DynamicR......

javail
26分钟前
49
0
Day07继承中的面试题 答案

1. 每一个构造方法的第一条语句默认都是:super() Object类最顶层的父类。 class Zi extends Fu{ public int num = 20; public Zi(){ //super(); System.out.println("zi"); } 2.class Test......

Lao鹰
31分钟前
42
0
每天AC系列(四):四数之和

1 题目 Leetcode第18题,给定一个数组与一个target,找出数组中的四个数之和为target的不重复的所有四个数. 2 暴力 List<List<Integer>> result = new ArrayList<>();if (nums.length == 4 &......

Blueeeeeee
41分钟前
54
0
git clone --mirror和git clone --bare有什么区别

git clone帮助页面上有关于--mirror : 设置远程存储库的镜像。 这意味着--bare 。 但没有详细介绍--mirror克隆与--bare克隆--mirror不同。 #1楼 克隆将从远程服务器复制参考,并将其填充到名...

技术盛宴
57分钟前
72
0
代码生成器技术乱弹二十六,未来之野望,未实现的功能:动态Controller名字后缀

现在,光1.5.0的Controller后缀是固定的。比如:UserController, PrivilegeController之类的。而动态Controller名字后缀功能实现后,您只需要定义 controllernamingsuffix:Adaoter Control...

火箭船
今天
53
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部