摘要:數(shù)獨(dú)的規(guī)則為每個(gè)謎題都由一個(gè)在不同位置給與提示數(shù)字的網(wǎng)格組成。游戲的目的是將空方格填上數(shù)字,使得每一行,每一列以及每一個(gè)宮都沒有重復(fù)的數(shù)字出現(xiàn)。
利用Python來解數(shù)獨(dú)~~~
起因大概是:
自己解數(shù)獨(dú)實(shí)在是太費(fèi)勁了!!!
python版本: 3.5.4
思路很簡單:
將每個(gè)空格可能填入的數(shù)先列舉出來,然后就是深搜來解數(shù)獨(dú)。
數(shù)獨(dú)的規(guī)則為:
每個(gè)謎題都由一個(gè)在不同位置給與提示數(shù)字的9x9網(wǎng)格組成。游戲的目的是將空方格填上數(shù)字,使得每一行,每一列以及每一個(gè)3x3宮都沒有重復(fù)的數(shù)字出現(xiàn)。
</>復(fù)制代碼
# 點(diǎn)類class point():
def __init__(self, x, y):
self.x = x
self.y = y
self.available = []
self.value = 0# 該空格所在行有哪些數(shù)def rowNum(p ,sudoku):
# set用于去重,因?yàn)?不止一個(gè)!
row = set(sudoku[p.y*9: (p.y+1)*9])
row.remove(0)
return row# 該空格所在列有哪些數(shù)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# 該空格所在小九宮有哪些數(shù)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# 初始化,作用為:# 把每個(gè)空格可能的點(diǎn)先列舉出來# 比如空格所在的行和列還有小九宮內(nèi)有數(shù)字1、2、3# 那么空格只能填入4、5、6、7、8、9中的某個(gè)數(shù)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這個(gè)數(shù)
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# 檢驗(yàn)該數(shù)填入空格后是否滿足數(shù)獨(dú)規(guī)則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# 展示數(shù)獨(dú)結(jié)果def showResult(sudoku):
for r in range(9):
for c in range(9):
print("%d " % (sudoku[r*9+c]), end="")
print("")# 深搜來解數(shù)獨(dú)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:
passif __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("數(shù)獨(dú)題目為:/n")
showResult(sudoku)
print("/n數(shù)獨(dú)的解為:/n")
p_first = sudokuList.pop()
solve(p_first, sudoku)
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/119756.html
摘要:數(shù)獨(dú)技巧直觀法候選數(shù)法相關(guān)二十格一個(gè)數(shù)字只與其所在行列及小九宮格的二十格相關(guān)我的思路精心設(shè)計(jì)了有效性判定函數(shù),最多一次遍歷個(gè)小單元格就能做出方案的有效性判定。 看《算法的樂趣》,試著用非遞歸窮舉來解數(shù)獨(dú),看效率如何! 數(shù)獨(dú)規(guī)則 數(shù)獨(dú)游戲,經(jīng)典的為9×9=81個(gè)單元格組成的九宮格,同時(shí)也形成了3×3=9個(gè)小九宮格,要求在81個(gè)小單元格中填入數(shù)字1~9,并且數(shù)字在每行每列及每個(gè)小九宮格中都...
摘要:利用強(qiáng)大的語言制作屬于自己的第一張?jiān)~云。還有一件很有意思的事情,和的中文意思,都是蟒蛇。好,接下來進(jìn)入正題,一步一步實(shí)現(xiàn)我們的第一張?jiān)~云。但是我們?nèi)绻獙χ形倪M(jìn)行分析,還必須要借助中文分詞技術(shù)。 相信很多人在網(wǎng)上,或者是在一些報(bào)告或者ppt上,都看到過類似這種圖片 showImg(https://segmentfault.com/img/bVQRr0?w=1920&h=919); 你可...
摘要:第部分第部分第部分第部分源代碼下載每日前端實(shí)戰(zhàn)系列的全部源代碼請從下載代碼解讀解數(shù)獨(dú)的一項(xiàng)基本功是能迅速判斷一行一列或一個(gè)九宮格中缺少哪幾個(gè)數(shù)字,本項(xiàng)目就是一個(gè)訓(xùn)練判斷九宮格中缺少哪個(gè)數(shù)字的小游戲。 showImg(https://segmentfault.com/img/bVbkNGa?w=400&h=300); 效果預(yù)覽 按下右側(cè)的點(diǎn)擊預(yù)覽按鈕可以在當(dāng)前頁面預(yù)覽,點(diǎn)擊鏈接可以全屏預(yù)...
閱讀 2464·2021-11-19 09:40
閱讀 3589·2021-11-17 17:08
閱讀 3796·2021-09-10 10:50
閱讀 2223·2019-08-27 10:56
閱讀 1948·2019-08-27 10:55
閱讀 2643·2019-08-26 12:14
閱讀 999·2019-08-26 11:58
閱讀 1498·2019-08-26 10:43