产生数独迷题
随着数独解题算—LX的完成，产生一个数独迷题的任务就顺理成章地完成了。当然，基本的思想还是先生成终盘，然后对填好的数独题进行挖洞，每挖一个洞，就要考虑一下挖去这个洞会不会导致迷题将有多个解。假如会，这个洞就是不能挖的。事实上当一个洞被证实挖去之后会导致多解后，这个洞就注定不能被挖了。也就是说，这个算法的复杂度应该是81*O(f(n))，其中f(n)是用于解一个数独的时间复杂度。

《编程之美》里面提供了一种生成终盘的方法，即在数独中间的块（B5）上随机填入1~9，然后利用这个块行列变换到旁边的块（B4跟B6、B2跟B8）上，同样的做法将在B4、B6上填充B1跟B7，B3跟B9，从而得到一个合法的数独终盘。这种方法将可以产生 9! 种数独终盘。前面的文章我们已经讨论过了，总共存在 6.67*10^21 种数独终盘，相比之下 9! 未免也太少了吧？于是我决定另谋思路。

现在我们已经得到了解数独的方法，我的思路是，对角线上的三个块（B1，B4，B7）是可以随便填而不会造成不合法行为的，把这三个块随机填完后，再利用DLX进行求解，就可以得到一个终盘了。虽然我们知道对于同一个初始局面（B1、B4、B7被随机填好），DLX是可以得到很多个解的，但是由于算法本身的确定性，因此产生终盘的顺序也是固定的，也就是说，这种做法下，我们只能得到(9!)^3，大概是 10^14 种数独终盘。我因此产生了一个想法，把算法的结果弄得有点不是那么确定。我们知道，当我们确定性地选了一列拥有最少元素的列后，算法的思路是深搜该列下的每一行，当通过该行最终得到了一个解后，就返回结果了。为了使算法具有不确定性，我决定在选择行的时候，带上一点随机性质：随机选一个行来进行深搜。这样，我们理论上就能得到所有可能的数独了。

接下来便是挖洞。前面我们大概提到了，当我们尝试挖一个洞而该洞使数独迷题拥有多解时，该洞就不能被挖了，无论我们后面挖了哪些格子。因此，每个格子都只最多会被尝试挖一次。这样的话我们可以首先一个[0,81)的随机序列，然后按照该序列的顺序对终盘进行挖洞，直到所有的格子都被挖过，或者未填的空格已经满足要求后算法才停止。如何判断该挖去该洞后会否使数独迷题拥有多个解呢？那就是，选中某个格子后，假设该格中原先的值为i，那么我们就分别用[1,9]中除了i以外的数替换i，再对数独进行求解，如果能得到解，说明挖去该洞会使数独存在不止一个解。算法虽是这么描述，在真正实现的时候还是可以做一定的优化的。不过我通过实验发现，一般最多只能挖去59个洞，也就是说有得到的数独迷题最少有22个提示，看资料说目前为止数独迷题有唯一解的最少的提示可以达到17个，大概在选格子的顺序上是需要一点处理的。

具体实现的时候，我使用了上篇文章最后提到的那个只有30几行的dlx实现版本，原因是这样进行随机选行方便了很多，呵呵。我在代码里面做了大量的注释。不过为了保证copy时不会出现错误，我都用的英语注释。

