Sudoku求解器

Sudoku中文叫做数独,是一种在日本很流行的数字谜题游戏。手工解决这种谜题需要用很多逻辑推算,我对这个一直不再行,只会几种最简单的逻辑,而且经常忘记和算错,所以一直想写一个求解程序来满足一下。

前两天用传播与分配法写了一个矩形谜题游戏的求解程序之后,感觉比较爽,所以今天就花了不少时间来做这个Sudoku solver 。这个程序同样用传播分配算法。传播算法就是用逻辑尽量减小每个方块的取值范围。在网上搜索到 Sudoku Solver by Logic这个网站,它试图尽量采用逻辑来解Sudoku,我从中学到了不少解Sudoku的高级逻辑,不过用程序来实现这些逻辑的效率反而不如让程序直接搜索。所以我写的这个求解器,只用最简单的逻辑进行传播计算,其余的就交给分配器搜索了。

由于我不太会用Javascript,所以这个程序是用Python写的,在服务器上运行,由于服务器是旧笔记本电脑(奔2),所以要等2,3秒才能求得答案。


用传播与分配算法解矩形谜题

谜题如下图所示,每个数字N表示一个矩形区域R, R所包含的小方格数正好为N。要求计算出所有数字对应的矩形区域,使得它们之间不互相覆盖,并且正好包含所有的方块。

        8
    
    8
      6
  
            
6
      6
     
    6
     9
   6
            
6
     8
     6
 
   6
     8
    
10
         6
  
   6
    6
  5
   6
     6
       
    6
      4
  

解决这种问题的最简单的办法就是回溯法,按照顺序把每个数字对应的矩形区域计算出来,如果当前计算出来的矩形区域和已经放置的矩形重叠的话,就尝试下一个候选矩形,直到全部区域被填满。题中一共有22个数字,每个数字对应的可能的矩形区域平均也有5,6种,这样下来,回溯法要花很长时间才能找到答案。

本文给出一种快速算法:传播与分配算法,此算法的基本知识,请参照文章:Constraint Programming in Oz

首先我们需要得到所有的数字所对应的所有可能矩形,我们称之为解空间,通过传播与分配算法,逐渐缩小这个解空间的取值范围,直到找到最终解。

解空间我们用英文status来表示,下面的程序计算出问题的初始解空间。

blocks列表是一个3个元素的的组元,(横坐标、纵坐标、此坐标上的数字)。

WIDTH = 12  
HEIGHT = 12
blocks = [
(0, 8, 10),(8, 4, 9),(7, 0, 8),(3, 1, 8),(5, 6, 8),
(7, 7, 8), (8, 9, 5),(11,9, 6),(4, 10,6),(3, 11,6),
(9, 11,4),(9,1, 6),(0, 3, 6),(6, 3, 6),(3, 4, 6),
(11,4, 6),(0, 6, 6),(10,6, 6),(2, 7, 6),(9, 8, 6),
(2, 9, 6),(6, 9, 6)
]

possibleBlock2函数计算出所有包含坐标为(x,y)的方块的,长宽为(w,h)的矩形区域,它返回的是有4个元素的组元,其意义分别为(矩形区域的左上点横坐标, 矩形区域的左上点纵坐标, 矩形区域的宽, 矩形区域的高)。

def possibleBlock2(x, y, w, h):
for i in range(-w+1, 1):
for j in range(-h+1, 1):
if x+i>=0 and y+j>=0 and x+i+w<=WIDTH and y+j+h<=HEIGHT:
yield (x + i, y + j, w, h)

possibleBlock函数计算出坐标为(x,y)的数字c所对应的所有可能的矩形区域。例如

>>> print list(possibleBlock(0, 8, 10))
[(0, 0, 1, 10), (0, 1, 1, 10), (0, 2, 1, 10), (0, 4, 2, 5),
(0, 5, 2, 5), (0, 6, 2, 5), (0, 7, 2, 5), (0, 7, 5, 2),
(0, 8, 5, 2), (0, 8, 10, 1)]
def possibleBlock(x, y, c):
for i in range(1, c+1):
if c%i == 0:
for p in possibleBlock2(x, y, i, c/i):
yield p

makeInitStatus函数通过收集所有的数字对应的所有可能的矩形区域,返回本问题的初始解空间status。status[i]为blocks[i]对应的所有可能的解。

