数独解题程序的python实现_使用Python编写程序求解数独游戏答案
原標(biāo)題:使用Python編寫程序求解數(shù)獨游戲答案
問題描述:數(shù)獨盤面是個九宮,每一宮又分為九個小格。在這八十一格中給出一定的已知數(shù)字和解題條件,利用邏輯和推理,在其他的空格上填入1-9的數(shù)字。使1-9每個數(shù)字在每一行、每一列和每一宮中都只出現(xiàn)一次,所以又稱“九宮格”。
解題建議:遇到問題后,最好先手工推導(dǎo)和模擬一下,把思路理清楚,然后再動手寫代碼。
參考代碼:
importrandom
definit():
# 初始狀態(tài),每個格內(nèi)都是1-9之間的數(shù)字
grids = {(r, c):list(range(1,10))
forr inrange(9) forc inrange(9)}
# 根據(jù)文件中的位置和數(shù)字設(shè)置數(shù)獨游戲初始狀態(tài)
withopen('values.txt') asfp:
forline infp:
line = line.strip()
ifline =='0':
break
row, col, value = map(int, line.split(','))
grids[(row,col)] = value
returngrids
defeachGrid(grids, row, col, value):
tempValue = grids[(row,col)]
# 刪除不可能的數(shù)字
ifisinstance(tempValue, list):
ifvalue intempValue:
tempValue.remove(value)
# 如果格內(nèi)只有一個數(shù)字,就拿出來填充
iflen(tempValue) == 1:
grids[(row,col)] = tempValue[0]
defsolve(oldGrids):
grids = oldGrids.copy()
forr inrange(9):
forc inrange(9):
value = grids[(r,c)]
ifisinstance(value, int):
# 處理同一列
forrr inrange(9):
eachGrid(grids, rr, c, value)
# 處理同一行
forcc inrange(9):
eachGrid(grids, r, cc, value)
# 處理小九宮格內(nèi)的數(shù)字
rowStart = r//3 * 3
colStart = c//3 * 3
forrr inrange(rowStart, rowStart+3):
forcc inrange(colStart, colStart+3):
eachGrid(grids, rr, cc, value)
elifisinstance(value, list) andlen(value)==1:
# 當(dāng)前格內(nèi)只有一個數(shù)了,拿出來填充
grids[(r,c)] = value[0]
returngrids
defoutput(grids):
'''輸出grids中的內(nèi)容'''
forrow inrange(9):
forcol inrange(9):
value = grids[(row,col)]
ifisinstance(value, int):
print(grids[(row,col)], end=' ')
else:
print(' ', end=' ')
print()
defcheck(grids):
'''檢查grids是否滿足數(shù)獨游戲要求'''
forrc inrange(9):
row = {grids[(rc,c)] forc inrange(9)}
iflen(row) != 9:
return False
col = {grids[(r,rc)] forr inrange(9)}
iflen(col) != 9:
return False
forrow inrange(0,9,3):
forcol inrange(0,9,3):
value = {grids[(r,c)]
forr inrange(row,row+3)
forc inrange(col,col+3)}
iflen(value) != 9:
return False
return True
defmain(oldGrids):
grids = oldGrids.copy()
steps = 0
while True:
steps += 1
grids = solve(grids)
ifsteps > 20:
try:
position = [(r,c)
forr inrange(9) forc inrange(9)
ifisinstance(grids[(r,c)],list)][0]
grids[position] = random.choice(grids[position])
except:
grids = oldGrids.copy()
steps = 0
continue
ifall({isinstance(grids[(r,c)], int)
forr inrange(9) forc inrange(9)}):
ifcheck(grids):
returngrids
else:
# 當(dāng)前選擇無效,恢復(fù)原狀,選擇下一個
grids = oldGrids.copy()
steps = 0
grids = init()
output(grids)
result = main(grids)
print('='*30)
output(result)
print(check(result))
代碼中使用的文本文件values.txt中內(nèi)容格式,以第一行為例,0,2,9表示第0行第2列的初始數(shù)字為9:
運行結(jié)果一:
運行結(jié)果二:
運行結(jié)果三:
運行結(jié)果四:
------------我是分割線-------------
新書《Python程序設(shè)計開發(fā)寶典》封面與目錄,已在天貓(清華大學(xué)出版社官方旗艦店)、亞馬遜、當(dāng)當(dāng)、京東、互動出版網(wǎng)等各大網(wǎng)店全面上架。
第1章 管中窺豹:Python概述 14
1.1 Python是這樣一種語言 14
1.2 Python版本之爭 14
1.3 Python編程規(guī)范與代碼優(yōu)化建議 15
1.4 Python虛擬開發(fā)環(huán)境的搭建 17
1.5 Eclipse+PyDev環(huán)境搭建和使用 17
1.6 安裝擴(kuò)展庫的幾種方法 19
1.7 標(biāo)準(zhǔn)庫與擴(kuò)展庫中對象的導(dǎo)入與使用 20
1.7.1 import 模塊名 [as 別名] 20
1.7.2 from 模塊名 import 對象名[ as 別名] 21
1.7.3 from 模塊名 import * 21
1.7.4 模塊導(dǎo)入時的搜索路徑 22
1.8 編寫與發(fā)布自己的包 23
1.9 Python程序偽編譯與打包 25
1.10 從命令行參數(shù)和配置文件獲取信息 27
第2章 萬丈高樓平地起:運算符、表達(dá)式與內(nèi)置對象 29
2.1 Python常用內(nèi)置對象 29
2.1.1 常量與變量 30
2.1.2 數(shù)字 31
2.1.3 字符串 34
2.1.4 列表、元組、字典、集合 35
2.2 Python運算符與表達(dá)式 37
2.2.1 算術(shù)運算符 38
2.2.2 關(guān)系運算符 39
2.2.3 成員測試運算符in與同一性測試運算符is 40
2.2.4 位運算符與集合運算符 41
2.2.5 邏輯運算符 41
2.2.6 矩陣乘法運算符@ 42
2.2.7 補(bǔ)充說明 42
2.3 Python關(guān)鍵字簡要說明 43
2.4 Python常用內(nèi)置函數(shù)用法精要 44
2.4.1 類型轉(zhuǎn)換與類型判斷 47
2.4.2 最值與求和 51
2.4.3 基本輸入輸出 52
2.4.4 排序與逆序 55
2.4.5 枚舉與迭代 56
2.4.6 map()、reduce()、filter() 57
2.4.7 range() 61
2.4.8 zip() 61
2.4.9 eval()、exec() 62
第3章 玄之又玄,眾妙之門:詳解Python序列結(jié)構(gòu) 64
3.1 列表:打了激素的數(shù)組 64
3.1.1 列表創(chuàng)建與刪除 65
3.1.2 列表元素訪問 66
3.1.3 列表常用方法 67
3.1.4 列表對象支持的運算符 72
3.1.5 內(nèi)置函數(shù)對列表的操作 74
3.1.6 使用列表模擬向量運算 75
3.1.7 列表推導(dǎo)式語法與應(yīng)用案例 76
3.1.8 切片操作的強(qiáng)大功能 83
3.2 元組:輕量級列表 86
3.2.1 元組創(chuàng)建與元素訪問 86
3.2.2 元組與列表的異同點 87
3.2.3 生成器推導(dǎo)式 88
3.3 字典:反映對應(yīng)關(guān)系的映射類型 90
3.3.1 字典創(chuàng)建與刪除 90
3.3.2 字典元素的訪問 91
3.3.3 元素添加、修改與刪除 92
3.3.4 標(biāo)準(zhǔn)庫collections中與字典有關(guān)的類 93
3.4 集合:元素之間不允許重復(fù) 94
3.4.1 集合對象的創(chuàng)建與刪除 95
3.4.2 集合操作與運算 95
3.4.3 不可變集合frozenset 97
3.4.4 集合應(yīng)用案例 97
3.5 序列解包的多種形式和用法 100
3.6 標(biāo)準(zhǔn)庫中的其他常用數(shù)據(jù)類型 102
3.6.1 枚舉類型 102
3.6.2 數(shù)組類型 103
3.6.3 隊列 103
3.6.4 具名元組 105
3.6.5 堆 106
第4章 反者,道之動:程序控制結(jié)構(gòu) 108
4.1 條件表達(dá)式 108
4.2 選擇結(jié)構(gòu) 110
4.2.1 單分支選擇結(jié)構(gòu) 110
4.2.2 雙分支選擇結(jié)構(gòu) 111
4.2.3 多分支選擇結(jié)構(gòu) 112
4.2.4 選擇結(jié)構(gòu)的嵌套 113
4.2.5 構(gòu)建跳轉(zhuǎn)表實現(xiàn)多分支選擇結(jié)構(gòu) 114
4.3 循環(huán)結(jié)構(gòu) 114
4.3.1 for循環(huán)與while循環(huán) 115
4.3.2 break與continue語句 116
4.3.3 循環(huán)代碼優(yōu)化技巧 117
4.4 精彩案例賞析 118
第5章 代碼復(fù)用技術(shù)(一):函數(shù) 126
5.1 函數(shù)定義與使用 126
5.1.1 基本語法 126
5.1.2 函數(shù)嵌套定義、可調(diào)用對象與修飾器 128
5.1.3 函數(shù)對象成員的動態(tài)性 132
5.1.4 函數(shù)遞歸調(diào)用 132
5.2 函數(shù)參數(shù) 134
5.2.1 位置參數(shù) 135
5.2.2 默認(rèn)值參數(shù) 135
5.2.3 關(guān)鍵參數(shù) 137
5.2.4 可變長度參數(shù) 137
5.2.5 強(qiáng)制函數(shù)的某些參數(shù)必須以關(guān)鍵參數(shù)形式進(jìn)行傳值 138
5.2.6 強(qiáng)制函數(shù)的所有參數(shù)必須以位置參數(shù) 139
5.2.7 傳遞參數(shù)時的序列解包 140
5.2.8 標(biāo)注函數(shù)參數(shù)與返回值類型 142
5.3 變量作用域 142
5.3.1 全局變量與局部變量 142
5.3.2 nonlocal變量 145
5.4 lambda表達(dá)式 146
5.5 生成器函數(shù)設(shè)計要點 148
5.6 偏函數(shù)與函數(shù)柯里化 150
5.7 單分發(fā)器與泛型函數(shù) 152
5.8 協(xié)程函數(shù) 153
5.9 注冊程序退出時必須執(zhí)行的函數(shù) 155
5.10 回調(diào)函數(shù)原理與實現(xiàn) 156
5.11 精彩案例賞析 156
第6章 代碼復(fù)用技術(shù)(二):面向?qū)ο蟪绦蛟O(shè)計 184
6.1 類的定義與使用 184
6.1.1 基本語法 184
6.1.2 type類 185
6.1.3 定義帶修飾器的類 186
6.2 數(shù)據(jù)成員與成員方法 187
6.2.1 私有成員與公有成員 187
6.2.2 數(shù)據(jù)成員 189
6.2.3 成員方法、類方法、靜態(tài)方法、抽象方法 190
6.2.4 屬性 192
6.2.5 類與對象的動態(tài)性、混入機(jī)制 194
6.3 繼承、多態(tài)、依賴注入 196
6.3.1 繼承 196
6.3.2 多態(tài) 198
6.3.3 依賴注入技術(shù)的不同實現(xiàn)方法 199
6.4 特殊方法與運算符重載 202
6.5 精彩案例賞析 204
6.5.1 自定義隊列 204
6.5.2 自定義棧 208
6.5.3 自定義集合 210
6.5.4 自定義數(shù)組 216
6.5.5 自定義雙鏈表 221
6.5.6 自定義常量類 223
6.5.7 自定義不允許修改值的字典 224
6.5.8 自定義支持with關(guān)鍵字的類 225
第7章 文本處理(一):字符串 226
7.1 字符串編碼格式簡介 227
7.2 轉(zhuǎn)義字符與原始字符串 228
7.3 字符串格式化 229
7.3.1 使用%符號進(jìn)行格式 229
7.3.2 使用format()方法進(jìn)行字符串格式化 231
7.3.3 格式化的字符串常量 232
7.3.4 使用Template模板進(jìn)行格式化 232
7.4 字符串常用操作 233
7.4.1 find()、rfind()、index()、rindex()、count() 233
7.4.2 split()、rsplit()、partition()、rpartition() 235
7.4.3 join() 236
7.4.4 lower()、upper()、capitalize()、title()、swapcase() 237
7.4.5 replace()、maketrans()、translate() 238
7.4.6 strip()、rstrip()、lstrip() 239
7.4.7 startswith()、endswith() 239
7.4.8 isalnum()、isalpha()、isdigit()、isdecimal()、isnumeric()、isspace()、isupper()、islower() 240
7.4.9 center()、ljust()、rjust()、zfill() 241
7.4.10 字符串對象支持的運算符 241
7.4.11 適用于字符串對象的內(nèi)置函數(shù) 243
7.4.12 字符串對象的切片操作 245
7.5 其他有關(guān)模塊 245
7.5.1 textwrap模塊 245
7.5.2 zlib模塊提供的壓縮功能 248
7.6 字符串常量 249
7.7 可變字符串 250
7.8 中英文分詞 251
7.9 漢字到拼音的轉(zhuǎn)換 252
7.10 精彩案例賞析 253
第8章 文本處理(二):正則表達(dá)式 256
8.1 正則表達(dá)式語法 256
8.1.1 正則表達(dá)式基本語法 256
8.1.2 正則表達(dá)式擴(kuò)展語法 257
8.1.3 正則表達(dá)式錦集 257
8.2 直接使用正則表達(dá)式模塊re處理字符串 259
8.3 使用正則表達(dá)式對象處理字符串 262
8.4 match對象 264
8.5 精彩案例賞析 267
第9章 數(shù)據(jù)永久化:文件內(nèi)容操作 273
9.1 文件操作基本知識 274
9.1.1 內(nèi)置函數(shù)open() 274
9.1.2 文件對象屬性與常用方法 276
9.1.3 上下文管理語句with 277
9.2 文本文件內(nèi)容操作案例精選 277
9.3 二進(jìn)制文件操作案例精選 282
9.3.1 使用pickle模塊讀寫二進(jìn)制文件 282
9.3.2 使用struct模塊讀寫二進(jìn)制文件 284
9.3.3 使用shelve模塊操作二進(jìn)制文件 285
9.3.4 使用marshal模塊操作二進(jìn)制文件 285
9.3.5 其他常見類型二進(jìn)制文件操作案例 286
第10章 文件與文件夾操作 297
10.1 os模塊 297
10.2 os.path模塊 300
10.3 shutil模塊 301
10.4 其他常用模塊 303
10.4.1 glob模塊 303
10.4.2 fnmatch模塊 303
10.5 精彩案例賞析 304
第11章 代碼質(zhì)量保障:異常處理結(jié)構(gòu)、程序調(diào)試與測試 309
11.1 異常處理結(jié)構(gòu) 309
11.1.2 Python內(nèi)置異常類層次結(jié)構(gòu) 310
11.1.3 異常處理結(jié)構(gòu) 311
11.1.4 斷言與上下文管理語句 317
11.2 文檔測試doctest 318
11.3 單元測試unittest 320
11.4 覆蓋測試 323
11.5 軟件性能測試 324
11.6 代碼調(diào)試 326
11.6.1 使用IDLE調(diào)試 326
11.6.2 使用Eclipse+PyDev進(jìn)行代碼調(diào)試 329
11.6.3 使用pdb調(diào)試 329
第12章 多任務(wù)與并行處理:線程、進(jìn)程、協(xié)程、分布式、GPU加速 334
12.1 多線程編程 334
12.1.1 線程概念與標(biāo)準(zhǔn)庫threading 335
12.1.2 線程對象 336
12.1.3 線程調(diào)度 339
12.1.4 Lock/RLock對象 341
12.1.5 Condition對象 343
12.1.6 Queue對象 345
12.1.7 Event對象 348
12.1.8 Semaphore與BoundedSemaphore 349
12.1.9 Barrier對象 350
12.2 多進(jìn)程編程 351
12.2.1 進(jìn)程創(chuàng)建與管理 352
12.2.2 進(jìn)程同步技術(shù) 352
12.2.3 Pool對象 353
12.2.4 Manager對象 358
12.2.5 Listener與Client對象 361
12.2.6 進(jìn)程間數(shù)據(jù)交換與共享 362
12.2.7 標(biāo)準(zhǔn)庫subprocess 365
12.3 協(xié)程 365
12.4 concurrent.futures模塊提供的并發(fā)執(zhí)行功能 368
12.5 pySpark并行計算與分布式計算框架 369
12.6 GPU編程 376
12.6.1 使用pycuda實現(xiàn)GPU加速 376
12.6.2 使用pyopencl實現(xiàn)GPU加速 378
12.6.3 使用tensorflow實現(xiàn)GPU加速 379
第13章 互通互聯(lián):asyncio提供的網(wǎng)絡(luò)通信功能 381
13.1 Transport類與Protocol類 381
13.2 StreamReader與StreamWriter 386
附錄:精彩在繼續(xù) 390
附錄1:GUI開發(fā) 390
附錄2:SQLite數(shù)據(jù)庫操作 393
附錄3:計算機(jī)圖形學(xué)編程 394
附錄4:圖像編程 397
附錄5:數(shù)據(jù)分析、機(jī)器學(xué)習(xí)、科學(xué)計算可視化 400
附錄6:密碼學(xué)編程 400
附錄7:系統(tǒng)運維 401
附錄8:Windows系統(tǒng)編程 402
附錄9:軟件分析與逆向工程 404
責(zé)任編輯:
總結(jié)
以上是生活随笔為你收集整理的数独解题程序的python实现_使用Python编写程序求解数独游戏答案的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: (全角→半角)把文字从PDF复制到Wor
- 下一篇: cesium 高程数据使用