from itertools import productfrom random import shuffleimport timeitN_Cell = 3N = 9GRIDS = 81def exact_cover( X, Y ):X = {j:set() for j in X}for i, row in Y.items():for j in row:X[j].add(i)return X, Ydef select( X, Y, r ):cols = []for j in Y[r]:for i in X[j]:for k in Y[i]:if k!=j:X[k].remove(i)cols.append(X.pop(j))return colsdef deselect( X, Y, r, cols ):for j in reversed(Y[r]):X[j]=cols.pop()for i in X[j]:for k in Y[i]:if k!=j:X[k].add(i)def solve( X, Y, solution=[], isRandom=False ):if not X:return list(solution)else:c = min(X, key=lambda c:len(X[c]))rows = list(X[c])#shuffling the rows results in picking a row in randomif isRandom: shuffle(rows)for r in rows:solution.append(r)cols = select(X, Y, r)if solve(X, Y, solution):#we don't use yield anymore, #instead, when a solution found, return itreturn solutiondeselect( X, Y, r, cols )solution.pop()#they are contributed mostly by: http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html#helper function #given index of row, colunm and the ans in the corresponding cell#return colunms that should be one in this contextdef get_ones( r, c, n ):b = (r//N_Cell)*N_Cell + (c//N_Cell)ones = [("rc", (r, c)), ("rn", (r, n)),("cn", (c, n)), ("bn", (b, n))]return onesdef puzzle_generator():#identifier for columns are static, we have our index from 0#when("rc",(r,c)) has a one, it means sudoku grid (r,c) has been filled#when("rn",(r,n)) has a one, it means sudoku line r already has a number n#when("cn",(c,n)) has a one, it means sudoku column c already has a number n#when("bn",(b,n)) has a one, it means sudoku block b already has a number nX_init=([("rc", rc) for rc in product(range(N), range(N))]+[("rn", rn) for rn in product(range(N), range(1, N+1))]+[("cn", cn) for cn in product(range(N), range(1, N+1))]+[("bn", bn) for bn in product(range(N), range(1, N+1))])#Y and Y_final records lines (r,c,n) has which columns as one#where Y is for solving the randomly generated puzzle#while Y_final is for recording the final answer,#if there is a Y_final[(r,c,n)], that means grid[r][c]has been filled with nY = dict()Y_final = dict()#puzzle we are going to generate, initially all 0puzzle = [ ([0]*N) for i in range(N) ]for i in range(N_Cell):init = range(1, N+1)#generate a random sequence from 1~9 and fill them one by one to the blocks#lines are added to Y and Y_final in correspondance, prepare for diggin cellsshuffle(init)for j in range(N_Cell):for k in range(N_Cell):r = i*N_Cell+jc = i*N_Cell+kn = init[j*N_Cell+k]puzzle[r][c]=nY[(r,c,n)]=list(get_ones(r,c,n))Y_final[(r,c,n)] = list(get_ones(r,c,n))#other unfilled cells are 0, there are more than one possibilities for them#which means we have Y[(r,c,i)](i=1~9)for j in range(N_Cell):for k in range(2*N_Cell):r = (6+i*N_Cell+j)%Nc = (i*N_Cell+k)%Nfor n in range( 1, N+1 ):Y[(r,c,n)]=list(get_ones(r, c, n))#convert it to a exact_cover problem and solve it#the final answers are added to Y_finalX, Y = exact_cover(X_init, Y)solution = solve(X, Y, isRandom=True)for (r, c, n) in solution:puzzle[r][c]=nY_final[(r,c,n)]=list(get_ones(r, c, n))#begin digging, we have no investigation on how many cells should be digged for a specific difficulty#so here we made it 60 in temporary, that's, we have 21 hints#but running result shows that we can hardly have 60 cells digged successfully, most of the time 50+empty = 60done = 0tries = 0#dig the cells in a random orderseq = range(GRIDS)shuffle(seq)while done<empty and tries<GRIDS:#main idea: try each cell(r,c,n) where cell(r,c) is filled with n#pop (r,c,n) from Y_final, replace it with other (r,c,i)(i!=n)r, c = divmod(seq[tries], N)tries += 1n = puzzle[r][c]for i in range(1, N+1):Y_final[(r,c,i)]=get_ones(r,c,i)Y_final.pop((r,c,n))#this is a new exact_cover problem#we are replace the initial n in cell(r,c) with other i#to see if there is an answer for itX,Y_final=exact_cover(X_init, Y_final)#if not, that means we can't get an answer from it,#we can safely delete the cell, that is, puzzle[r][c]=0if( not solve(X,Y_final) ):puzzle[r][c]=0done += 1#if yes, that means this cell can be filled with other number and #still we get a legal sudoku, the cell can't be deleted#so Y_final[(r,c,i)] should be pop else:for i in range(1,n)+range(n+1, N+1):Y_final.pop((r,c,i))#finally, the initially deleted line, (r,c,n) should be push in Y_final[(r,c,n)]=get_ones(r,c,n)print 'empty:', donereturn puzzleif __name__ == '__main__':puzzle = puzzle_generator()for row in range(len(puzzle)):print puzzle[row]

好了，接下来我要去研究一下pygame了，先把基础界面做出来，再考虑数独的难度、人工解法及提示。come on ~