前言
利用Python來解數獨~~~
起因大概是：
自己解數獨實在是太費勁了！！！
代碼效果展示
所需工具
python版本： 3.5.4
主要思路
思路很簡單：
將每個空格可能填入的數先列舉出來，然后就是深搜來解數獨，
數獨的規則為：
每個謎題都由一個在不同位置給與提示數字的9x9網格組成，游戲的目的是將空方格填上數字，使得每一行，每一列以及每一個3x3宮都沒有重復的數字出現，
代碼實作
# 點類
class point():
def __init__(self, x, y):
self.x = x
self.y = y
self.available = []
self.value = 0
# 該空格所在行有哪些數
def rowNum(p ,sudoku):
# set用于去重，因為0不止一個！
row = set(sudoku[p.y*9: (p.y+1)*9])
row.remove(0)
return row
# 該空格所在列有哪些數
def colNum(p, sudoku):
col = []
length = len(sudoku)
for j in range(p.x, length, 9):
col.append(sudoku[j])
col = set(col)
col.remove(0)
return col
# 該空格所在小九宮有哪些數
def blockNum(p, sudoku):
block_x = p.x//3
block_y = p.y//3
block = []
start_point = block_y*3*9 + block_x*3
for j in range(start_point, start_point+3):
block.append(sudoku[j])
for j in range(start_point+9, start_point+9+3):
block.append(sudoku[j])
for j in range(start_point+9+9, start_point+9+9+3):
block.append(sudoku[j])
block = set(block)
block.remove(0)
return block
# 初始化，作用為：
# 把每個空格可能的點先列舉出來
# 比如空格所在的行和列還有小九宮內有數字1、2、3
# 那么空格只能填入4、5、6、7、8、9中的某個數
def initialize(sudoku):
sudokuList = []
length = len(sudoku)
for index in range(length):
# 找到需要填入的單元，即空格
if sudoku[index] == 0:
p = point(index%9, index//9)
for i in range(1, 10):
# 如果行、列、小九宮中均沒有i這個數
if (i not in rowNum(p, sudoku)) and (i not in colNum(p, sudoku)) and (i not in blockNum(p, sudoku)):
p.available.append(i)
sudokuList.append(p)
return sudokuList
# 檢驗該數填入空格后是否滿足數獨規則
def check(p, sudoku):
if p.value == 0:
return False
if (p.value not in rowNum(p, sudoku)) and (p.value not in colNum(p, sudoku)) and (p.value not in blockNum(p, sudoku)):
return True
else:
return False
# 展示數獨結果
def showResult(sudoku):
for r in range(9):
for c in range(9):
print('%d ' % (sudoku[r*9+c]), end='')
print('')
# 深搜來解數獨
def solve(p, sudoku):
available_Num = p.available
for ava in available_Num:
p.value = ava
if check(p, sudoku):
sudoku[p.y*9+p.x] = p.value
if len(sudokuList) < 1:
showResult(sudoku)
exit()
p_next = sudokuList.pop()
solve(p_next, sudoku)
sudoku[p_next.y*9+p_next.x] = 0
sudoku[p.y*9+p.x] = 0
p_next.value = 0
sudokuList.append(p_next)
else:
pass
if __name__ == '__main__':
# 0代表需要填入的單元，即空格
sudoku = [
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 9, 3, 6, 2, 8, 1, 4, 0,
0, 6, 0, 0, 0, 0, 0, 5, 0,
0, 3, 0, 0, 1, 0, 0, 9, 0,
0, 5, 0, 8, 0, 2, 0, 7, 0,
0, 4, 0, 0, 7, 0, 0, 6, 0,
0, 8, 0, 0, 0, 0, 0, 3, 0,
0, 1, 7, 5, 9, 3, 4, 2, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
]
sudokuList = initialize(sudoku)
print('數獨題目為：\n')
showResult(sudoku)
print('\n數獨的解為：\n')
p_first = sudokuList.pop()
solve(p_first, sudoku)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298930.html
標籤：其他