准备工作
系统
由于使用exe文件和win32gui，所以只支持Windows。
数字华容道游戏下载
下载一个数字华容道的游戏，如图：
这个文件可在https://pan.baidu.com/s/1hI8Ngo5_VZsdPYjtgXaewg下载。
提取码: 9wg6
下载第三方库
依赖项不少：
pip install pillow
pip install pyautogui
pip install pypiwin32
pip install paddlepaddle
pip install shapely
pip install paddleocr
算法分析
计算解法
- 使用bfs暴力穷举搜索，求出可以由当前状态变换而成的2-4个状态，并记录父级关系哈希表(模拟一颗树)，直到还原为止。
- 根据父级关系哈希表逆推还原解题步骤。
OCR
- 使用
paddleocr获取盘面信息。 - 对中心点标注，没有的则为空缺点。
项目结构
代码
ai.py
计算解法部分
from collections import deque, defaultdict
from typing import List
from copy import deepcopy
TARGET = [
[1, 2, 3],
[4, 5, 6],
[7, 8, -1]
] # 定义结果列表
def find_position(target: int, board: List[List[int]]):
"""
寻找一个值在二维列表中的位置。
:param target: 目标值
:param board: 二维列表
:return: 值在二维列表中的位置
"""
for x, i in enumerate(board): # 遍历board，时间复杂度O(n2)
for y, j in enumerate(i):
if j == target:
return x, y
raise ValueError
def find_next(state: str):
"""
给定当前状态，返回可以由当前状态变换而成的状态。
:param state: 当前状态字符串表示
:return: 可以由当前状态变换而成的状态list，保证长度为2-4
"""
board = eval(state) # 转列表
res = []
x, y = find_position(-1, board)
for nx, ny in ((0, 1), (0, -1), (-1, 0), (1, 0)): # 遍历四个方向
tx, ty = nx + x, ny + y
if 0 <= tx < 3 and 0 <= ty < 3: # 在范围内
temp = deepcopy(board) # 二维列表深拷贝一份
temp[x][y], temp[tx][ty] = temp[tx][ty], temp[x][y] # 移动方向上的数字
res.append(str(temp))
return res
def get_parent(board: List[List[int]]):
"""
给定一个盘面，返回运算后的父级关系哈希表。
:param board: 初始盘面，二维列表
:return: 父级关系哈希表
"""
parent = defaultdict(str)
state = str(board) # 字符串可以哈希
visited = {state} # 遍历过的状态
q = deque()
q.append(state)
parent[state] = 'None'
while q: # bfs穷举求解
state = q.popleft()
# print(state)
if state == str(TARGET):
return parent
for nxt in find_next(state):
if nxt not in visited:
q.append(nxt) # 放到待处理队列中
visited.add(nxt)
parent[nxt] = state # 记录关系
return parent
def get_list(ans: List[str]):
"""
对比每个状态，求上下状态中移动方向。
:param ans: 状态列表
:return: 移动方向列表
"""
res = []
for index, item in enumerate(ans):
if index == 0:
continue
item = eval(item)
last = eval(ans[index - 1]) # 上一个状态
lx, ly = find_position(-1, last)
# 上一个状态中空缺位置在这个状态中的数字即为移动的数字
move = item[lx][ly]
nx, ny = find_position(move, last) # 上一个状态中移动数字的位置
if lx - nx == 1:
res.append('down')
elif lx - nx == -1:
res.append('up')
elif ly - ny == 1:
res.append('right')
else:
res.append('left')
# print(last, item, res)
return res
def find_answer(parent: defaultdict, start: str):
"""
给定父级关系哈希表和初始盘面，求移动方向。
:param parent: 父级关系哈希表
:param start: 初始盘面的字符状态
:return: 数字移动方向
"""
ans = [str(TARGET)] # 状态列表
father = parent[str(TARGET)]
while father != start: # 遍历整个树，逆推还原解题过程
ans.append(father)
father = parent[father]
ans.append(str(start))
ans.reverse()
return get_list(ans)
def get_result(board: List[List[int]]):
"""
主函数，给定初始盘面，求数字移动方向。
:param board: 初始盘面
:return: 数字移动方向
"""
parent = get_parent(board)
ans = find_answer(parent, str(board))
return ans
gui.py
OCR识别和模拟点击部分。
import os
import time
from typing import List
import win32gui # 用于定位窗口
import pyautogui # 用于操作键盘
from PIL import ImageGrab # 用于截图
from paddleocr import PaddleOCR # 用于ocr识别
from ai import find_position
pyautogui.PAUSE = .5 # 按键间隔时间
TITLE = 'Fifteen' # 窗口标题
NUM_DIGITS = 25 # 宽度可容许的差异
def active_window():
hwnd = win32gui.FindWindow(0, TITLE)
if not hwnd:
raise SystemExit('未找到窗口')
win32gui.SetForegroundWindow(hwnd) # 高亮窗口
return hwnd
def get_window_image():
hwnd = active_window()
left, top, right, bottom = win32gui.GetWindowRect(hwnd)
# 这里的数据使用截图软件调的，不同显示屏可能不一样，请自行调整
left += 38
top += 92
right -= 38
bottom -= 68
image = ImageGrab.grab().crop((left, top, right, bottom)) # 对数字区进行截图
return image
def find_center():
return [(i, j) for i in range(3) for j in range(3)]
def get_center(rect):
left = rect[0][0]
right = rect[1][0]
top = rect[0][1]
bottom = rect[3][1]
x, y = (left + right) / 4, (top + bottom) / 4
return x // 61.3, y // 61.3 # 这里的数据使用截图软件调的，不同显示屏可能不一样，请自行调整
def get_board(image: str):
# 这里一定要用ch_ppocr_server模型，自带模型识别不出"7"字
ocr = PaddleOCR(det_model_dir='inference/ch_ppocr_server_v2.0_det_infer',
rec_model_dir='inference/ch_ppocr_server_v2.0_rec_infer',
use_angle_cls=True)
text = ocr.ocr(image, cls=True)
os.system('cls') # ocr识别有输出，cls清理控制台
# from pprint import pprint
# pprint(text)
d = {i[1][0]: get_center(i[0]) for i in text}
center_list = find_center()
res = [[0] * 3 for _ in range(3)]
for k, v in d.items():
k = int(k)
c, r = int(v[0]), int(v[1])
res[r][c] = k
for i in center_list:
if v == i:
center_list.remove(i)
break
assert len(center_list) == 1 # 空缺只有一个
y, x = center_list.pop() # 判断算法以列为项，XY要倒序
res[x][y] = -1
return res # 转二维列表
def press_key(board: List[List[int]], result: List[str]):
hwnd = active_window()
left, top, right, bottom = win32gui.GetWindowRect(hwnd)
left += 38
top += 92
time.sleep(.5)
y, x = find_position(-1, board) #
x, y = left + x * 61.3 + 61.3 // 2, top + y * 61.3 + 61.3 // 2
pyautogui.moveTo(x, y)
for i in result:
if i == 'left':
x += 61.3
elif i == 'right':
x -= 61.3
elif i == 'up':
y += 61.3
elif i == 'down':
y -= 61.3
else:
raise SystemExit('错误')
pyautogui.click(x, y)
main.py
入口程序。
from ai import get_result
from gui import get_window_image, get_board, press_key
def main():
image = get_window_image()
image = image.resize((184*2, 184*2))
image.save('crop.png')
print('窗口图像截图完成')
board = get_board('crop.png')
print(f'识别的盘面: {board}')
assert len(board) == 3
assert len(board[0]) == 3
result = get_result(board)
print('还原顺序计算完成')
press_key(board, result)
print('复原成功')
if __name__ == '__main__':
main()