用python玩3x3数字华容道_如何利用python完成3*3华容道程序编写

准备工作

系统

由于使用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
1
2
3
4
5
6

算法分析

计算解法

1. 使用bfs暴力穷举搜索，求出可以由当前状态变换而成的2-4个状态，并记录父级关系哈希表(模拟一颗树)，直到还原为止。
2. 根据父级关系哈希表逆推还原解题步骤。

OCR

1. 使用paddleocr获取盘面信息。
2. 对中心点标注，没有的则为空缺点。

项目结构

代码

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
   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22