文档章节

计算机解决数独,只是网上存个档,勿喷

林小宝
 林小宝
发布于 2018/06/07 16:31
字数 1023
阅读 26
收藏 0

计算机解决数独,只是网上存个档,勿喷

解决各种数独 9x9  16x16
16x16的需要大量时间。

初始 0 表示 空

代码

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.concurrent.atomic.AtomicLong;
 
/**
 * 数独
 * 
 * @author zlb
 */
public class ShuDu {
    private final int DD_SIZE;
    private final int SQRT_SIZE;
    private final int[][] dd;
 
    public ShuDu(String filePath) {
        this(filePath, 9);
    }
 
    public ShuDu(String filePath, int size) {
        DD_SIZE = size;
        SQRT_SIZE = (int) Math.sqrt(size);
        dd = new int[DD_SIZE][DD_SIZE];
        if (SQRT_SIZE * SQRT_SIZE != DD_SIZE) {
            throw new IllegalArgumentException(" size error !" + size);
        }
        BufferedReader in = null;
        int vv = 0;
        int i = 0;
        try {
            in = new BufferedReader(new FileReader(filePath));
            String line;
            for (i = 0; i < DD_SIZE; i++) {
                while (null != (line = in.readLine())) {
                    line = line.trim();
                    if (!line.isEmpty()) {
                        break;
                    }
                }
                if(null !=line){
                    line = line.replaceAll("\\s{2,}", " ");
                    String[] cc = line.split(" ");
                    for (int j = 0; j < cc.length; j++) {
                        vv = Integer.valueOf(cc[j]);
                        dd[i][j] = vv;
                    }
                }
            }
        } catch (Exception e) {
            throw new IllegalArgumentException("参数异常 :filePath= " + filePath
                    + " : " + i, e);
        } finally {
            if (null != in) {
                try {
                    in.close();
                } catch (IOException e) {
                }
            }
        }
    }
 
    public int[][] getDd() {
        return dd;
    }
 
    public void show(int[][] values) {
        System.out.println("------------------------------------");
        for (int i = 0; i < values.length; i++) {
            for (int j = 0; j < values[i].length; j++) {
                System.out.print(String.format("%-4d", values[i][j]));
            }
            System.out.println();
        }
        System.out.println("\n====================================");
    }
 