def makeInitStatus(blocks):
status = []
for x, y, b in blocks:
status.append( list(possibleBlock(x,y,b)) )
return status

传播和分配的基本思想是通过传播操作,尽量缩小解空间的取值范围,在无法缩小的情况下,进行解空间的分配操作,也就是把解空间分解成两个子空间,然后分别对其进行传播和分配操作,直到找到解为止。

我们先来看看传播操作。对于本问题,传播操作就是剔除掉所有相互重叠的矩形。具体地说,就是当某个矩形R与某个数字N对应的所有的矩形都重叠的时候,从解空间中删除矩形R,下文称这种矩形为无效矩形。下面是这部分代码的说明。

rectangleOverlap函数判断矩形rect1和矩形rect2是否有重叠部分,有则返回True,无则返回False。

def rectangleOverlap(rect1, rect2):
x1, y1, w1, h1 = rect1
x2, y2, w2, h2 = rect2
if y1 + h1 - 1 < y2: return False
if y1 > y2 + h2 - 1: return False
if x1 + w1 - 1 < x2: return False
if x1 > x2 + w2 - 1: return False
return True

rectangleOverlapAll函数判断矩形rect和矩形列表rectlist中的所有矩形是否都重叠,都重叠时返回True。

def rectangleOverlapAll(rect, rectlist):
for rect1 in rectlist:
if not rectangleOverlap(rect, rect1):
return False
return True

removeOverlapRectangles函数从矩形列表rectlist1中删除掉与举行列表rectlist2中所有矩形重叠的矩形,如果删除了某个矩形的话,返回True,否则返回False。

def removeOverlapRectangles(rectlist1, rectlist2):
flag = False
for i, x in enumerate(rectlist1):
if rectangleOverlapAll(x, rectlist2):
rectlist1[i] = 0
flag = True
while 0 in rectlist1:
rectlist1.remove(0)
return flag

delImpossibleChoice函数完成对解空间status的传播操作,从解空间status中删除掉所有无效矩形,直到找不到更多的无效矩形。tocheck是一个待检查的集合,它的元素为一个2元组元(x, y),表示要删除status[x]中所有与status[y]重叠的矩形。当removeOverlapRectangles返回Ture时,表示status[x]发生了变化,因此需要重新检查(i, x),i为除了x之外的所有下标。当tocheck为空时,则表示无法继续进行传播操作了。此时的解空间的大小将明显的减少。例如本问题的初始解空间中共有个345矩形元素,经过一次传播操作之后剩下156个矩形元素。

def delImpossibleChoice(status):
tocheck = Set()
for i in range(len(status)):
for j in range(len(status)):
if i!=j: tocheck.add((i,j))
while len(tocheck) > 0:
x, y = tocheck.pop()
r = removeOverlapRectangles(status[x], status[y])
if r:
for i in range(len(status)):
if i!=x:
tocheck.add((i,x))

当传播操作无法继续时,进行分配操作,通过分配算法将当前的解空间分解为两个子解空间,然后再递归执行传播分配操作。下面是这部分程序的解释。

divideStatus函数对解空间status进行分配,得到两个子解空间status1和status2。分配的算法有很多种,这里采用的具体算法如下:
当某个数所对应的矩形列表长度为1时表示这个数所对应的矩形已经有解,当长度大于1时表示还多个候选解,找到候选解最少的下标index,然后把这组候选解[x0, x1, x2,...,xn]分为两部分:[x0], [x1, x2, ... , xn]。程序中的status1和status2是分解后的子解空间,显然status1和status2的集合就是status。

def divideStatus(status):
m = 100
index = -1
for i, x in enumerate(status):
if len(x) > 1 and m > len(x):
m = len(x)
index = i
status1 = deepcopy(status)
status2 = deepcopy(status)
status1[index] = [status[index][0]]
status2[index] = status[index][1:]
return status1, status2

isSolvedStatus函数判断status是否是最终解。当解空间status中所有的候选矩形数都为1时,则找到了最终解。

def isSolvedStatus(status):
for x in status:
if len(x)!= 1:
return False
return True

isImpossibleStatus函数判断status是否是无解解空间。 当解空间status中某组候选矩形数为0时,表示此空间无解。

