作者：小小明，博客地址：https://blog.csdn.net/as604049322
最近发现有个玩数独游戏的网站：https://www.sudoku.name/index-cn.php
游戏界面如下图所示
当然这类玩数独游戏的网站很多，现在我们先以该网站为例进行演示。希望能用Python实现自动计算并填好数独游戏！
大概效果能像下面这样就好啦
玩过的都非常清楚数独的基本规则：
-
数字 1-9 在每一行只能出现一次。
-
数字 1-9 在每一列只能出现一次。
-
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
如何让程序辅助我们玩这个数独游戏呢？
思路：
-
我们可以通过web自动化测试工具（例如selenium）打开该网页
-
解析网页获取表格数据
-
传入处理程序中自动解析表格
-
使用程序自动写入计算好的数独结果
下面我们尝试一步步解决这个问题：
通过Selenium访问目标网址
关于selenium的安装请参考：
https://blog.csdn.net/as604049322/article/details/114157526
首先通过selenium打开游览器：
1from selenium import webdriver 2browser = webdriver.Chrome()
如果你的selenium已经正确安装，运行上述代码会打开谷歌游览器：
此时我们可以通过直接在受控制的游览器输入url访问，也可以用代码控制游览器访问数独游戏的网址：
1url = "https://www.sudoku.name/index.php?ln=cn&puzzle_num=&play=1&difficult=4&timer=&time_limit=0" 2browser.get(url)
内心PS：以后还是得给谷歌游览器装个去广告的插件
数独数据提取
节点分析
table节点的id为：
节点值存在于value属性中：
使用Selenium控制游览器就是这个好处，可以随时让程序提取我们需要的数据。
首先获取目标table标签：
1from selenium.webdriver.common.by import By 2from selenium.webdriver.support.ui import WebDriverWait 3from selenium.webdriver.support import expected_conditions as EC 4 5wait = WebDriverWait(browser, 10) 6 7table = wait.until(EC.element_to_be_clickable( 8 (By.CSS_SELECTOR, 'table#sudoku_main_board')))
下面我们根据对节点的分析提取出我们需要的数独数据：
1board = [] 2for tr in table.find_elements_by_xpath(".//tr"): 3 row = [] 4 for input_e in tr.find_elements_by_xpath(".//input[@class='i3']"): 5 cell = input_e.get_attribute("value") 6 row.append(cell if cell else ".") 7 board.append(row) 8board
1[['7', '.', '.', '.', '.', '4', '.', '.', '.'], 2 ['.', '4', '.', '.', '.', '5', '9', '.', '.'], 3 ['8', '.', '.', '.', '.', '.', '.', '2', '.'], 4 ['.', '.', '6', '.', '9', '.', '.', '.', '4'], 5 ['.', '1', '.', '.', '.', '.', '.', '3', '.'], 6 ['2', '.', '.', '.', '8', '.', '5', '.', '.'], 7 ['.', '5', '.', '.', '.', '.', '.', '.', '1'], 8 ['.', '.', '3', '7', '.', '.', '.', '8', '.'], 9 ['.', '.', '.', '2', '.', '.', '.', '.', '6']]
将凡是需要填写的位置都用.表示。
数独计算程序
如何对上述数独让程序来计算结果呢？这就需要逻辑算法的思维了。
这类问题最基本的解题思维就是通过递归 + 回溯算法遍历所有可能的填法挨个验证有效性，直到找到没有冲突的情况。在递归的过程中，如果当前的空白格不能填下任何一个数字，那么就进行回溯。
在此基础上，我们可以使用位运算进行优化。常规方法我们需要使用长度为 99 的数组表示每个数字是否出现过，借助位运算，仅使用一个整数就可以表示每个数字是否出现过。例如二进制表 (011000100)表示数字 3，7，8 已经出现过。
具体而言最终的程序还算比较复杂的，无法理解代码逻辑的可以直接复制粘贴：
1def solveSudoku(board): 2 def flip(i: int, j: int, digit: int): 3 line[i] ^= (1 << digit) 4 column[j] ^= (1 << digit) 5 block[i // 3][j // 3] ^= (1 << digit) 6 7 def dfs(pos: int): 8 nonlocal valid 9 if pos == len(spaces): 10 valid = True 11 return 12 13 i, j = spaces[pos] 14 mask = ~(line[i] | column[j] | block[i // 3][j // 3]) & 0x1ff 15 while mask: 16 digitMask = mask & (-mask) 17 digit = bin(digitMask).count("0") - 1 18 flip(i, j, digit) 19 board[i][j] = str(digit + 1) 20 dfs(pos + 1) 21 flip(i, j, digit) 22 mask &= (mask - 1) 23 if valid: 24 return 25 26 line = [0] * 9 27 column = [0] * 9 28 block = [[0] * 3 for _ in range(3)] 29 valid = False 30 spaces = list() 31 32 for i in range(9): 33 for j in range(9): 34 if board[i][j] == ".": 35 spaces.append((i, j)) 36 else: 37 digit = int(board[i][j]) - 1 38 flip(i, j, digit) 39 40 dfs(0)
然后我们运行一下：
1solveSudoku(board) 2board
1[['7', '2', '9', '3', '6', '4', '1', '5', '8'], 2 ['3', '4', '1', '8', '2', '5', '9', '6', '7'], 3 ['8', '6', '5', '9', '7', '1', '4', '2', '3'], 4 ['5', '3', '6', '1', '9', '2', '8', '7', '4'], 5 ['9', '1', '8', '5', '4', '7', '6', '3', '2'], 6 ['2', '7', '4', '6', '8', '3', '5', '1', '9'], 7 ['6', '5', '2', '4', '3', '8', '7', '9', '1'], 8 ['4', '9', '3', '7', '1', '6', '2', '8', '5'], 9 ['1', '8', '7', '2', '5', '9', '3', '4', '6']]
可以看到，程序已经计算出了数独的结果。
不过对于数据：
1[['.', '.', '.', '6', '.', '.', '.', '3', '.'], 2 ['5', '.', '.', '.', '.', '.', '6', '.', '.'], 3 ['.', '9', '.', '.', '.', '5', '.', '.', '.'], 4 ['.', '.', '4', '.', '1', '.', '.', '.', '6'], 5 ['.', '.', '.', '4', '.', '3', '.', '.', '.'], 6 ['8', '.', '.', '.', '9', '.', '5', '.', '.'], 7 ['.', '.', '.', '7', '.', '.', '.', '4', '.'], 8 ['.', '.', '5', '.', '.', '.', '.', '.', '8'], 9 ['.', '3', '.', '.', '.', '8', '.', '.', '.']]
上述算法耗时居然达到17秒，还需继续优化算法：
1def solveSudoku(board: list) -> None: 2 def flip(i: int, j: int, digit: int): 3 line[i] ^= (1 << digit) 4 column[j] ^= (1 << digit) 5 block[i // 3][j // 3] ^= (1 << digit) 6 7 def dfs(pos: int): 8 nonlocal valid 9 if pos == len(spaces): 10 valid = True 11 return 12 13 i, j = spaces[pos] 14 mask = ~(line[i] | column[j] | block[i // 3][j // 3]) & 0x1ff 15 while mask: 16 digitMask = mask & (-mask) 17 digit = bin(digitMask).count("0") - 1 18 flip(i, j, digit) 19 board[i][j] = str(digit + 1) 20 dfs(pos + 1) 21 flip(i, j, digit) 22 mask &= (mask - 1) 23 if valid: 24 return 25 26 line = [0] * 9 27 column = [0] * 9 28 block = [[0] * 3 for _ in range(3)] 29 valid = False 30 spaces = list() 31 32 for i in range(9): 33 for j in range(9): 34 if board[i][j] != ".": 35 digit = int(board[i][j]) - 1 36 flip(i, j, digit) 37 38 while True: 39 modified = False 40 for i in range(9): 41 for j in range(9): 42 if board[i][j] == ".": 43 mask = ~(line[i] | column[j] | 44 block[i // 3][j // 3]) & 0x1ff 45 if not (mask & (mask - 1)): 46 digit = bin(mask).count("0") - 1 47 flip(i, j, digit) 48 board[i][j] = str(digit + 1) 49 modified = True 50 if not modified: 51 break 52 53 for i in range(9): 54 for j in range(9): 55 if board[i][j] == ".": 56 spaces.append((i, j)) 57 58 dfs(0)
再次运行：
1solveSudoku(board) 2board
耗时仅3.2秒，性能提升不少。
优化思路：如果一个空白格只有唯一的数可以填入，也就是其对应的 b 值和 b-1 进行按位与运算后得到 0（即 b 中只有一个二进制位为 1）。此时，我们就可以确定这个空白格填入的数，而不用等到递归时再去处理它。
下面我们需要做的就是将结果填入到相应的位置中，毕竟自己手敲也挺费劲的。
写结果回写到网页
对于Selenium，我们可以模拟人工点击按钮并发送键盘操作。
下面我们重新遍历table标签，并使用click和send_keys方法：
1for i, tr in enumerate(table.find_elements_by_xpath(".//tr")): 2 for j, input_e in enumerate(tr.find_elements_by_xpath(".//input[@class='i3']")): 3 if input_e.get_attribute("readonly") == "true": 4 continue 5 input_e.click() 6 input_e.clear() 7 input_e.send_keys(board[i][j])
运行过程中的效果：
△程序自动填写
骨灰级数独玩家证明：
别人14分钟，你用程序10秒填完。
用Python后终于也体验了一次“最强大脑”的感觉了，先容我装个B去
大家如果喜欢这类文章，欢迎关注小明哥的博客_https://blog.csdn.net/as604049322_
-------------------********************************** End **********-------------**-----********-**********************************
往期精彩文章推荐：
欢迎各位大佬点击链接加入群聊【helloworld开发者社区】：https://jq.qq.com/?_wv=1027&k=mBlk6nzX进群交流IT技术热点。
本文转自 https://mp.weixin.qq.com/s/dqmFmNh2Fpwrwf7OCdRgmw，如有侵权，请联系删除。