游戲界面如下圖所示
當然這類玩數獨游戲的網站很多，現在我們先以該網站為例進行演示，希望能用Python實作自動計算并填好數獨游戲！
很多人學習蟒蛇，不知道從何學起， 很多人學習python，掌握了基本語法之后，不知道在哪里尋找案例上手， 很多已經做了案例的人，卻不知道如何去學習更多高深的知識， 那么針對這三類人，我給大家提供一個好的學習平臺，免費獲取視頻教程，電子書，以及課程的源代碼！ QQ群：101677771 歡迎加入，一起討論一起學習！
大概效果能像下面這樣就好啦
玩過的都非常清楚數獨的基本規則：
- 數字 1-9 在每一行只能出現一次，
- 數字 1-9 在每一列只能出現一次，
- 數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次，
如何讓程式輔助我們玩這個數獨游戲呢？
思路：
- 我們可以通過web自動化測驗工具（例如selenium）打開該網頁
- 決議網頁獲取表格資料
- 傳入處理程式中自動決議表格
- 使用程式自動寫入計算好的數獨結果
下面我們嘗試一步步解決這個問題：
通過Selenium訪問目標網址
關于selenium的安裝請參考：
https://blog.csdn.net/as604049322/article/details/114157526
首先通過selenium打開瀏覽器：
from selenium import webdriver
browser = webdriver.Chrome()
如果你的selenium已經正確安裝，運行上述代碼會打開谷歌游覽器：
此時我們可以通過直接在受控制的游覽器輸入url訪問，也可以用代碼控制游覽器訪問數獨游戲的網址：
url = "https://www.sudoku.name/index.php?ln=cn&puzzle_num=&play=1&difficult=4&timer=&time_limit=0"
browser.get(url)
內心PS：以后還是得給谷歌游覽器裝個去廣告的插件
數獨資料提取
節點分析
table節點的id為：
節點值存在于value屬性中：
使用Selenium控制游覽器就是這個好處，可以隨時讓程式提取我們需要的資料，
首先獲取目標table標簽：
from selenium.webdriver.common.by import By
from selenium.webdriver.support.ui import WebDriverWait
from selenium.webdriver.support import expected_conditions as EC
wait = WebDriverWait(browser, 10)
table = wait.until(EC.element_to_be_clickable(
(By.CSS_SELECTOR, 'table#sudoku_main_board')))
下面我們根據對節點的分析提取出我們需要的資料：
board = []
for tr in table.find_elements_by_xpath(".//tr"):
row = []
for input_e in tr.find_elements_by_xpath(".//input[@class='i3']"):
cell = input_e.get_attribute("value")
row.append(cell if cell else ".")
board.append(row)
board
[['7', '.', '.', '.', '.', '4', '.', '.', '.'],
['.', '4', '.', '.', '.', '5', '9', '.', '.'],
['8', '.', '.', '.', '.', '.', '.', '2', '.'],
['.', '.', '6', '.', '9', '.', '.', '.', '4'],
['.', '1', '.', '.', '.', '.', '.', '3', '.'],
['2', '.', '.', '.', '8', '.', '5', '.', '.'],
['.', '5', '.', '.', '.', '.', '.', '.', '1'],
['.', '.', '3', '7', '.', '.', '.', '8', '.'],
['.', '.', '.', '2', '.', '.', '.', '.', '6']]
將凡是需要填寫的位置都用.表示，
數獨計算程式
如何對上述數獨讓程式來計算結果呢？這就需要邏輯演算法的思維了，
這類問題最基本的解題思維就是通過遞回 + 回溯演算法遍歷所有可能的填法挨個驗證有效性，直到找到沒有沖突的情況，在遞回的程序中，如果當前的空白格不能填下任何一個數字，那么就進行回溯，
在此基礎上，我們可以使用位運算進行優化，常規方法我們需要使用長度為 99 陣串列示每個數字是否出現過，借助位運算，僅使用一個整數就可以表示每個數字是否出現過，例如二進制表 (011000100)表示數字 3，7，8 已經出現過，
具體而言最終的程式還算比較復雜的，無法理解代碼邏輯的可以直接復制粘貼：
def solveSudoku(board):
def flip(i: int, j: int, digit: int):
line[i] ^= (1 << digit)
column[j] ^= (1 << digit)
block[i // 3][j // 3] ^= (1 << digit)
def dfs(pos: int):
nonlocal valid
if pos == len(spaces):
valid = True
return
i, j = spaces[pos]
mask = ~(line[i] | column[j] | block[i // 3][j // 3]) & 0x1ff
while mask:
digitMask = mask & (-mask)
digit = bin(digitMask).count("0") - 1
flip(i, j, digit)
board[i][j] = str(digit + 1)
dfs(pos + 1)
flip(i, j, digit)
mask &= (mask - 1)
if valid:
return
line = [0] * 9
column = [0] * 9
block = [[0] * 3 for _ in range(3)]
valid = False
spaces = list()
for i in range(9):
for j in range(9):
if board[i][j] == ".":
spaces.append((i, j))
else:
digit = int(board[i][j]) - 1
flip(i, j, digit)
dfs(0)
然后我們再運行一下：
solveSudoku(board)
board
[['7', '2', '9', '3', '6', '4', '1', '5', '8'],
['3', '4', '1', '8', '2', '5', '9', '6', '7'],
['8', '6', '5', '9', '7', '1', '4', '2', '3'],
['5', '3', '6', '1', '9', '2', '8', '7', '4'],
['9', '1', '8', '5', '4', '7', '6', '3', '2'],
['2', '7', '4', '6', '8', '3', '5', '1', '9'],
['6', '5', '2', '4', '3', '8', '7', '9', '1'],
['4', '9', '3', '7', '1', '6', '2', '8', '5'],
['1', '8', '7', '2', '5', '9', '3', '4', '6']]
可以看到，程式已經計算出了數獨的結果，
不過對于資料來說：
[['.', '.', '.', '6', '.', '.', '.', '3', '.'],
['5', '.', '.', '.', '.', '.', '6', '.', '.'],
['.', '9', '.', '.', '.', '5', '.', '.', '.'],
['.', '.', '4', '.', '1', '.', '.', '.', '6'],
['.', '.', '.', '4', '.', '3', '.', '.', '.'],
['8', '.', '.', '.', '9', '.', '5', '.', '.'],
['.', '.', '.', '7', '.', '.', '.', '4', '.'],
['.', '.', '5', '.', '.', '.', '.', '.', '8'],
['.', '3', '.', '.', '.', '8', '.', '.', '.']]
上述演算法耗時居然達到17秒，還需繼續優化演算法：
def solveSudoku(board: list) -> None:
def flip(i: int, j: int, digit: int):
line[i] ^= (1 << digit)
column[j] ^= (1 << digit)
block[i // 3][j // 3] ^= (1 << digit)
def dfs(pos: int):
nonlocal valid
if pos == len(spaces):
valid = True
return
i, j = spaces[pos]
mask = ~(line[i] | column[j] | block[i // 3][j // 3]) & 0x1ff
while mask:
digitMask = mask & (-mask)
digit = bin(digitMask).count("0") - 1
flip(i, j, digit)
board[i][j] = str(digit + 1)
dfs(pos + 1)
flip(i, j, digit)
mask &= (mask - 1)
if valid:
return
line = [0] * 9
column = [0] * 9
block = [[0] * 3 for _ in range(3)]
valid = False
spaces = list()
for i in range(9):
for j in range(9):
if board[i][j] != ".":
digit = int(board[i][j]) - 1
flip(i, j, digit)
while True:
modified = False
for i in range(9):
for j in range(9):
if board[i][j] == ".":
mask = ~(line[i] | column[j] |
block[i // 3][j // 3]) & 0x1ff
if not (mask & (mask - 1)):
digit = bin(mask).count("0") - 1
flip(i, j, digit)
board[i][j] = str(digit + 1)
modified = True
if not modified:
break
for i in range(9):
for j in range(9):
if board[i][j] == ".":
spaces.append((i, j))
dfs(0)
再次運行：
solveSudoku(board)
board
耗時僅3.2秒，性能提升不少，
優化思路：如果一個空白格只有唯一的數字可以填入，也就是其對應的 b 值和 b-1 進行按位與運算后得到 0（即 b 只有一個二進制位置為 1），此時，我們就可以確定這個空白格填入的數，而不用等到遞回時再去處理它，
下面我們需要做的就是將結果填入到相應的位置中，畢竟自己手敲也挺費勁的，
寫結果回寫到網頁
對于Selenium，我們可以模擬人工點擊按鈕并發送鍵盤操作，
下面我們重新遍歷table標簽，并使用click和send_keys方法：
for i, tr in enumerate(table.find_elements_by_xpath(".//tr")):
for j, input_e in enumerate(tr.find_elements_by_xpath(".//input[@class='i3']")):
if input_e.get_attribute("readonly") == "true":
continue
input_e.click()
input_e.clear()
input_e.send_keys(board[i][j])
運行程序中的效果：
△程式自動填寫
骨灰級數獨玩家證明：
別人14分鐘，你用程式10秒填完，
用Python后終于也體驗了一次“最強大腦”的感覺了，先容我裝個B去
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/396038.html
標籤：Python