芬蘭數(shù)學家因卡拉花費3個月時間設計出的世界上迄今難度最大的數(shù)獨。數(shù)獨是 9 橫 9 豎共有 81 個格子，同時又分為 9 個九宮格。規(guī)則很簡單：每個空格填入 1~9 任意一個數(shù)字，需要保證每個橫排和豎排以及九宮格內(nèi)無相同數(shù)字。
數(shù)獨
解數(shù)獨是一個可有可無的愛好，知道這個益智游戲，但是不很上心。但是前兩天，由于自己的學生裝了一個 ubuntu 18.04 的系統(tǒng)，上面有一些數(shù)獨游戲，偶然間，讓我看見了，為了更好的顯擺自己的 Python 知識，決定用 Python 寫一個程序，所以就有了下面的文字。
1、將待解的數(shù)獨轉換成 Python 矩陣
m = [
[6, 0, 0, 1, 0, 0, 7, 0, 8],
[0, 0, 0, 8, 0, 0, 2, 0, 0],
[2, 3, 8, 0, 5, 0, 1, 0, 0],
[0, 0, 0, 0, 4, 0, 0, 9, 2],
[0, 0, 4, 3, 0, 8, 6, 0, 0],
[3, 7, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 3, 0, 7, 0, 5, 2, 6],
[0, 0, 2, 0, 0, 4, 0, 0, 0],
[9, 0, 7, 0, 0, 6, 0, 0, 4]
]
就是這么簡單，將待填寫的空白格用 0 來代替。
2、尋找第一個空格位置
def start_pos(m:"數(shù)獨矩陣"):
""" 功能：返回第一個空白格的位置坐標"""
for x in range(9):
for y in range(9):
if m[x][y] == 0:
return x, y
return False, False # 若數(shù)獨已完成，則返回 False, False
找到 Python 矩陣中第一個是 0 的元素的位置坐標。
3、尋找下一個空格位置
def get_next(m:"數(shù)獨矩陣", x:"空白格行數(shù)", y:"空白格列數(shù)"):
""" 功能：獲得下一個空白格在數(shù)獨中的坐標。
"""
for next_y in range(y+1, 9): # 下一個空白格和當前格在一行的情況
if m[x][next_y] == 0:
return x, next_y
for next_x in range(x+1, 9): # 下一個空白格和當前格不在一行的情況
for next_y in range(0, 9):
if m[next_x][next_y] == 0:
return next_x, next_y
return -1, -1 # 若不存在下一個空白格，則返回 -1，-1
找到 Python 矩陣中下一個是 0 的元素的位置坐標。詳細內(nèi)容看注釋。
4、尋找適合當前空格的數(shù)字的集合
def value(m:"數(shù)獨矩陣", x:"空白格行數(shù)", y:"空白格列數(shù)"):
""" 功能：返回符合"每個橫排和豎排以及
九宮格內(nèi)無相同數(shù)字"這個條件的有效值。
"""
i, j = x//3, y//3
grid = [m[i*3+r][j*3+c] for r in range(3) for c in range(3)]
v = set([x for x in range(1,10)]) - set(grid) - set(m[x]) - \
set(list(zip(*m))[y])
return list(v)
每個空格可以填入 1~9 中的任意一個數(shù)字，但要符合規(guī)則：每個空格填入 1~9 任意一個數(shù)字，需要保證每個橫排和豎排以及九宮格內(nèi)無相同數(shù)字。下面的代碼中的 grid 變量，保存的是當前位置所處的九宮格。v 變量是通過集合運算，將 1~9 這個數(shù)字集合中，與行的數(shù)字集合、列的數(shù)字集合以及九宮格的數(shù)字集合重疊的部分去除掉。剩余的部分就是符合條件的數(shù)字的集合。
5、使用遞歸嘗試解數(shù)獨（Sudoku）
def try_sudoku(m:"數(shù)獨矩陣", x:"空白格行數(shù)", y:"空白格列數(shù)"):
""" 功能：試著填寫數(shù)獨 """
for v in value(m, x, y):
m[x][y] = v
next_x, next_y = get_next(m, x, y)
if next_y == -1: # 如果無下一個空白格
return True
else:
end = try_sudoku(m, next_x, next_y) # 遞歸
if end: # 數(shù)獨解完之后，此處的 end 會是 True
return True
m[x][y] = 0 # 在遞歸的過程中，如果數(shù)獨沒有解開，
# 則回溯到上一個空白格
詳細內(nèi)容看注釋。
6、代碼展示
import random
import sys
sys.setrecursionlimit(100000) # 發(fā)現(xiàn)python默認的遞歸深度是很有限的
#（默認是1000），因此當遞歸深度超過999的
# 樣子，就會引發(fā)這樣的一個異常。
def get_next(m:"數(shù)獨矩陣", x:"空白格行數(shù)", y:"空白格列數(shù)"):
""" 功能：獲得下一個空白格在數(shù)獨中的坐標。
"""
for next_y in range(y+1, 9): # 下一個空白格和當前格在一行的情況
if m[x][next_y] == 0:
return x, next_y
for next_x in range(x+1, 9): # 下一個空白格和當前格不在一行的情況
for next_y in range(0, 9):
if m[next_x][next_y] == 0:
return next_x, next_y
return -1, -1 # 若不存在下一個空白格，則返回 -1，-1
def value(m:"數(shù)獨矩陣", x:"空白格行數(shù)", y:"空白格列數(shù)"):
""" 功能：返回符合"每個橫排和豎排以及
九宮格內(nèi)無相同數(shù)字"這個條件的有效值。
"""
i, j = x//3, y//3
grid = [m[i*3+r][j*3+c] for r in range(3) for c in range(3)]
v = set([x for x in range(1,10)]) - set(grid) - set(m[x]) - \
set(list(zip(*m))[y])
return list(v)
def start_pos(m:"數(shù)獨矩陣"):
""" 功能：返回第一個空白格的位置坐標"""
for x in range(9):
for y in range(9):
if m[x][y] == 0:
return x, y
return False, False # 若數(shù)獨已完成，則返回 False, False
def try_sudoku(m:"數(shù)獨矩陣", x:"空白格行數(shù)", y:"空白格列數(shù)"):
""" 功能：試著填寫數(shù)獨 """
for v in value(m, x, y):
m[x][y] = v
next_x, next_y = get_next(m, x, y)
if next_y == -1: # 如果無下一個空白格
return True
else:
end = try_sudoku(m, next_x, next_y) # 遞歸
if end:
return True
m[x][y] = 0 # 在遞歸的過程中，如果數(shù)獨沒有解開，
# 則回溯到上一個空白格
def sudoku(m):
x, y = start_pos(m)
try_sudoku(m, x, y)
print(m)
if __name__ == "__main__":
m = [
[6, 0, 0, 1, 0, 0, 7, 0, 8],
[0, 0, 0, 8, 0, 0, 2, 0, 0],
[2, 3, 8, 0, 5, 0, 1, 0, 0],
[0, 0, 0, 0, 4, 0, 0, 9, 2],
[0, 0, 4, 3, 0, 8, 6, 0, 0],
[3, 7, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 3, 0, 7, 0, 5, 2, 6],
[0, 0, 2, 0, 0, 4, 0, 0, 0],
[9, 0, 7, 0, 0, 6, 0, 0, 4]
]
sudoku(m)
""" 數(shù)獨結果如下：
[
[6, 9, 5, 1, 2, 3, 7, 4, 8],
[7, 4, 1, 8, 6, 9, 2, 5, 3],
[2, 3, 8, 4, 5, 7, 1, 6, 9],
[8, 1, 6, 7, 4, 5, 3, 9, 2],
[5, 2, 4, 3, 9, 8, 6, 7, 1],
[3, 7, 9, 6, 1, 2, 4, 8, 5],
[4, 8, 3, 9, 7, 1, 5, 2, 6],
[1, 6, 2, 5, 8, 4, 9, 3, 7],
[9, 5, 7, 2, 3, 6, 8, 1, 4]
]
"""
視頻請轉 B 站：