def isImpossibleStatus(status):
for x in status:
if len(x) == 0:
return True
return False

solvePuzzle函数递归调用自己来实现传播分配操作,直到找到解。

def solvePuzzle(status):
delImpossibleChoice(status) #分配操作,尽可能地缩小解空间
if isSolvedStatus(status): #判断解空间是否为最终解
#printSolveStatus(status)
print status
return
if isImpossibleStatus(status): #判断解空间是否无解
return
#对解空间status进行分配操作,得到子解空间status1和status2
status1, status2 = divideStatus(status)
solvePuzzle(status1) #递归调用solvePuzzle搜索解空间status1中的解
solvePuzzle(status2) #递归调用solvePuzzle搜索解空间status2中的解

最后我们来运行一下程序:

>>> status = makeInitStatus(blocks)
>>> solvePuzzle(status)
[[(0, 7, 2, 5)], [(8, 2, 3, 3)], [(0, 0, 8, 1)], [(2, 1, 4, 2)],
[(5, 3, 1, 8)], [(6, 4, 2, 4)], [(8, 7, 1, 5)], [(11, 6, 1, 6)],
[(4, 5, 1, 6)], [(2, 11, 6, 1)], [(9, 10, 2, 2)], [(8, 0, 3, 2)],
[(0, 1, 2, 3)], [(6, 1, 2, 3)], [(2, 3, 3, 2)], [(11, 0, 1, 6)],
[(0, 4, 2, 3)], [(8, 5, 3, 2)], [(2, 5, 2, 3)], [(9, 7, 2,3)],
[(2, 8, 2, 3)], [(6, 8, 2, 3)]]

printSolveStatus函数将解打印成易读的形式:

def printSolveStatus(status):
chars = "abcdefghijklmnopqrstuvwxyz"
board = []
for i in range(HEIGHT):
board.append([" "]*WIDTH)
for cnt, rect in enumerate(status):
x, y, w, h = rect[0]
for i in range(x, x+w):
for j in range(y, y+h):
board[j][i] = chars[cnt]
for line in board:
print "".join(line)

最终的输出结果为:

cccccccclllp
mmddddnnlllp
mmddddnnbbbp
mmoooennbbbp
qqoooeffbbbp
qqssieffrrrp
qqssieffrrrh
aassieffgtth
aauuievvgtth
aauuievvgtth
aauuievvgkkh
aajjjjjjgkkh

在我的电脑上整个计算过程不过2,3秒。我用回溯法解了一下这个题,睡了一觉才等到答案,所以不知道到底花了多长时间。:-)

完整程序下载


Studio添加新内容

建设这个网站的初衷本来是想针对学汉语的日本人做一些关于汉语教学方面的内容。可是自从做了这个博客之后,网站的重心渐渐地偏移到DSP开发技术上。留言板也变成了一个小小的DSP技术论坛了。而汉语教学方面的内容已经好多个月没有更新了。这种状况令老婆十分不满,于是我准备利用这个黄金周,好好为HYRY Studio做些事情。这几天下来,有了不少改进:

  • 留言板可以分版面了,这样便于把讨论语言的和讨论技术的分开。
  • 网页的家族头像放上了海月的近照,以前那张都有一年历史了。
  • 为HYRY Studio设计了一个图标,为俯视的三人手牵手的图案,此图案由老婆创意的,经过几番修改,最终的效果还是挺令人满意的。大家可以在博客页面左侧的【本页博文列表】背景中、或者Studio首页左侧的导航树的背景中看到这个图案,如果你没有看到的话,建议按F5强制浏览器刷新一下。
  • 为HYRY Studio设计了超酷的名片,名片的具体设计将在以后的博文中详细介绍。
  • HYRY Studio的首页改版,老婆说这次改版令她非常满意,以前那个都提不起她更新网页的兴趣。
  • 制作了几个实用的学汉语的小工具: 在线拼音输入法 ,采用javascript直接在网页上输入中文 ;汉字偏旁部首查询 ,通过选择几次鼠标选择找到所查的汉字,并且可以查看汉字的日语解释和例句,并且所有的用户都可以自由地添加新的内容,相当于一个小型的wiki字典。

经过如上修改之后,大大地提高了老婆制作教程的兴趣,今后可能能够保证定期完成新的【汉语语音教科书】了。