游戏界面如下图所示
当然这类玩数独游戏的网站很多，当初咱们先以该网站为例进行演示。心愿能用 Python 实现主动计算并填好数独游戏 ！
大略成果能像上面这样就好啦👇
玩过的都十分分明数独的根本规定：
- 数字 1-9 在每一行只能呈现一次。
- 数字 1-9 在每一列只能呈现一次。
- 数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能呈现一次。
如何让程序辅助咱们玩这个数独游戏呢？
思路：
- 咱们能够通过 web 自动化测试工具（例如 selenium）关上该网页
- 解析网页获取表格数据
- 传入处理程序中主动解析表格
- 应用程序主动写入计算好的数独后果
上面咱们尝试一步步解决这个问题：
通过 Selenium 拜访指标网址
对于 selenium 的装置请参考：
https://blog.csdn.net/as60404…
首先通过 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 去🚀
文末
您的点赞珍藏就是对我最大的激励！
欢送关注我，分享 Python 干货，交换 Python 技术。
对文章有何见解，或者有何技术问题，欢送在评论区一起留言探讨！