Python 解数独（Sudoku）

闲来有了用python解数独的想法，但由于对复杂些的算法仍是一窍不通，最终算是用简单算法实现了出来。

相关简介：

1.使用的算法很常规，很好理解，有点类似深度优先搜索算法。
2.解常规难度的数独耗时约50~150 ms，但对网上的超难数独尚不能短时间内解出。 - -0
3.输入数独数据要么要input一行行手输，要么在程序中替换default_data数据，总之没有图形界面，输入有点不方便。

后续可能会继续优化性能，也可能改成图形界面~

使用方法：

主要是输入介绍，我设定了两种，游戏开始前可选择方式“1”或“2”：

***Method 1: Modify the default sudoku***
***Method 2: Through input method***

Please select the data input method：1 or 2

• 1：直接修改程序中给出的default_data，数字的修改数字，空处请填0。
  如下所示（default_data的初始数独也可以跑的~）:

default_data = [[1 ,0 ,6 ,2 ,0 ,0 ,0 ,0 ,0 ],
                [0 ,0 ,0 ,4 ,0 ,0 ,8 ,2 ,0 ],
                [2 ,0 ,0 ,0 ,0 ,5 ,0 ,0 ,0 ],
                [0 ,8 ,0 ,0 ,4 ,0 ,0 ,0 ,7 ],
                [0 ,0 ,0 ,6 ,0 ,3 ,0 ,0 ,0 ],
                [5 ,0 ,0 ,0 ,1 ,0 ,0 ,4 ,0 ],
                [0 ,0 ,0 ,9 ,0 ,0 ,0 ,0 ,0 ],
                [0 ,3 ,9 ,0 ,0 ,4 ,0 ,0 ,0 ],
                [0 ,0 ,0 ,0 ,0 ,2 ,9 ,0 ,5 ]]

• 2：input() + for loops，一行行地输入代码，输入一行确定后按回车进入下一行输入，9行全部输入后还可以让你再次确认下，都OK了再开始计算。
  如下所示（每一行的数字键用空格间隔开即可）：

***Method 1: Modify the default sudoku***
***Method 2: Through input method***

Please select the data input method：1 or 2
2
Enter 1th line: 1 0 6 2 0 0 0 0 0
Enter 2th line: 0 0 0 4 0 0 8 2 0
Enter 3th line: 2 0 0 0 0 5 0 0 0
Enter 4th line: 0 8 0 0 4 0 0 0 7
Enter 5th line: 0 0 0 6 0 3 0 0 0
Enter 6th line: 5 0 0 0 1 0 0 4 0
Enter 7th line: 0 0 0 9 0 0 0 0 0
Enter 8th line: 0 3 9 0 0 4 0 0 0
Enter 9th line: 0 0 0 0 0 2 9 0 5

当你输入完毕会打印你输入的Sudoku，然后问你是否确认，输入Y确认后即可得到答案，N则重新输入：

Your data:
 1  0  6  2  0  0  0  0  0 
 0  0  0  4  0  0  8  2  0 
 2  0  0  0  0  5  0  0  0 
 0  8  0  0  4  0  0  0  7 
 0  0  0  6  0  3  0  0  0 
 5  0  0  0  1  0  0  4  0 
 0  0  0  9  0  0  0  0  0 
 0  3  9  0  0  4  0  0  0 
 0  0  0  0  0  2  9  0  5 
Confirm? Y or N

原理介绍

主要函数有两个：

• judge，用于判断数独矩阵中某一处是否允许填入某个数字，这个比较简单

def judge(data, x, y, num): 
    if data[y].count(num) > 0:   #行判断
        #print('error1')
        return False

    for col in range(9):   #列判断
        if data[col][x] == num:
            #print('error2')
            return False

    for a in range(3):   #九宫格判断
        for b in range(3):
            if data[a+3*(y//3)][b+3*(x//3)] == num:
                #print('error3')
                return False
    return True

• fill_num，用于将judge函数允许的数字填入空处，接着填下一个空，再下一个...（没错，这是一个递归过程）...直到某一个空发生judge为False的情况，额，会pass掉；直到所有的空都被填满且judge均为True，则返回填满的data矩阵。
  顺便还要介绍一下 build_data_list函数：用于初始化，为每个空位建立备选数字列表，如下所示：

def build_data_list(data):   
    data_list = []
    for y in range(9):
        for x in range(9):
            if data[y][x] == 0:
                data_list.append([(x, y), [1, 2, 3, 4, 5, 6, 7, 8, 9]])   #列表中有坐标信息以及备选的数字
    return data_list

为每一个空处都建立一个备选列表，而fill_num函数则是在递归所有的空，循环其中的备选列表。备选列表是可以在每一步前被筛选掉一部分，从而提高速度的，不过这一部分工作还没想好怎么做。

fill_num函数代码如下：

def fill_num(data, data_list, start): 
    if start < len(data_list):
        one = data_list[start]
        for num in one[1]:
            if judge(data, one[0][0], one[0][1], num):
                data[one[0][1]][one[0][0]] = num
                tem_data = fill_num(data, data_list, start+1)   #递归部分
                if tem_data != None:
                    return tem_data   #当递归返回值非空时才传给上层
        data[one[0][1]][one[0][0]] = 0   #当for loops结束时需要执行清零操作
    else:
        return data

fill_num函数中有坑：

• 每一处空的循环尝试都能成功，并通向下一处空，直至最后一个空...这种情况当然是最好啦，这种情况下会一层层返回正确的data，不会出啥问题。图示如下：

  
  理想情况

• 但这种猜测式解数独法，总是猜错的情况多。对应的这种情况就是第n阶的猜测judge为True，但却不是答案值，而这种错误往往要继续往下猜很多阶才能体现出来，图解如下，这样就会形成两个坑。

  
  日常情况

• 坑一，当第n+1阶的for loops执行完都没找到可填的数字时，此时的第n+1阶的递归函数也会返回值（只不过这个值为None）。一旦某一阶函数返回了值，其外部的函数依次返回，后续的猜测就终止了，无法找到正确值（正确值非None）。

if tem_data != None:
    return tem_data   #当递归返回值非空时才传给上层

因此增加这部分代码，避免某函数for loops结束，返回值为None时，引起外层函数连续return，中断操作。

• 坑二，解决返回值问题是其一，其二是尽管对返回值设了检查，return有了保障，但是毕竟某一阶或多阶的for loops已经错误执行，导致data被多次错误赋值：

if judge(data, one[0][0], one[0][1], num):   #judge为True就允许赋值
    data[one[0][1]][one[0][0]] = num

解决方案为，一旦for loops能完整执行，表明前面一定填错了，因此要将每一个错误的填数清零：

data[one[0][1]][one[0][0]] = 0   #当for loops结束时需要执行清零操作

解决了这俩坑就没啥大问题了。

文件放在这里了，enjoy yourself~
Sudoku v2

Sudoku v2