让Python程序自动玩数独游戏，秒变最强大脑！

当然这类玩数独游戏的网站很多，现在我们先以该网站为例进行演示。希望能用Python实现自动计算并填好数独游戏！

大概效果能像下面这样就好啦👇

玩过的都非常清楚数独的基本规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

如何让程序辅助我们玩这个数独游戏呢？

思路：

• 我们可以通过web自动化测试工具（例如selenium）打开该网页
• 解析网页获取表格数据
• 传入处理程序中自动解析表格
• 使用程序自动写入计算好的数独结果

下面我们尝试一步步解决这个问题：

通过Selenium访问目标网址

关于selenium的安装请参考：

https://blog.csdn.net/as604049322/article/details/114157526

首先通过selenium打开游览器：

 webdriver
browser = webdriver.Chrome() 

如果你的selenium已经正确安装，运行上述代码会打开谷歌游览器：

此时我们可以通过直接在受控制的游览器输入url访问，也可以用代码控制游览器访问数独游戏的网址：

browser.get(url) 

内心PS：以后还是得给谷歌游览器装个去广告的插件

数独数据提取

节点分析

table节点的id为：

节点值存在于value属性中：

使用Selenium控制游览器就是这个好处，可以随时让程序提取我们需要的数据。

首先获取目标table标签：

 EC

wait = WebDriverWait(browser, 10)

table = wait.until(EC.element_to_be_clickable(
(By.CSS_SELECTOR, 'table#sudoku_main_board')))

下面我们根据对节点的分析提取出我们需要的数独数据：

)
    board.append(row)
board 

]] 

将凡是需要填写的位置都用.表示。

数独计算程序

如何对上述数独让程序来计算结果呢？这就需要逻辑算法的思维了。

这类问题最基本的解题思维就是通过递归 + 回溯算法遍历所有可能的填法挨个验证有效性，直到找到没有冲突的情况。在递归的过程中，如果当前的空白格不能填下任何一个数字，那么就进行回溯。

在此基础上，我们可以使用位运算进行优化。常规方法我们需要使用长度为 99 的数组表示每个数字是否出现过，借助位运算，仅使用一个整数就可以表示每个数字是否出现过。例如二进制表 (011000100)表示数字 3，7，8 已经出现过。

具体而言最终的程序还算比较复杂的，无法理解代码逻辑的可以直接复制粘贴：

 << 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 

]] 

可以看到，程序已经计算出了数独的结果。

不过对于数据：

]] 

上述算法耗时居然达到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方法：

        input_e.click()
        input_e.clear()
        input_e.send_keys(board[i][j]) 

运行过程中的效果：

骨灰级数独玩家证明：

别人14分钟，你用程序10秒填完。

用Python后终于也体验了一次“最强大脑”的感觉了，先容我装个B去🚀