    public boolean isFormDD(int[][] values) {
        for (int i = 0; i < DD_SIZE; i++) {
            for (int j = 0; j < DD_SIZE; j++) {
                if (0 != dd[i][j] && dd[i][j] != values[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
 
    public int check(int[][] values) {
        int result = 0;
        for (int i = 0; i < DD_SIZE; i++) {// 初始化
            for (int j = 0; j < DD_SIZE; j++) {
                if (0 != dd[i][j] && dd[i][j] != values[i][j]) {
                    result += 1;
                    continue;
                }
                if (check(values, i, j) > 0) {
                    result++;
                }
            }
        }
        return result;
    }
 
    protected int check(int[][] values, int row, int col) {
        if (0 == values[row][col]) {
            return 1;
        }
        int vv = values[row][col];
        int j = row / SQRT_SIZE * SQRT_SIZE;
        int k = col / SQRT_SIZE * SQRT_SIZE;
        for (int i = 0; i < DD_SIZE; i++) {// check row
            if (i != row && 0 == values[i][col] && vv == values[i][col]) {
                return 2;
            }
            if (i != col && 0 == values[row][i] && vv == values[row][i]) {
                return 3;
            }
            if (row != (j + i / SQRT_SIZE) && col != (k + i % SQRT_SIZE)) {
                if (0 != values[j + i / SQRT_SIZE][k + i % SQRT_SIZE]
                        && vv == values[j + i / SQRT_SIZE][k + i % SQRT_SIZE]) {
                    return 4;
                }
            }
        }
        return 0;
    }
 
    public int[][] exhaustiveAttack() {
        int[][] tmp = new int[DD_SIZE][DD_SIZE];
        for (int i = 0; i < DD_SIZE; i++) {// 初始化
            for (int j = 0; j < DD_SIZE; j++) {
                tmp[i][j] = dd[i][j];
            }
        }
        if (solve(tmp, 0, 0)) {
            System.out.println("solve & isFormDD  == " + isFormDD(tmp));
        }
        return tmp;
    }
 
    protected AtomicLong callTime = new AtomicLong();
 
    protected boolean solve(int[][] sk, int row, int col) {
        long tmp = callTime.incrementAndGet();
        if (tmp % 10000000 == 0) {
            System.out.println(String
                    .format("%s do [%2s - %2s]", tmp, row, col));
        }
        if (col >= DD_SIZE) {
            col = 0;
            row++;
        }
        if (row >= DD_SIZE)
            return true;
 
        if (sk[row][col] != 0)
            return solve(sk, row, ++col); // 若当前格子已有解则进行下一个格子的运算.
 
        int sqrt_row = row / SQRT_SIZE * SQRT_SIZE;
        int sqrt_col = col / SQRT_SIZE * SQRT_SIZE;
        for (int i = 0; i < DD_SIZE; i++) {
            int vv = i + 1;
            for (int j = 0; j < DD_SIZE; j++) { // 非当前节点不在行列及宫中
                if (row != j && sk[j][col] == vv) {
                    vv = 0;
                    break;
                }
                if (col != j && sk[row][j] == vv) {
                    vv = 0;
                    break;
                }
                if ((row != (sqrt_row + j / SQRT_SIZE) && col != (sqrt_col + j
                        % SQRT_SIZE))
                        && vv == sk[sqrt_row + j / SQRT_SIZE][sqrt_col + j
                                % SQRT_SIZE]) {
                    vv = 0;
                    break;
                }
            }
            sk[row][col] = vv;
            if (vv > 0 && solve(sk, row, col + 1)) {
                return true;
            }
        }
        sk[row][col] = 0;
        return false;
    }
 
    public static void main(String[] args) {
        new ShuDu("./sd/jn1.txt").report();
    }
 
    public void report() {
        show(dd);
        System.out.println("is null : " + check(dd));
        long time = System.currentTimeMillis();
        int[][] result = exhaustiveAttack();
        show(result);
        time = System.currentTimeMillis() - time;
        String msg = String.format("ok[ %s ] time[ %s ms ] call[ %s ]",
                check(result), time, callTime.get());
        System.out.println(msg);
    }
}

示例输入 9*9

9 0 6 0 1 3 0 0 8
0 5 8 0 0 0 0 9 0
0 3 0 0 0 0 0 1 0
0 6 0 8 0 0 9 2 0
0 0 3 4 0 9 1 0 0
0 4 9 0 0 6 0 3 0
0 9 0 0 0 0 0 8 0
0 1 0 0 0 0 6 7 0
4 0 0 9 6 0 3 0 1

示例 16*16

1   0   0   0   11  7   0   0   0   0   13  2   0   0   0   10 
0   0   0   12  4   0   0   8   10  0   0   3   5   0   0   0  
0   0   5   4   0   0   16  0   0   9   0   0   6   3   0   0  
0   16  14  0   0   10  0   13  1   0   11  0   0   15  2   0  
7   15  0   0   8   0   0   0   0   0   0   12  0   0   16  1  
14  0   0   3   0   0   0   0   0   0   0   0   4   0   0   9  
0   0   13  0   0   0   1   2   3   4   0   0   0   6   0   0  
0   1   0   11  0   0   5   6   7   8   0   0   12  0   13  0  
0   2   0   6   0   0   9   10  11  12  0   0   16  0   5   0  
0   0   1   0   0   0   13  14  15  16  0   0   0   9   0   0  
11  0   0   13  0   0   0   0   0   0   0   0   10  0   0   4  
12  14  0   0   1   0   0   0   0   0   0   7   0   0   15  3  
0   6   16  0   0   12  0   15  13  0   4   0   0   11  10  0  
0   0   4   9   0   0   11  0   0   7   0   0   14  5   0   0  
0   0   0   5   14  0   0   4   16  0   0   6   7   0   0   0  
13  0   0   0   10  3   0   0   0   0   12  14  0   0   0   15

© 著作权归作者所有

林小宝
粉丝 5
博文 30
码字总数 11167
作品 2
深圳
私信 提问
iscroll 使用同个wrapper多状态数据切换重新定位到顶部

https://blog.csdn.net/qq_26409411/article/details/79021301 问题:移动端同个页面,有个状态导航栏(几种状态)切换请求数据操作同一个wrapper里面的数据。不同状态切换过程中,新的状态如...

壹峰
2018/07/31
0
0
在学校,推广一个淘宝客网站,大家觉得可行不?

不是突发奇想吧,自己早就有这个打算,只是想知道有没有哪位仁兄,有类似的经验?小弟想在学校做一个淘宝返利的网站(当然现在自己也没有能力去写这样的一个系统,只能在网上找点淘宝客的源码...

请叫我赵小宝
2014/10/13
654
6
android 线程销毁如何做到真正销毁?

最近遇到线程销毁的问题,网上看了很多资料,都是千篇一律,根据他们的例子,也并没有 得到具体解决,而且 还更加疑惑,比如 http://www.open-open.com/lib/view/open1394113617887.html 这边...

黛曦葛溪
2016/02/03
1K
1
音乐客户端应用的免流量功能可以通过缓存的方式实现么

今天在网上查了一些手机端应用的免流量功能的实现方式,都是通过由运营商提供的流量包来实现的。不知道有没有高手研究过这个问题,可不可以通过缓存技术来实现这种对缓存的调用,类似于在用户...

smh821025
2018/01/05
73
2
毕设系列之Libx264实时视频流(YUV 420P转H264视频编码篇)

#PS:要转载请注明出处,本人版权所有 #PS:这个只是 《 我自己 》理解,如果和你的 #原则相冲突,请谅解,勿喷 开发环境:Ubuntu 16.04 LTS 本文的技术实现部分参考雷博士的这篇文章。http:...

u011728480
2017/08/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

最开始学习素描的步骤是什么?

最开始学习素描的步骤是什么?很多学画画的朋友们都会问直接跳过素描不学素描行不行,小编非常的肯定告诉你不行,素描是所以绘画类的基础,台阶是一层一层筑起的,目前的现实是未来理想的基础...

设绘嗨
22分钟前
1
0
Caused by: java.lang.ClassCastException: scala.collection.mutable.WrappedArray

code val linkPairSum = F.udf( (list:List[Map[Long,Int]]) => { var map = Map[Long,Int]() for(m <- list){ if(m != null){ ......

张欢19933
22分钟前
1
0
git常见问题

一、clone代码 clone 1.登录账号密码不对 fatal: Authentication failed for 2.权限不足 Permission denied (publickey) 或者emote: User permission denied fatal: unable to access u......

hexiaoming123
32分钟前
1
0
Mybatis操作mysql 8的Json字段类型

Json字段是从mysql 5.7起加进来的全新的字段类型,现在我们看看在什么情况下使用该字段类型,以及用mybatis如何操作该字段类型 一般来说,在不知道字段的具体数量的时候,使用该字段是非常合...

算法之名
40分钟前
37
0
Windows7至Windows10的升级建议

目前,诸多企业或已开始在进行Windows7至Windows10的升级,或正在规划Windows7升级至Windows10。 主要原因有两个: Windows7的生命周期即将结束,这意味着再也无法获取Windows7的安全更新,以...

嘉为科技
43分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部