# Sudoku

**Repository Path**: janbar/Sudoku

## Basic Information

- **Project Name**: Sudoku
- **Description**: go语言破解数独。
- **Primary Language**: Go
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2017-11-28
- **Last Updated**: 2025-01-02

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

1. 求解数独的思路
	我想通过自己的思路来求解，虽然网上肯定有非常巧妙高效的解法。因此我安装了HoDoKu这个软件，这个软件会分析当前数独每个待填格子可能存在的值，目前我发现Naked Or Hiden Single这2中是最容易找出来的，找出来了该位置就必填那个数。下图是一个例子，表示裸露的单个数字，该位置只有一种可能值。经过仔细研究,我得出了2个原则：
	**1.当前位置只有一种可能值，则优先填入**
	**2.当前位置的可能值在当前行列宫格唯一，那么这个值是隐藏的单个，也是必填的**
![该位置必填的数](https://ws1.sinaimg.cn/large/a5bd7ddagy1fmcxybwc5fj20lz0cqwk4.jpg)
	有了上述2个原则，那么我必须有一种算法计算每一个待填单元格可能填入的数据。其实很简单，只需要遍历这些代填的位置，然后变量当前行列所在宫格，去掉已经确定的值，剩下的就是代填值。

	经过上面的计算也只能将代填位置确认值填好，但是剩下有可能存在多个值且无法确定。因此我首先想到的就是暴力破解法，假设代填位置为其中一个可能值，由此继续填数字，每次填入数字后再进行一次上面找以确定单个数，如果无法继续，或者得到一个存在某个位置没有可能填入数据则说明假设出错，恢复上一次保存的状态，继续假设下一个可能值。具体流程图如下：
![](https://ws1.sinaimg.cn/large/a5bd7ddagy1fmcya3xz92j20jb0ef77e.jpg)

	下面就贴上我的代码，其中保存状态用了栈结构，每次缓存则压栈，恢复则弹栈：

上面的方案效率在应对简单级别的也是很快的，基本毫秒级别。这里找了一个在线数独网站[在线玩数独](https://www.newdoku.com/zh/sudoku.php)，下面是在里面找的骨灰级运算结果：
![](https://ws1.sinaimg.cn/large/a5bd7ddagy1fmcyul6cxcj206x0920tq.jpg)
但是比较蛋疼的就是暴力求解存在把所有解遍历一遍的情况，那将遍历非常大，虽然我已经保证每次把确定的值填入，但仍然无可避免，下面就是一个例子，用时44分钟：
![](https://ws1.sinaimg.cn/large/a5bd7ddagy1fmcyw5z20rj207t0ac40l.jpg)
好了上面就把我自己的想法写成代码，并能正确得到结果，只是某些情况计算效率比较低，而且没有处理存在多个值的情况。
1. 舞蹈链求解数独
	求解数独最佳方案当然是舞蹈链了，优点就是不会占用多于空间，缓存和恢复状态非常快。
	http://www.cnblogs.com/grenet/p/3145800.html 讲解舞蹈链
	http://www.cnblogs.com/grenet/p/3163550.html 讲解如何用舞蹈链解数独
	代码灵感主要来源于上面的博客，并且舞蹈链求解比较快，因此我也做了多解数组至少算2种结果
2. 舞蹈链求解的具体流程就参照上面博客吧，下面把我的代码贴上：
3. 下面我用了一个多解数独测试，并且我已经百度最难数独，求解也是非一般的感觉：
![](https://ws1.sinaimg.cn/large/a5bd7ddagy1fmczgy9nntj207r0higo2.jpg)
4. 经过这次求解数独，我发现了舞蹈链这种好玩又高效的数据结构。比我的暴力破解穷举所有数据要快的多。

数独辅助工具
https://sourceforge.net/projects/hodoku/files/hodoku/hodoku_2.2.0/