游戏界面如下图所示

当然这类玩数独游戏的网站很多，现在我们先以该网站为例进行演示，希望能用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)

数独资料提取

节点分析

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秒，性能提升不少，

下面我们需要做的就是将结果填入到相应的位置中，毕竟自己手敲也挺费劲的，

写结果回写到网页

对于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])

运行程序中的效果：