让程序自动玩数独游戏让你秒变骨灰级数独玩家

news/2024/11/15 6:52:11/

程序自动填网页数独游戏

有个玩数独游戏的网站：https://www.sudoku.name/index-cn.php

image-20210707014138477

当然这类玩数独游戏的网站很多，现在我们先以该网站为例进行演示。

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

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

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

思路：

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

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

通过Selenium访问目标网址

关于selenium的安装请参考：https://blog.csdn.net/as604049322/article/details/114157526

首先通过selenium打开游览器：

from selenium import webdriver
browser = webdriver.Chrome()

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

image-20210708175406793

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

url = "https://www.sudoku.name/index.php?ln=cn&puzzle_num=&play=1&difficult=4&timer=&time_limit=0"
browser.get(url)

image-20210708180832959

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

数独数据提取

节点分析

table节点的id为：

image-20210708184010599

节点值存在于value属性中：

image-20210708184159928

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

首先获取目标table标签：

from selenium.webdriver.common.by import By
from selenium.webdriver.support.ui import WebDriverWait
from selenium.webdriver.support import expected_conditions as ECwait = 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 validif pos == len(spaces):valid = Truereturni, j = spaces[pos]mask = ~(line[i] | column[j] | block[i // 3][j // 3]) & 0x1ffwhile mask:digitMask = mask & (-mask)digit = bin(digitMask).count("0") - 1flip(i, j, digit)board[i][j] = str(digit + 1)dfs(pos + 1)flip(i, j, digit)mask &= (mask - 1)if valid:returnline = [0] * 9column = [0] * 9block = [[0] * 3 for _ in range(3)]valid = Falsespaces = 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]) - 1flip(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 validif pos == len(spaces):valid = Truereturni, j = spaces[pos]mask = ~(line[i] | column[j] | block[i // 3][j // 3]) & 0x1ffwhile mask:digitMask = mask & (-mask)digit = bin(digitMask).count("0") - 1flip(i, j, digit)board[i][j] = str(digit + 1)dfs(pos + 1)flip(i, j, digit)mask &= (mask - 1)if valid:returnline = [0] * 9column = [0] * 9block = [[0] * 3 for _ in range(3)]valid = Falsespaces = list()for i in range(9):for j in range(9):if board[i][j] != ".":digit = int(board[i][j]) - 1flip(i, j, digit)while True:modified = Falsefor i in range(9):for j in range(9):if board[i][j] == ".":mask = ~(line[i] | column[j] |block[i // 3][j // 3]) & 0x1ffif not (mask & (mask - 1)):digit = bin(mask).count("0") - 1flip(i, j, digit)board[i][j] = str(digit + 1)modified = Trueif not modified:breakfor i in range(9):for j in range(9):if board[i][j] == ".":spaces.append((i, j))dfs(0)

再次运行：

solveSudoku(board)
board

image-20210708195631062

耗时仅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":continueinput_e.click()input_e.clear()input_e.send_keys(board[i][j])

运行过程中的效果：

录制_2021_07_08_20_45_24_372

骨灰级数独玩家证明：

image-20210708205314338

别人9分钟，你用程序11秒填完。

完整代码

from selenium.webdriver.support import expected_conditions as EC
from selenium.webdriver.support.ui import WebDriverWait
from selenium.webdriver.common.by import By
from selenium import webdriverbrowser = webdriver.Chrome()
url = "https://www.sudoku.name/index.php?ln=cn&puzzle_num=&play=1&difficult=4&timer=&time_limit=0"
browser.get(url)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)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 validif pos == len(spaces):valid = Truereturni, j = spaces[pos]mask = ~(line[i] | column[j] | block[i // 3][j // 3]) & 0x1ffwhile mask:digitMask = mask & (-mask)digit = bin(digitMask).count("0") - 1flip(i, j, digit)board[i][j] = str(digit + 1)dfs(pos + 1)flip(i, j, digit)mask &= (mask - 1)if valid:returnline = [0] * 9column = [0] * 9block = [[0] * 3 for _ in range(3)]valid = Falsespaces = list()for i in range(9):for j in range(9):if board[i][j] != ".":digit = int(board[i][j]) - 1flip(i, j, digit)while True:modified = Falsefor i in range(9):for j in range(9):if board[i][j] == ".":mask = ~(line[i] | column[j] |block[i // 3][j // 3]) & 0x1ffif not (mask & (mask - 1)):digit = bin(mask).count("0") - 1flip(i, j, digit)board[i][j] = str(digit + 1)modified = Trueif not modified:breakfor i in range(9):for j in range(9):if board[i][j] == ".":spaces.append((i, j))dfs(0)solveSudoku(board)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":continueinput_e.click()input_e.clear()input_e.send_keys(board[i][j])

数独网站2

还有一个数独网站是：https://cn.sudokupuzzle.org/

实际数独游戏处于框架内部，我们可以直接只看内部：https://cn.sudokupuzzle.org/online2.php?nd=4

上面的网站都搞定了，这个网站的节点元素相对简单很多，按照同样的思想，我们编写出如下代码：

from selenium.webdriver.support import expected_conditions as EC
from selenium.webdriver.support.ui import WebDriverWait
from selenium.webdriver.common.by import By
from selenium import webdriverbrowser = webdriver.Chrome()
url = "https://cn.sudokupuzzle.org/online2.php?nd=4"
browser.get(url)wait = WebDriverWait(browser, 10)
table = wait.until(EC.element_to_be_clickable((By.CSS_SELECTOR, 'table.sd')))
board = []
for tr in table.find_elements_by_xpath('.//tr'):row = []for input_e in tr.find_elements_by_xpath('.//td/input'):cell = input_e.get_attribute("value")row.append(cell if cell else ".")board.append(row)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 validif pos == len(spaces):valid = Truereturni, j = spaces[pos]mask = ~(line[i] | column[j] | block[i // 3][j // 3]) & 0x1ffwhile mask:digitMask = mask & (-mask)digit = bin(digitMask).count("0") - 1flip(i, j, digit)board[i][j] = str(digit + 1)dfs(pos + 1)flip(i, j, digit)mask &= (mask - 1)if valid:returnline = [0] * 9column = [0] * 9block = [[0] * 3 for _ in range(3)]valid = Falsespaces = list()for i in range(9):for j in range(9):if board[i][j] != ".":digit = int(board[i][j]) - 1flip(i, j, digit)while True:modified = Falsefor i in range(9):for j in range(9):if board[i][j] == ".":mask = ~(line[i] | column[j] |block[i // 3][j // 3]) & 0x1ffif not (mask & (mask - 1)):digit = bin(mask).count("0") - 1flip(i, j, digit)board[i][j] = str(digit + 1)modified = Trueif not modified:breakfor i in range(9):for j in range(9):if board[i][j] == ".":spaces.append((i, j))dfs(0)solveSudoku(board)for i, tr in enumerate(table.find_elements_by_xpath(".//tr")):for j, input_e in enumerate(tr.find_elements_by_xpath(".//td/input")):if input_e.get_attribute("readonly") == "true":continueinput_e.click()input_e.clear()input_e.send_keys(board[i][j])

也玩一把：

录制_2021_07_08_21_50_37_630


http://www.ppmy.cn/news/563441.html

相关文章

项目集活动—项目集交付阶段活动

项目集活动—项目集交付阶段活动

项目集交付阶段活动包括协调和管理项目集实际交付所需执行的项目集活动。这些活动包括围绕 变更控制、报告和信息发布所开展的活动&#xff0c;以及围绕成本、采购、质量和风险所开展的活动。 这些活动提供了贯穿整个项目集生命周期的支持活动和流程&#xff0c;旨在提供项目集…
阅读更多...
为什么要做数据治理

为什么要做数据治理

在数聚股份看来&#xff0c;数据治理是管理企业数据资源、提高数据价值的一种方法。它是一种综合性的管理方式&#xff0c;旨在帮助企业提高数据管理效率&#xff0c;加强数据安全管理&#xff0c;优化数据质量。随着企业数据规模的不断增大&#xff0c;数据治理越来越成为企业…
阅读更多...
java中如何实现字符串反转

java中如何实现字符串反转

java中如何实现字符串反转 方式1&#xff1a;通过创建StringBuilder或StringBuffer对象&#xff0c;并使用其reverse()方法实现字符串的反转 上代码&#xff1a; /*** 给定一个字符串&#xff0c;通过创建SpringBuilder对象的方式将字符串进行反转* return*/public static …
阅读更多...
Adobe Photoshop CC 2014 15.2.1 32/64位中文特别安装版+绿色版

Adobe Photoshop CC 2014 15.2.1 32/64位中文特别安装版+绿色版

软件名称：Photoshp CC 2014软件版本：15.2.0.230软件语言：简体中文 软件官网：http://www.adobe.com/cn/软件大小：139M+165M软件依赖：vc++ 2008、2010、2012运行库 运行环境：Windows vista/Win7/Win8/Win8.1测试环境：windows8.1 x64/x86（32位在虚拟机中测试） 更新人：r…
阅读更多...
win7 64位系统PS、AI、PSD缩略图预览补丁

win7 64位系统PS、AI、PSD缩略图预览补丁

MysticThumbs支持Windows 7 / Vista / XP&#xff0c;32位和64位。除了预览PSD以外&#xff0c;还支持DDS、SGI缩略图显示。 Mystic Thumbs是一款用来支持win7 64位操作系统psd缩略图的小插件。现在win7系统已经被越来越多的人接受&#xff0c;甚至win7 64位系统都有着大量的用…
阅读更多...
photoshop  绿色版下载地址

photoshop  绿色版下载地址

http://www.yzhida.com/photoshop 转载于:https://my.oschina.net/u/3523365/blog/1031300
阅读更多...
Photoshop CC 2018 破解绿色版

Photoshop CC 2018 破解绿色版

版本说明 by zd423 01、移除多国语言、示例文件、搜索、教程、帮助等文件&#xff1b; 02、移除扩展功能#新式界面新建文档面板组件,可自行下载恢复&#xff1b; 03、系统无需安装VC运行库即可直接运行&#xff0c;放U盘随插随用方便&#xff1b; 04、移除扩展功能 05、集…
阅读更多...
ps滤镜下载大全-PSCC 64位滤镜收集

ps滤镜下载大全-PSCC 64位滤镜收集

图片后期处理软件最新版本 顶级数码后期软件DxO Optics Pro 9.5.125汉化版 DxO Optics Pro 破解版是世界上最好的照片后期处理软件之一&#xff0c;也是一款数码单反相机自动图象质量优化软件&#xff0c;具有图像光学纠正、优化曝光、调整对比度、色彩控制、RAW格式转换、消除…
阅读更多...
最新文章

Copyright @ 2022~2023