利用python，求解数独_用python解数独

import numpy as np
import time
time1 = time.time()
'''
    整体灵感就是
    1 求出每个数字为0的位置可以填的数，并将其位置和能填的数分别以key和value的方式
      存储到字典里面
    2 将字典里的数据按照所能填写的数据的多少进行排序，先在能填的数少的里面选取一个
      进行填写
    3 将填写的过程记录到列表里面，这个地方暂时想到的就是用列表记录填写过程
    4 更新1、2步，若出现某一步可填写的数据为空，说明之前某一步的选择有问题，回溯回
      去，更换数值，然后回到步骤1
    5 当所有的数都填完后，退出循环
'''
 
 
def nine(data):
    nine_block = np.zeros([3,3,3,3], dtype = int)
    for i in range(3):
        for j in range(3):
            nine_block[i,j] = data[3*i:3*(i+1),3*j:3*(j+1)]
    return nine_block
 
def num_set(data, nine_block):
    pick_set = {}
    for i in range(9):
        for j in range(9):
            if data[i,j] == 0:
                pick_set[str(i)+str(j)] = set(np.array(range(10))) - \
                (set(data[i,:]) | set(data[:,j]) | \
                set(nine_block[i//3,j//3].ravel()))
    return pick_set
 
 
def try_insert(data):    
 
    insert_step = []
    while True:
        
        pick_set = num_set(data, nine(data))
        if len(pick_set) == 0: break
        pick_sort = sorted(pick_set.items(), key = lambda x:len(x[1]))
        item_min = pick_sort[0]
        key = item_min[0]
        value = list(item_min[1])
        insert_step.append((key, value))
        if len(value) != 0:
            data[int(key[0]), int(key[1])] = value[0]
        else:
            insert_step.pop()
            for i in range(len(insert_step)):
                huishuo = insert_step.pop()
                key = huishuo[0]
                insert_num = huishuo[1]
                if len(insert_num) == 1:
                    data[int(key[0]), int(key[1])] = 0
                else:
                    data[int(key[0]), int(key[1])] = insert_num[1]
                    insert_step.append((key, insert_num[1:]))
                    break
    tiem2 = time.time()
    print('\nFinished! using time:', tiem2-time1, 's')
    print(data)    
   
if __name__ == '__main__':
    data =  "0 0 0 0 0 0 0 6 0 \
             0 0 0 0 0 4 7 0 5 \
             5 0 0 0 0 0 1 0 4 \
             1 0 0 0 0 2 4 0 0 \
             0 0 8 0 7 0 0 0 0 \
             0 3 0 6 0 0 0 0 0 \
             2 0 0 0 0 9 0 0 1 \
             0 0 6 0 8 0 0 0 0 \
             0 7 0 3 0 0 0 0 0 "
    data = np.array(data.split(), dtype = int).reshape((9, 9))
    print(data)
    try_insert(data)

别不多说，代码先行，运行结果如下

      用时1.91秒，还算能看，其实很早就想做点什么，但碍于能力有限，一直拖着，没有实践。刚开始考虑用excel实现求解数独来着，奈何同样涉及到VBA，而在下对VBA只是略懂皮毛，只能作罢。

      至于学习Python的过程，其实在很早的时候，就听同窗加挚友洪同学提及过Python，当时第一感觉和帕金森音略同，故而与之戏称帕金森云云，真正开始学习Python其实要追溯到17年12月份，到写此文时也有近6个月的时间，不知不觉，小半年了。进度之缓慢，说来实在惭愧。

      好了，回到正文，其实基本的思想在代码里面也有所提及，下面就着重讲解下各部分代码在干嘛吧！

      numpy这个东西很好用，里面提供了数组的各种花样操作，对于初学者来说，降低了入门难度，故而我很喜欢^_^。而time模块在这里其实只起到了计算程序运行时间的作用，就不再说了。

      首先，定义函数nine(data)，这个函数的主要功能是将9×9的数据，变成3×3的块，于是在事先，就先利用了numpy模块生成了这样的块，这也就是下面这行代码所干的事。

nine_block = np.zeros([3,3,3,3], dtype = int)

紧接着，将原来的数据按块填进已生成的nine_block中，就是两个for循环，就实现了这个需求。

for i in range(3):
        for j in range(3):
            nine_block[i,j] = data[3*i:3*(i+1),3*j:3*(j+1)]

至于这里的赋值为什么是这样来赋值，其实很容易理解，拿所要填的第一块来说，也就是nine_block[0,0]，是不是希望将data里面的前三行前三列数据填过来，这个时候那就是data[0:3, 0:3]; 再看水平方向的第二块，是不是就是data[0:3, 3:6]，以此类推。那么跟nine_block的索引i, j结合起来就不难看出这个赋值表达式意义了。

        接着，定义函数num_set(data, nine_block)，此函数的作用为，将data中所有为0的位置的可填数找到，并存储到一个字典里面，其中这个字典的key为0值的行索引和列索引，这里用str(i)+str(j)实现，而该位置可填的数究竟怎么确定的，其实，这就要回到数独的玩法上了，因为在填数时玩家必须保证该位置所属的行、列以及块里面没有这个数的时候，否则就违反了游戏规则，那么这里的可填数就使用了这个规则，就是在（1 ~ 9）的数字集合删去已经在相关位置出现的数，那么这样就找到了该位置可填的数的集合。在这里主要用到了集合的子、交、并、补概念。

pick_set = {}
for i in range(9):
    for j in range(9):
        if data[i,j] == 0:
            pick_set[str(i)+str(j)] = set(np.array(range(10))) - \
            (set(data[i,:]) | set(data[:,j]) | \
            set(nine_block[i//3,j//3].ravel()))

可能你会注意到在这里的相应的所属块取出来后，可能无法直接用set(nine_block[i//3,j//3])，但我把这个块状的数据ravel()后，就是拉平后，可以使用了，至于内在原因，还在摸索当中。

这个函数的返回值是长这样的^_^

                                                                

比如说'00':{3,4,7,8,9}，这就表明此时在data中位于第1行，第1列的位置，其可填的数为3，4，7，8和9。其他的也是如此。

        最后定义的函数为try_insert(data)，实现了数据的插入，步骤分为两步，即插和改。由于对递归实现的方法不甚理解，所以就不班门弄斧了，这里使用的是利用列表来记录每一次的插入。插入一个值，同时在插入下一个值之前，就更新了我们的可选字典，这样以便快速验证插入数值的正确性。那么究竟怎么判断我首次插入的值是否准确呢，其实这个地方就是深度优先的概念了，就是说，一条路走到黑，直到走不通为止，因为但凡我前面的数填的不对，走到后面就会发现，在某一个位置就会出现没有可填数的情况，但怎么告诉程序说前面填错了呢？思考三分钟...

        这个时候我们的记录插入情况的列表就派上用场了，可以根据插入情况进行回溯，怎么个回溯法呢？简单来说就是由后往前找，在第一个分叉的地方，换另外的数，并把之前走不通的数舍去，下面就一个例子进行说明，假如下面是我的某一次的插入过程

                                                                

在程序里面默认的插入方法是：当有多个选择时，先插入可选数集合中的第1个数。在如上的这个插入过程当中，发现，在进行对索引值为'55'位置的数进行插入时，竟然发现此处没有可插入数，那么，问题来了，必然是前面出错了，可是错误出在哪呢？无从得知，只知道错误出现了，那么就此例而言，错误会出现在索引值为'45', '75', '01'这些可填值只有1个的位置上吗，显然不是，因为可填数只有1个，那我只能填这个了，暂且称之为被动正确（临时想到的），那么这个错误很有可能是出在诸如索引值为'00', '21'这样的可填数不唯一的地方，可是怎么回去呢，思考三分钟...

        一言以蔽之 改，如何改，不卖关子了，就是把'70', '10', '62'这些被动正确的地方数重新变为0，然后在'00'这个位置把插入数不选9，选3，然后往下走，如果选3之后后面走通了，那么皆大欢喜，但是，万一走不通怎么办，如果又走不通，说明不是'00'处的问题，而是问题还在前面，如'21', '40'这样的位置，但如何回溯到更前一步呢？即然在前面情况不变下，'00'处选9走不通，那何不在首次回溯时，就暂时在'00'处的可选值中将9丢弃，这样在'00'处选3的情况下，如果还走不通，那么我们再次进行回溯时，就不会还是找'00'了，而是会找到'21'的位置。如此循环，直到所有的值都填上为止。

        代码就不再贴了，前面可能没有说，在选值进行插入时，我提前将可选集合按照可填数的多少进行了排序，先填可选数少的，这样可以大大提高程序运行效率。^_^