閑來有了用python解數(shù)獨的想法，但由于對復雜些的算法仍是一竅不通，最終算是用簡單算法實現(xiàn)了出來。

相關簡介：

1.使用的算法很常規(guī)，很好理解，有點類似深度優(yōu)先搜索算法。
2.解常規(guī)難度的數(shù)獨耗時約50~150 ms，但對網(wǎng)上的超難數(shù)獨尚不能短時間內解出。 - -0
3.輸入數(shù)獨數(shù)據(jù)要么要input一行行手輸，要么在程序中替換default_data數(shù)據(jù)，總之沒有圖形界面，輸入有點不方便。

后續(xù)可能會繼續(xù)優(yōu)化性能，也可能改成圖形界面~

使用方法：

主要是輸入介紹，我設定了兩種，游戲開始前可選擇方式“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，數(shù)字的修改數(shù)字，空處請?zhí)?。
  如下所示（default_data的初始數(shù)獨也可以跑的~）:

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了再開始計算。
  如下所示（每一行的數(shù)字鍵用空格間隔開即可）：

***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

原理介紹

主要函數(shù)有兩個：

• judge，用于判斷數(shù)獨矩陣中某一處是否允許填入某個數(shù)字，這個比較簡單

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函數(shù)允許的數(shù)字填入空處，接著填下一個空，再下一個...（沒錯，這是一個遞歸過程）...直到某一個空發(fā)生judge為False的情況，額，會pass掉；直到所有的空都被填滿且judge均為True，則返回填滿的data矩陣。
  順便還要介紹一下 build_data_list函數(shù)：用于初始化，為每個空位建立備選數(shù)字列表，如下所示：

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]])   #列表中有坐標信息以及備選的數(shù)字
    return data_list

為每一個空處都建立一個備選列表，而fill_num函數(shù)則是在遞歸所有的空，循環(huán)其中的備選列表。備選列表是可以在每一步前被篩選掉一部分，從而提高速度的，不過這一部分工作還沒想好怎么做。

fill_num函數(shù)代碼如下：

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結束時需要執(zhí)行清零操作
    else:
        return data

fill_num函數(shù)中有坑：

• 每一處空的循環(huán)嘗試都能成功，并通向下一處空，直至最后一個空...這種情況當然是最好啦，這種情況下會一層層返回正確的data，不會出啥問題。圖示如下：

  
  
  理想情況

• 但這種猜測式解數(shù)獨法，總是猜錯的情況多。對應的這種情況就是第n階的猜測judge為True，但卻不是答案值，而這種錯誤往往要繼續(xù)往下猜很多階才能體現(xiàn)出來，圖解如下，這樣就會形成兩個坑。

  
  
  日常情況

• 坑一，當?shù)趎+1階的for loops執(zhí)行完都沒找到可填的數(shù)字時，此時的第n+1階的遞歸函數(shù)也會返回值（只不過這個值為None）。一旦某一階函數(shù)返回了值，其外部的函數(shù)依次返回，后續(xù)的猜測就終止了，無法找到正確值（正確值非None）。

if tem_data != None:
    return tem_data   #當遞歸返回值非空時才傳給上層

因此增加這部分代碼，避免某函數(shù)for loops結束，返回值為None時，引起外層函數(shù)連續(xù)return，中斷操作。

• 坑二，解決返回值問題是其一，其二是盡管對返回值設了檢查，return有了保障，但是畢竟某一階或多階的for loops已經(jīng)錯誤執(zhí)行，導致data被多次錯誤賦值：

if judge(data, one[0][0], one[0][1], num):   #judge為True就允許賦值
    data[one[0][1]][one[0][0]] = num

解決方案為，一旦for loops能完整執(zhí)行，表明前面一定填錯了，因此要將每一個錯誤的填數(shù)清零：

data[one[0][1]][one[0][0]] = 0   #當for loops結束時需要執(zhí)行清零操作

解決了這倆坑就沒啥大問題了。

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

Sudoku v2