7668人阅读
算法，数独问题用概率算法中的拉斯维加斯算法实现数独问题的生成用回溯法实现对数独问题的求解
注：数独问题与数度难题的区别是数度难题只有一个解，而数独问题的解有一个或多个。
Introduction :
标准的数独游戏是在一个 9 X 9 的棋盘上填写 1 – 9 这 9 个数字，规则是这样的：
棋盘分成上图所示的 9 个区域（不同颜色做背景标出，每个区域是 3 X 3 的子棋盘），在每个子棋盘中填充 1 – 9 且不允许重复 ，下面简称块重复每一行不许有重复值 ，下面简称行重复每一列不许有重复值 ，下面简称列重复
如上红色框出的子区域中的亮黄色格子只能填 8。
扩展阅读：
随机生成数独问题，如果做成一个数独小游戏的话可以按游戏难易程度生成，比如有简单、中等、困难三个程度求解数独问题，根据生成的数独问题或者用户输入的数独问题求解出所有答案或者求解出不超过MAX个答案，因为某个问题可能含有上十万个解，用MAX约束找到MAX个答案后就不再找其它的答案
有一种求解数独问题的方案是“候选数字法”，就是在待填充的格子中填写不会造成行重复、列重复、块重复的数字，有的时候存在多个这样的数字，那么我们可以随机选取一个，如果待填充的格子中填写任何一个数字都会造成某种重复的发生，则说明这个问题没有解，也就是这不是一个数独问题。如上图中红色框出区域的下面一个区域的红色格子中可以填写的数字为 4、8、9，那么它的候选数字就是4、8、9，你可以随机选一个填入。当所有的格子填充完后数独问题就解决了。
根据上述的这种候选数字法，我们可以用它来生成数独问题以及求解数独问题。
关于生成数独问题：
循环遍历 9 X 9 的数独格子，在遍历到的当前格子的候选数字中随机选取一个数字填入，如果当前格子没有了候选数字则清空所有已经填好的格子，重新再来。这是一个最简单的也是最容易理解的概率方法了。伪码如下：
1: int[][] sudoku = new int[9][9]; //数独棋盘
2: while(true) {
clearSudoku(); //清空所有已填数字, 每个格子置 0
for(int row = 0; row & 9; row++) {
for(int col = 0; col & 9; col++) {
//getCandidates(row, col) 获取当前格子的候选数字
//randomCandidate() 随机选取一个候选数字
if(getCandidates(row, col) != NULL) //如果有候选数字
sudoku[row][col] = randomCandidate(getCandidates(row, col));
goto //跳转到label那里清空格子重新来过
关于求解数独问题：
同上， 不过这次不是采用随机算法，因为随机算法没法保证把所有的解都求出。利用回溯法把所有可能的情况都遍历，那么就可以求出所有的解。我们考虑下面的一个实例：
初始时，sudoku[0][0]格子的候选数字为2， 3，5， 6，如图标出，sudoku[4][0]的为2，4，5，其它如图。那么我们在填充sudoku[0][0]的时候不能按照随机来了，因为我们需要把所有的情况遍历的话，需要按一定顺序来，也就是从2开始来，因为一旦某个格子填充了一个候选数字后，其它格子的候选数字会发生变化，假设sudoku[0][0]填充了2，那么与sudoku[0][0]在同一行、同一列、同一块内的格子的候选数字就不能再有2了，sudoku[4][0]、sudoku[6][0]等都应该将原来含有的2给删掉。
我们遍历着填写候选数字，当遇到某个格子的候选数字不存在的时候，我们应该回溯了，我们回到上一格，填写另一个候选数字。比如上图，我们按照这样的顺序来：
sudoku[0][0]填写2，sudoku[4][0]候选为(4,5)，sudoku[6][0]候选为(3, 5)，sudoku[7][0]候选为(4, 5, 6)，sudoku[8][0]候选为(5, 6)；sudoku[4][0]填写4，sudoku[6][0]候选为(3, 5)，sudoku[7][0]候选为(5, 6)，sudoku[8][0]候选为(5, 6)；sudoku[6][0]填写5，sudoku[7][0]候选为(6)，sudoku[8][0]候选为(6)；那么sudoku[7][0]填了6之后sudoku[8][0]就没有候选数字可填了
至于如何遍历所有的情况，我们可以这样来：
把候选数字都按大小从小到大排序，用一个栈记录已经选取过的候选数字在这个序列中的序号，每一次选取候选数字就入栈，每一次回溯就出栈。另外需要注意的是每一次改变格子数字的操作都需要更新候选数字。伪码如下（注意，这只是表达思想，代码在如果按执行顺序来是有误的）：
3: while(true) {
if(candidates[row][col] != NULL) {
//当前格子填写第idx个候选数字, idx = 0,1,2,3...
sudoku[row][col] = candidates[row][col](idx);
//如果所有的格子都填了，那么就把这个解保存起来，然后回溯
if(allBlanked()) {
solutions.add();
backtrace(row, col);
//idx入栈以记录已经填过的候选数字
s.push(idx);
//更新候选数字
updateCandidates();
//填写下一行
next(row, col);
else {//如果没有了候选数字就回到上一格填过的位置
backtrace(row, col);
//回溯到原点就结束
if(s.isEmpty()) {
//获取上一格填写的数字的序号,这次应该填写下一个候选数字了,即序号加1
idx = s.pop() + 1;
1: New game:
12: Solution: 1
22: Solution: 2
32: Solution: 3
42: Solution: 4
52: Solution: 5
1: New game:
12: Solution: 1
22: Solution: 2
32: Solution: 3
42: Solution: 4
52: Solution: 5
62: Solution: 6
72: Solution: 7
82: Solution: 8
1: New game:
12: Solution: 1
22: Solution: 2
32: Solution: 3
45: Solution: 235
55: Solution: 236
65: Solution: 237
Implementations : （代码是大二学期末的算法分析课程实习上写的，纯原创，当时用Qt写过一个界面设计了一个数独游戏，但是出于当时时间紧张没有做得很好，所以这里就不贴了，等以后有空完善好了再在Qt栏目里面贴出来，因为当时的代码存在小漏洞，这个版本修改了那个漏洞，原博文出于我的网易博客，因为今天是10月的最后一天了，再不加一篇博文，首页的那个“恒”就没了 = =！）
Qt游戏的那个截图：
Java源码：
Java测试源码：
@Ggicci 本文属于个人学习笔记，如有错误，希望您能指正！转载请注明出处，谢谢 :) [CSDN博客]
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：70318次
排名：千里之外
原创：24篇
评论：14条
(1)(4)(4)(4)(4)(9)JavaScript遍历求解数独问题的主要思路小结
投稿：goldensun
字体：[ ] 类型：转载 时间：
数独游戏非常流行,其规则就是1到9数字填入9*9宫格并要求每一行、每一列、每一个粗线(小型)宫内的数字不重复,对此我们来看一下JavaScript遍历求解数独问题的主要思路小结
数独游戏，经典的为9×9=81个单元格组成的九宫格，同时也形成了3×3=9个小九宫格，要求在81个小单元格中填入数字1~9，并且数字在每行每列及每个小九宫格中都不能重复。
相关二十格：一个数字只与其所在行列及小九宫格的二十格相关
精心设计了有效性判定函数，最多一次遍历81个小单元格就能做出方案的有效性判定。
同理设计了相关20格判定，一次0~9的循环就完成有效性判定。
用数组模拟堆栈，为搜索提供回溯信息。
利用对象具有map性质，来辅助判断方案的有效性，大大简化了算法。
方案设计与实现
只用了一个二维数组存储数独方案，一个一维数组作堆栈，一个布尔变量作回溯标识。
1.变量定义：
var problem = [
//这是书上提到的难度10.7的题
[8,0,0,0,0,0,0,0,0],
[0,0,3,6,0,0,0,0,0],
[0,7,0,0,9,0,2,0,0],
[0,5,0,0,0,7,0,0,0],
[0,0,0,0,4,5,7,0,0],
[0,0,0,1,0,0,0,3,0],
[0,0,1,0,0,0,0,6,8],
[0,0,8,5,0,0,0,1,0],
[0,9,0,0,0,0,4,0,0]
var stack = [],flag =
2.方案有效性判定：
充分利用了javascript对象的哈希特性，为了方便调试，判定有效时函数的返回值为0，无效时分三种情况，行冲突、列冲突、小九宫格冲突，分别返回1，2，3。前期判定用了它，后来增加了相关二十格判定，在找答案时这个函数就用不上了。
function checkValid(sudo){
let subSudo = {}
//辅助变量，用来判定小九宫格是否冲突
for(let i = 0; i&9; i++){
let row = {}, col = {}
//辅助变量，用来判定行、列是否冲突
for(let j = 0; j&9; j++){
let cur1 = sudo[i][j], cur2 = sudo[j][i]
//一次内循环同时完成行列的判定
if(row[cur1])
//当前元素已经在行中出现，优化掉零的判断，key为0时值为0，不需要额外判断
//返回错误代码
row[cur1] = cur1
//当前元素未在行中出现，存入辅助变量中
if(col[cur2])
//列的判定与行类似，优化掉零的判断，key为0时值为0，不需要额外判断
col[cur2] = cur2;
let key = Math.floor(i/3)+'-'+Math.floor(j/3)
//为不同的小九宫格生成不同的key
if(subSudo[key]){
//小九宫格中已经有元素，优化掉零的判断，key为0时值为0，不需要额外判断
if(subSudo[key][cur1])
//对某一个小九宫格的判定与行类似
subSudo[key][cur1] = cur1
//这是某小九宫格中的第一个元素
subSudo[key] = {}
//为小九宫格新建一个辅助变量，并将第一个元素存入其中
subSudo[key][cur1] = cur1
//程序能运行到这，说明方案有效
3.相关二十格判定
原理同整体判定，亮点在小九宫格的定位上。
function check20Grid(sudo,i,j){
let row = {}, col = {}, subSudo = {}
//辅助变量
for(let k = 0; k & 9; k++){
let cur1 = sudo[i][k], cur2 = sudo[k][j]
//当前元素已经在行中出现，优化掉零的判断，key为0时值为0，不需要额外判断
if(row[cur1])
//返回错误代码
row[cur1] = cur1
//当前元素未在行中出现，存入辅助变量中
//列的判定与行类似，优化掉零的判断，key为0时值为0，不需要额外判断
if(col[cur2])
col[cur2] = cur2;
//转化循环变量到小九宫格的坐标
let key = sudo[Math.floor(i/3)*3 + Math.floor(k/3)][Math.floor(j/3)*3+Math.floor(k%3)]
if(subSudo[key])
//九宫格判定与行类似，优化掉零的判断，key为0时值为0，不需要额外判断
subSudo[key] = key
4.遍历求解
利用元素状态初值为零的元素即为待定的特性，并加上堆栈的辅助，没有再开辟额外的存储空间。
function findAnswer(){
for(let i = 0; i&9; i++){
for(let j = 0; j&9; ){
if(problem[i][j] === 0 || flag){
//当前位置为待定元素的首次处理或回溯到当前位置，两种情况看似不同，其实处理相同，自加1即可
let k = problem[i][j] + 1;
//搜索向下一个合法值迈进
while(k&10){
//循环找到下一个合法值
problem[i][j] =
if(check20Grid(problem,i,j) == 0){
//判定合法，相关二十格判定
stack.push([i,j++])
//存储回溯点，并步进
//当前位置找不到合法值，回溯
problem[i][j] = 0;
//回溯前归零
let rt = stack.pop();
//堆栈中取回溯信息
//无解判断，返回0
//当前位置数字为题目给定
//成功找到一组解
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具人人网 - 抱歉
哦，抱歉，好像看不到了
现在你可以:
看看其它好友写了什么
北京千橡网景科技发展有限公司：
文网文[号··京公网安备号·甲测资字
文化部监督电子邮箱：wlwh@··
文明办网文明上网举报电话： 举报邮箱：&&&&&&&&&&&&数独游戏怎么玩呀_百度知道请问数独生成算法在android平台上试写一个数独游戏.现在问题卡在,如何生成一个数独题目,使其不会变成死题 请了解这方面的算法达人指点一下.谢谢!
回答1：我只写了个解答数独的生成数独 《编程之美》 那本书上的 1.15 章讲了
tearlessness
回答2：没错，编程之美上面有
tearlessness
回答3：应该类似于八皇后问题，可以用搜索法构建