本文转自：
解数独用的就是深度优先搜索，有几个方面可以优化一下提高速度：
1.把每个空格的可能的点先列举出来，因为深搜是把遍历的值写入sudoku矩阵再判断，如果不列举可能的值，那就只能用0-9遍历，这样效率会降低，如果空格较少的情况下，先把可能的点列举出来会使速度翻倍；
2.每次把可能情况最少的点优先尝试写入值判断，这个我在程序里没有加，因为深搜的每个树节点必须是固定的，这样当退栈返回上一结点的时候才能正确返回，而我加了这个判断最优节点功能的代码中，返回的树节点不是固定的，因为随着数独空格中值的填入，矩阵也发生着变化，每个点的优先级也在同时发生着变化，这样逻辑就乱了，但我觉得还是可以加上的，这里也算一个小遗憾，希望感兴趣的大牛加上这个功能，那速度又是一番提升。
代码如下：
import time
t0=time.time()
class point:
def __init__(self,x,y):
self.available=[]
self.value=0
def rowNum(p,sudoku):
row=set(sudoku[p.y*9:(p.y+1)*9])
row.remove(0)
return row #set type
def colNum(p,sudoku):
length=len(sudoku)
for i in range(p.x,length,9):
col.append(sudoku[i])
col=set(col)
col.remove(0)
return col #set type
def blockNum(p,sudoku):
block_x=p.x//3
block_y=p.y//3
start=block_y*3*9+block_x*3
for i in range(start,start+3):
block.append(sudoku[i])
for i in range(start+9,start+9+3):
block.append(sudoku[i])
for i in range(start+9+9,start+9+9+3):
block.append(sudoku[i])
block=set(block)
block.remove(0)
return block #set type
def initPoint(sudoku):
pointList=[]
length=len(sudoku)
for i in range(length):
if sudoku[i]==0:
p=point(i%9,i//9)
for j in range(1,10):
if j not in rowNum(p,sudoku) and j not in colNum(p,sudoku) and j not in blockNum(p,sudoku):
p.available.append(j)
pointList.append(p)
return pointList
def tryInsert(p,sudoku):
availNum=p.available
for v in availNum:
if check(p,sudoku):
sudoku[p.y*9+p.x]=p.value
if len(pointList)&=0:
t1=time.time()
useTime=t1-t0
showSudoku(sudoku)
print('\nuse Time: %f s'%(useTime))
p2=pointList.pop()
tryInsert(p2,sudoku)
sudoku[p2.y*9+p2.x]=0
sudoku[p.y*9+p.x]=0
p2.value=0
pointList.append(p2)
def check(p,sudoku):
if p.value==0:
print('not assign value to point p!!')
return False
if p.value not in rowNum(p,sudoku) and p.value not in colNum(p,sudoku) and p.value not in blockNum(p,sudoku):
return True
return False
def showSudoku(sudoku):
for j in range(9):
for i in range(9):
print('%d '%(sudoku[j*9+i]),end='')
if __name__=='__main__':
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,
pointList=initPoint(sudoku)
showSudoku(sudoku)
print('\n')
p=pointList.pop()
tryInsert(p,sudoku)
【Python】基于候选数的解数独算法 + 使用wxPython编写程序界面
本文提供了一种基于候选数的解数独算法，并使用wxPython编写了简单的程序界面...
python解数独--世界最难数独2.3秒完成
“芬兰数学家因卡拉，花费3个月时间设计出了世界上迄今难度最大的数独游戏，而且它只有一个答案。因卡拉说只有思考能力最快、头脑最聪明的人才能破解这个游戏。”这是英国《每日邮报》日的一篇报...
计算机视觉
python 解图片数独题
计算机视觉
来源于于一张 视觉库 里的数独图片。 经过一段时间探索 终于识别出数字 并解出数独。转载请注明出处https://...
回溯法 数独问题（sudoku） python
def print_grid(arr):
for i in range(9):
for j in range(9):
# 注意，在py3.x中，prin...
数独解法的Python实现
import itertoolssudoku = [[0,0,0,4,0,8,0,0,0],
[5,2,0,9,0,6,0,4,1],
[7,8,0,2,0,3...
*投诉人联系方式:
*版权证明: 只允许上传png/jpeg/jpg/gif格式的图片,且小于3M
*详细原因:
交 &em&python解数独&/em& 1积分 立即下载 ...
py写数独小 立即下载
上传者: xcz79350 时间:
综合评分: 0 积分/C币:2
&em&python解数独&/em& 立即下载
上传者: qq_ 时间:
使用Python编写程序求解数独游戏答案
解题建议：遇到问题后，最好先手工推导和模拟一下，把思路理清楚，然后再动手写代码。...
Python刷题笔记（1）- 数独判断
虽然脱离了码农行列，但是觉得写代码这个技能，每个人都应该会一点，而且最近突然有兴趣学习起python，恰好朋友提到codewar以打怪练级的形式来刷题熟练技能，于是就去玩了，感觉这种方式确实比较有成就...
没有更多推荐了，本人平时比较喜欢玩数独，但比较难的数独经常一做就是半个多小时。这学期选了一门”计算机视觉”课，课程最后要做一个项目，正好我就想能不能写一个程序，用手机拍个照或者截个图，放进程序里跑一下，自动就把题目识别然后解出来了，and it was so.
先来看一个opencv里自带的数独图片：
程序的最终目的就是将这种图像转化为一个矩阵或者说二维数组，来要告诉计算机在9x9的方格中哪个位置有数字、数字是什么，就像下面的形式：
[[0 0 0 6 0 4 7 0 0]
[7 0 6 0 0 0 0 0 9]
[0 0 0 0 0 5 0 8 0]
[0 7 0 0 2 0 0 9 3]
[8 0 0 0 0 0 0 0 5]
[4 3 0 0 1 0 0 7 0]
[0 5 0 2 0 0 0 0 0]
[3 0 0 0 0 0 2 0 8]
[0 0 2 3 0 1 0 0 0]]
在这个二维数组里，用0表示要填写的数字，用1-9表示识别出来的题目数字。
了解主要任务之后，下面就是具体的步骤了：
图像预处理
这里使用的语言及版本如下，关于开发环境的配置可以参考本人：
版本：3.6.3 （Anaconda 3）
版本：3.3.1
第一篇文章主要讲解图像预处理部分，并给出使用 matplotlib 显示 OpenCV 图像的方法。
图像预处理
首先是使用 cv2.imread() 函数读取原图片，然后使用 cv2.cvtColor() 灰度化，因为颜色信息不重要。之后是使用滤波算法进行降噪处理，因为滤波处理对于识别效果有很大影响。常用的有均值滤波、高斯滤波、中值滤波、双边滤波等，具体使用方法可以参考。本文使用高斯滤波及中值滤波，但是滤波参数不能适用于所有情况的图像， 必须根据图像尺寸和清晰度做调整 。
img_original = cv2.imread('./images/p1.png')
img_gray = cv2.cvtColor(img_original, cv2.COLOR_BGR2GRAY)
img_Blur = cv2.medianBlur(img_gray, 3)
img_Blur = cv2.GaussianBlur(img_Blur, (3, 3), 0)
可以看到，Python 版本的 OpenCV 与 C++ 版本有个很大的区别，就是处理后的图像一般作为函数的返回值（之一），而C++需要将原图像和处理后图像的地址作为参数传入，这是 Python 中函数可以返回多个值的特点决定的。
此图片在预处理阶段要解决的主要问题是亮度不均衡，图像左下角比较暗，如果直接进行二值化效果较差，对滤波后图像取100作为阈值处理得到中间的图像，左下部分图像缺失；若进行自适应阈值操作，可以得到较好的效果，但左下部分线条亦有缺失：
上一位大神的方法，以圆形作为结构化元素进行闭操作，将灰度图像除以闭操作后图像，再进行归一化。
kernel = cv2.getStructuringElement(cv2.MORPH_ELLIPSE, (11, 11))
close = cv2.morphologyEx(img_Blur, cv2.MORPH_CLOSE, kernel)
div = np.float32(img_Blur) / close
img_brightness_adjust = np.uint8(cv2.normalize(div, div, 0, 255, cv2.NORM_MINMAX))
第一句使用cv2.getStructuringElement() 获取结构元素，可以使用椭圆、矩形、十字形三种，这里使用椭圆。第二句使用cv2.morphologyEx() 对原图使用刚才的结构元素进行闭操作。将灰度图像除以闭操作后图像，但要先转换成 float32 类型才能除，/ 运算符相当于调用numpy中的divide函数，即点除，又即每个像素点分别相除，且只保留整数部分。最后将除的结果归一化到 [0, 255] 区间内，并转换回 无符号8位整数（uint8） 类型。
结果如下图，效果拔群：
下一步是二值化，OpenCV中二值化有简单阈值、自适应阈值、Otsu’s二值化等方法，可以参考。简单阈值是一种全局性的阈值，整个图像都和这个阈值比较。而自适应阈值可以看成一种局部性的阈值，通过规定一个区域大小，比较这个点与区域大小里面像素点的平均值（或者其他特征）的大小关系确定这个像素点是属于黑或者白。这里使用自适应阈值方法，代码如下：
img_thresh = cv2.adaptiveThreshold(img_brightness_adjust, 255,
cv2.ADAPTIVE_THRESH_GAUSSIAN_C,
cv2.THRESH_BINARY_INV, 11, 7)
使用 cv2.adaptiveThreshold() 函数， 其中 cv2.ADAPTIVE_THRESH_GAUSSIAN_C 代表在小区域内阈值选取为加权和，以高斯分布确定权重。cv2.THRESH_BINARY_INV 代表二值化的结果取反，为下一步形态学处理做准备。
使用 matplotlib 显示 OpenCV 图像
Matplotlib是Python中最常用的可视化工具之一，可以非常方便地创建海量类型地2D图表和一些基本的3D图表。也可以方便地显示图像。
众所周知，OpenCV 中彩色图像的像素是以 Bule Green Red 为顺序的，也就是BGR，而普通的图像则是采用RGB顺序，因此要在其他地方（如Qt、matplotlib 中）使用 OpenCV 的彩色图像，就必须转换格式。
我将使用 matplotlib 显示 OpenCV 图像的功能写成了一个函数：
def plotImg(img, title=""):
if img.ndim == 3:
b, g, r = cv2.split(img)
img = cv2.merge([r, g, b])
plt.imshow(img), plt.axis("off")
plt.imshow(img, cmap='gray'), plt.axis("off")
plt.title(title)
plt.show()
这里先判断输入图像是不是3维，即彩色图，是的话进行转换，不是的话作为灰度图显示。转换代码中分割再重新组合的方法，还可以使用 img = cv2.cvtColor(img, cv2.COLOR_BGR2RGB) 。注意如果灰度图不加 cmap='gray' 这个参数，会显示为“热度图”。
当然不要忘了开头加上：
import cv2
from matplotlib import pyplot as plt
matplotlib 还可以像 MATLAB 里一样方便的显示多个图像，例如这里并列显示两幅图像：
def plotImgs(img1, img2):
if img1.ndim == 3:
b, g, r = cv2.split(img1)
img1 = cv2.merge([r, g, b])
plt.subplot(121), plt.imshow(img1), plt.axis("off")
plt.subplot(121), plt.imshow(img1, cmap='gray'), plt.axis("off")
if img2.ndim == 3:
b, g, r = cv2.split(img2)
img2 = cv2.merge([r, g, b])
plt.subplot(122), plt.imshow(img2), plt.axis("off")
plt.subplot(122), plt.imshow(img2, cmap='gray'), plt.axis("off")
plt.show()
其中 plt.subplot(121) 就代表一行两列图像中的第一个。
编写计算机视觉程序时可以使用上述函数将中间过程图像显示出来，方便观察与调试。例如：
OpenCV实践之路——opencv玩数独之二九宫格小方格的提取和数字的提取
在之前的博文OpenCV实践之路——opencv玩数独之一九宫格轮廓提取与透视变换中，已经实现了九宫格最外围矩形轮廓的提取，并利用透视变换把矩形摆正。今天接着上一篇的内容，在摆正后的矩形中检测并提取出...
【图像处理】利用python和opencv解数独
利用python解数独题目。不同的是我的矩阵是用openCV识别出的，不是手工打上去的哦。...
计算机视觉
python 解图片数独题
计算机视觉
来源于于一张 视觉库 里的数独图片。 经过一段时间探索 终于识别出数字 并解出数独。转载请注明出处https://...
python中plt.imshow（img）显示不了图片
http://blog.csdn.net/hjxu2016/article/details/
[python] view
plain cop...
Python 基础 —— pylab
import pylab
pylab.subplot(1, 3, 1); pylab.axis('off'); pylab.imshow(img)
pylab.gray()
pylab.subplot...
OpenCV玩九宫格数独（三）：九宫格生成与数独求解前言在此之前，OpenCV玩九宫格数独（一）和（二）分别介绍了如何从九宫格图片中提取出已知数字和如何用knn训练数字识别模型。在这些前期工作都已经完...
def print_grid(arr):
for i in range(9):
for j in range(9):
# 注意，在py3.x中，prin...
用OPENCV视觉解数独
看到增强视觉网站上介绍老外用视觉解SUDOKU(http://www.cvchina.info//video-sudoku-solv...
本文部分参考自如下链接：Sudoku-recognizer。前几天发现了这个网页，觉得挺好玩的，就想自己实现一下。本以为只是把代码从Python转换到C++是一件很简单的事情，经过这几天的努力发现是自...
【Python+OpenCV】图片局部区域像素值处理（改进版）-一种特征提取方法
上个版本的代码虽然实现了我需要的功能，但还是走了很多弯路，我意识到图片本就是数组形式，对于8位灰度图，通道数为1,它就是个二位数组，这样就没有必要再设置ROI区域，复制出来这块区域再循环提取像素存入数...
没有更多推荐了，昨晚心血来潮在leetcode上pick one了一道算法题
https://leetcode.com/problems/sudoku-solver/
解决代码如下：
class Solution(object):
def solveSudoku(self, board):
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
def check(i, j, value):
for item in board[i]:
if item == value:
return False
for item in board:
if item[j] == value:
return False
col, row = i/3*3, j/3*3
array = board[col][row:row+3] + board[col+1][row:row+3] + board[col+2][row:row+3]
for item in array:
if item == value:
return False
return True
def get_next(i, j):
for row in range(j+1, 9):
if board[i][row] == ".":
return i, row
for col in range(i+1, 9):
for row in range(9):
if board[col][row] == ".":
return col, row
return -1, -1
def try_num(i, j):
if board[i][j] == ".":
for num in range(1, 10):
if check(i, j, str(num)):
board[i][j] = str(num)
next_i, next_j = get_next(i, j)
if next_i == -1:
return True
end = try_num(next_i, next_j)
if not end:
board[i][j] = "."
return True
if board[0][0] == ".":
try_num(0, 0)
i, j = get_next(0, 0)
try_num(i, j)
主要使用回溯递归的方法，先定义一个判断函数和一个获得下一个位置的函数，使结构清晰一些。
然后对可选i,j进行1~9遍历，如果遍历成功，获得next_i, next_j进行下一轮遍历，如果失败则重置为"."
思路还是挺好理解的，代码beat了60%，不知道为什么这个题设为hard了，以前设计过数独的题，这次解数独题也不是什么难事了。
突然想起来test case给的是
["..9748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.."]
实际给的是
[['.', '.', '9', '7', '4', '8', '.', '.', '.'], ['7', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '2', '.', '1', '.', '9', '.', '.', '.'], ['.', '.', '7', '.', '.', '.', '2', '4', '.'], ['.', '6', '4', '.', '1', '.', '5', '9', '.'], ['.', '9', '8', '.', '.', '.', '3', '.', '.'], ['.', '.', '.', '8', '.', '3', '.', '2', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '6'], ['.', '.', '.', '2', '7', '5', '9', '.', '.']]
自己测试的时候别弄混了
阅读(...) 评论()编写一个程序，通过已填充的空格来解决数独问题。一个数独的解法需遵循如下规则：数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。空白格用 '.' 表示。一个数独。答案被标成红色。Note:给定的数独序列只包含数字 1-9 和字符 '.' 。你可以假设给定的数独只有唯一解。给定数独永远是 9x9 形式的。思路：通过暴力搜索，每次确定往一个位置填入数据，填完后继续往下一个位置用递归的方式填，直到所有递归函数返回true，结果才为true。整体分为主函数，递归函数，判断位置是否有效函数。整体思路与八皇后相似，通过在循环中递归的手段不断回溯尝试可能的值。具体表现为我们代码里的for k in '', 这句for循环搭配我们在if里的递归起的效果是：我把目前这个位置填‘1’，电脑你负责帮我算我这里填‘1’能不能解，换言之，电脑你要尝试后面所有待填位置的所有解来告诉我这里填‘1’ok不ok。如果不行，好，那我换‘2’，同样，电脑你需要帮我算后面所有待填位置所有组合加上我在这个位置填的‘2’能不能构成一组解，也即我这里填‘2’到底解不解的了。代码及超详细解释：class Solution(object):
def isValue(self,board,x,y):
#检查填入的坐标是否与行中已有元素相等
for i in range(9):
if i != x and board[i][y] == board[x][y]:
return False
#检查行是否符合
for j in range(9):
if j != y and board[x][j] == board[x][y]:
return False
#检查每个正方形是否符合
#以下代码教会了我们如何遍历3*3方块
m = 3*(x // 3);n = 3*(y // 3)
for i in range(3):
for j in range(3):
if (i + m != x or j + n != y) and board[i + m][j + n] == board[x][y]:
return False
return True
def dfs(self,board):
#遍历每一个坐标
for i in range(9):
for j in range(9):
#找board里的需要填入的位置
if board[i][j] == '.':
#从可选之间选一个
for k in '':
board[i][j] = k
#在if的时候调用递归
#如果这个递归可以返回true并且当前填入的数字也没毛病
#则证明我们解完了数独
if self.isValue(board,i,j) and self.dfs(board):
return True
#到这个位置说明填入的数不太行，所以把它先空着。
board[i][j] = '.'
#进行完当前可选的所有数字都不行，说明上一次决策有问题，返回false
return False
#所有'.'都填满，并且没毛病，返回true
return True
def solveSudoku(self, board):
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
self.dfs(board)
LeetCode37. 解数独
题目分析：本题属于深度遍历DFS的一个经典例子。按照从左往右，从上到下的顺序依次填充空格，用‘1’~‘9’之间的数进行试探，若发现填充的数不满足三条规则中的任意一条，就换一个数进行填充，若都不行，则回...
Vaild Soduku(有效的数独） python3
最简代码(单次循环)
class Solution:
def isValidSudoku(self, board):
:type board: ...
leetcode ----有效的数独(python)
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x...
【无聊刷题】leetCode之解数独
题意：解数独，空缺的方格用.表示。
解法：就是典型的回溯法，用row[i][j],column[i][j],grid[i][j]表示i行，i列，i格j是否用。用flag表示当前是否有解。若有解，则不...
leetcode 36. 有效的数独 (python)
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x...
有效的数独判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分...
原题网址：点击打开题目链接判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在...
import numpy as np
import time
time1 = time.time()
整体灵感就是
1 求出每个数字为0的位置可以填的数，并将其位置和能填的数分...
典型DFS/递归/回溯/深搜题。对于DFS，说白了
1） 什么时候返回？在本题中，1.当x&8或y&8 表示已经遍历完所有的格子，因此成功完成，返回true。2.当下一个搜索（子搜索）返回true，说...
题目：leetcode--37. 解数独链接：https://leetcode-cn.com/problems/sudoku-solver/description/解数独，初始残局用 “ . ”表示空...
没有更多推荐了，python学习笔记-利用回溯法求解数独问题
数独游戏最近很流行，报纸上经常会有一些题目。有空的时候我也会去做做，但是实在太耗脑子，所以干脆试着写个程序来解数独问题。
我平时做数独题目的时候，基本思路是这样的：先对每个格子，列出每个格子中当前可以放的数字(候选数)。然后，找出其中候选数最少的那个格子，在该格子中
依次放入每个候选数，然后继续判断其他格子。在题目比较难的时候，这样做真的很费脑子，但是，让计算机来做这个，应该是一件轻而易举的事情。所以，我们这
个程序也将采用这个算法：
1. 建立堆栈，将题目作为初始值，压入堆栈
2. 若堆栈不为空，则不断循环：
&&&&&&&&&&&&&&&&&&&&
a) 从堆栈中取出一个当前解，遍历所有格子
&&&&&&&&&&&&&&&&&&&&&&&&&&&
i.若当前格子已有数字，则跳过
&&&&&&&&&&&&&&&&&&&&&&&&&&&
ii.若当前格子暂未放置数字，则计算当前格可以放置的候选数列表
&&&&&&&&&&&&&&&&&&&&&&&&&&&
iii.若当前格子候选数个数最少，则保存当前位置及候选数信息
&&&&&&&&&&&&&&&&&&&&&&&&&&&
iv.若某一格子候选数为空，则直接跳出遍历过程，重新从堆栈中取新的临时解进行计算
&&&&&&&&&&&&&&&&&&&&&&&&&&&
v. 若所有格子都已经存在数字，则表示该解即为最终解，直接跳出循环，返回该解
&&&&&&&&&&&&&&&&&&&&
b) 遍历完成后，已获取最少候选数的格子位置及候选数。对该格子，依次放入候选数，并作为新的临时解放入堆栈
下面举个简单示例 ：
第一步，可以判断，在右下角这个9宫格中有四个数字，因此该区域最多候选个数只有5个，列出候选数后，发现第8行第7列只有两个，因此取该格进行下一步计算
先取候选数9，发现上一个格子中候选数只有2个(3,5)，取该格继续计算
以此类推，不断重复这个过程，即可得到结果：
下面是python的源代码：
#!/usr/bin/python
# -*- coding:utf-8 -*-
import string
import copy
import time
#从文件中读取数独问题，每题之间用";"分隔,各数字之间用空格分隔
def read_problem():
inputFile=file('Sudoku_input.txt','r')
rtnList=[]
lProblem=[]
line=inputFile.readline()
line=line.strip()
&&& if len(line)
line==';':
rtnList.append(copy.deepcopy(lProblem))
lProblem=[]
rowList=line.split(' ')
numberList=[]
&&& for number
in rowList:
number=int(number)
numberList.append(number)
lProblem.append(numberList)
&&& return
#数独求解程序
# lProblem:数独问题，由一个二维数组表示
# logFile:
日志文件，将求解结果输出到这个文件中&&&
def sudoku_solver(lProblem,logFile):
lSolverStack=[lProblem]
若堆栈不为空，则循环
len(lSolverStack)&0:
lCurrSolution=lSolverStack.pop()
count=count+1
logFile.write("%d" % count + '\n')
&&& for row in
lCurrSolution:
outLine=''
&&& for number
outLine=outLine + "%d" % number +' '
logFile.write(outLine+'\n')
logFile.write("---------------------------\n")
isResult=True
#用于存放当前最少候选数列表
lMinAvailableNumber=range(1,10)
#当前最少候选数所在位置
lMinAvailableNumberX=0
lMinAvailableNumberY=0
&&& for idx in
range(81):
lCurrSolution[i][j]==0:
isResult=False
#计算当前位置可以放置的数字列表
lCurrAvailableNumber=range(1,10)
#如果同一行中存在相同元素，则排除
&&& for x in
lCurrAvailableNumber.count(lCurrSolution[i][x])&0:
lCurrAvailableNumber.remove(lCurrSolution[i][x])
#如果同一列中存在相同元素，则排除
&&& for y in
lCurrAvailableNumber.count(lCurrSolution[y][j])&0:
lCurrAvailableNumber.remove(lCurrSolution[y][j])
#如果当前位置所在的小九宫格中存在相同元素，则排除
&&& for x in
range(i/3*3,i/3*3+3):
&&& for y in
range(j/3*3,j/3*3+3):
lCurrAvailableNumber.count(lCurrSolution[x][y])&0:
lCurrAvailableNumber.remove(lCurrSolution[x][y])
#如果当前单元格中可选数字个数最少，则保留&&&
len(lCurrAvailableNumber)&len(lMinAvailableNumber):
lMinAvailableNumber=copy.deepcopy(lCurrAvailableNumber)
lMinAvailableNumberX=i
lMinAvailableNumberY=j
len(lMinAvailableNumber)==0:
#若当前位置存在可选数字，则将当前位置的所有可选数字，依次作为临时解，并存入堆栈
len(lMinAvailableNumber)&0:
&&& for number
in lMinAvailableNumber:
lNewSolution=copy.deepcopy(lCurrSolution)
lNewSolution[lMinAvailableNumberX][lMinAvailableNumberY]=number
lSolverStack.append(lNewSolution)&&&
&&& return
lCurrSolution
&&& return
if __name__=='__main__':
resultFile=open("Sudoku_output.txt",'w')
lProblemList=read_problem()
&&& print "Start
solving.."
&&& for lProblem
in lProblemList:
count=count+1
resultFile.write("Solving Problem:"+"%d" % count + ":" +
logFile=open("Problem_"+"%d" % count+".log","w")
startTime=time.time()
lResult=sudoku_solver(lProblem,logFile)
logFile.close()
endTime=time.time()
"& Problem " + "%d" % count + ": finished! Time
consuming: " + "%.4f" % (endTime-startTime) + " Seconds"
len(lResult)==0:
resultFile.write("No Answer...\n")
&&& for row in
outLine=''
&&& for number
outLine=outLine + "%d" % number +' '
resultFile.write(outLine+"\n")
resultFile.write("--------------------------------\n")
resultFile.close()
输入文件：
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
0 9 0 6 0 0 7 0 1
2 0 0 0 0 3 0 8 4
7 0 3 0 0 0 0 0 0
0 3 0 0 6 1 0 0 0
6 0 0 0 0 0 0 0 8
0 0 0 9 4 0 0 7 0
0 0 0 0 0 0 5 0 2
1 5 0 3 0 0 0 0 9
9 0 6 0 0 2 0 1 0
输出结果：
Solving Problem:1:
8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2
--------------------------------
Solving Problem:2:
4 9 8 6 2 5 7 3 1
2 6 5 7 1 3 9 8 4
7 1 3 8 9 4 2 5 6
8 3 7 2 6 1 4 9 5
6 4 9 5 3 7 1 2 8
5 2 1 9 4 8 6 7 3
3 7 4 1 8 9 5 6 2
1 5 2 3 7 6 8 4 9
9 8 6 4 5 2 3 1 7
--------------------------------
求解第一个问题，迭代了5573次，用了 4.5920秒
第二个问题，迭代了54次，用了 0.0310秒
总结一下，一开始我有点偷懒，在计算过程中，没有每次选取最少候选数的那个格子去计算，导致计算量急剧增大，第一个题目要跑很久，看来算法还是很重要的。下一步想尝试去把程序增强一下，让程序能够自己出数独的题目。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。