【油猴脚本】bing自动拼图 A*算法 Python/JavaScripts
本帖最后由 Cristy 于 2024-8-9 18:33 编辑# 以下是参考文章和引用的脚本
此脚本用于纯自动完成BING的拼图。
只是用来学习写着玩玩的。分享给大家。
**Bing官方拼图地址：**https://cn.bing.com/spotlight/imagepuzzle
脚本使用示例（JS版本）：
在这一次过程中我只是个学习者和拼装工，感谢各位大佬分享的资料
本次脚本的兴趣来源：**A*算法自动完成bing拼图 作者:
NoahPython：**https://www.bilibili.com/video/BV1ox421D7Kh/
A\*算法参考文章：**A*算法详解(个人认为最详细,最通俗易懂的一个版本) 作者StudyWinter：** https://blog.csdn.net/Zhouzi_heng/article/details/115035298
拼图移动脚本引用下面代码：**必应拼图小游戏键盘控件, 0.1 作者 haze alive：**https://update.greasyfork.org/scripts/474344/%E5%BF%85%E5%BA%94%E6%8B%BC%E5%9B%BE%E5%B0%8F%E6%B8%B8%E6%88%8F%E9%94%AE%E7%9B%98%E6%8E%A7%E4%BB%B6.user.js
# 下面是代码
## Python版本
### 该版本需借助 必应拼图小游戏键盘控件 监控键盘上下左右移动拼图，python代码只模拟按上下左右
```Python
# -*- coding: utf-8 -*-
"""
@file : bing拼图自动完成脚本.py
@Project : pythonToolsProject
@AuThor : auuuuu
@Email :
@Time : 2024/8/9 17:14
@Description:
"""
import heapq
import pyautogui
import time
import keyboard
class PuzzleState:
def __init__(self, board, zero_pos, moves):
self.board = board
self.zero_pos = zero_pos
self.moves = moves
def __lt__(self, other):
return len(self.moves) < len(other.moves)
def print_matrix(matrix):
for row in matrix:
print(', '.join(map(str, row)))
def find_blank_position(matrix):
for i in range(3):
for j in range(3):
if matrix == 0:
return i, j
return None
def is_solvable(puzzle):
inversions = 0
flat_puzzle =
for i in range(len(flat_puzzle)):
for j in range(i + 1, len(flat_puzzle)):
if flat_puzzle > flat_puzzle:
inversions += 1
return inversions % 2 == 0
def get_neighbors(state):
neighbors = []
x, y = state.zero_pos
directions = [(-1, 0, '下'), (1, 0, '上'), (0, -1, '右'), (0, 1, '左')]
for dx, dy, move in directions:
new_x, new_y = x + dx, y + dy
if 0 <= new_x < 3 and 0 <= new_y < 3:
new_board = for row in state.board]
new_board, new_board = new_board, new_board
neighbors.append(PuzzleState(new_board, (new_x, new_y), state.moves + ))
return neighbors
def a_star(start):
target = [, , ]
start_state = PuzzleState(start, find_blank_position(start), [])
priority_queue = []
heapq.heappush(priority_queue, start_state)
visited = set()
while priority_queue:
current_state = heapq.heappop(priority_queue)
current_tuple = tuple(map(tuple, current_state.board))
if current_state.board == target:
return current_state.moves
if current_tuple in visited:
continue
visited.add(current_tuple)
for neighbor in get_neighbors(current_state):
heapq.heappush(priority_queue, neighbor)
return []
def simulate_keypresses(moves):
print("自动按键模拟开始...")
time.sleep(1)# 等待1秒以便用户准备
for move in moves:
if move == '上':
pyautogui.press('up')
elif move == '下':
pyautogui.press('down')
elif move == '左':
pyautogui.press('left')
elif move == '右':
pyautogui.press('right')
time.sleep(0.5)# 每次按键之间间隔0.5秒
def main():
input_str = input("请输入九宫格的矩阵（用逗号分隔）：")
input_list = list(map(int, input_str.split(',')))
puzzle = for i in range(0, 9, 3)]
print("原始矩阵：")
print_matrix(puzzle)
if not is_solvable(puzzle):
print("这个拼图无法解决。")
return
moves = a_star(puzzle)
print("还原步骤：")
for move in moves:
print(move)
print("请按下 Ctrl 键以启动自动按键模拟...")
keyboard.wait('ctrl')# 等待按下 Ctrl 键
simulate_keypresses(moves)# 开始模拟按键
if __name__ == "__main__":
main()
```
## JS版本
### 浏览器控制台粘贴直接使用
```JavaScript
let tiles;
const loadElements = () => {
tiles = document.getElementById("tiles").children; // 加载拼图元素
console.log(tiles);
};
const inputArrowUp = () => {
for (let i = 0; i < tiles.length; i++) {
const next = i - 3; // 上移
if (checkTileByIndex(next)) {
tiles.click(); // 点击移动
break;
}
}
};
const inputArrowDown = () => {
for (let i = 0; i < tiles.length; i++) {
const next = i + 3; // 下移
if (checkTileByIndex(next)) {
tiles.click(); // 点击移动
break;
}
}
};
const inputArrowLeft = () => {
for (let i = 0; i < tiles.length; i++) {
const next = i - 1; // 左移
if (checkTileByIndex(next)) {
tiles.click(); // 点击移动
break;
}
}
};
const inputArrowRight = () => {
for (let i = 0; i < tiles.length; i++) {
const next = i + 1; // 右移
if (checkTileByIndex(next)) {
tiles.click(); // 点击移动
break;
}
}
};
const checkTileByIndex = (index) => {
if (index < 0 || index >= tiles.length) {
return false; // 超出边界
}
const targetChildren = tiles.children;
return targetChildren.length === 0; // 返回是否为空白
};
// 添加按钮到 Tampermonkey 菜单
const addButtonToMenu = () => {
const button = document.createElement('button');
button.innerText = '开始自动拼图';
button.style.position = 'fixed';
button.style.top = '10px';
button.style.right = '10px';
button.style.zIndex = 1000;
button.style.padding = '10px';
button.style.backgroundColor = '#4CAF50';
button.style.color = 'white';
button.style.border = 'none';
button.style.borderRadius = '5px';
button.style.cursor = 'pointer';
button.onclick = () => {
main(); // 点击按钮时调用主函数
};
document.body.appendChild(button);
};
// 拼图状态类
class PuzzleState {
constructor(board, zeroPos, moves) {
this.board = board; // 当前拼图状态
this.zeroPos = zeroPos; // 空白位置
this.moves = moves; // 移动记录
this.cost = this.calculateCost(); // 计算总代价 (g + h)
}
// 计算总代价 (g + h)
calculateCost() {
return this.moves.length + this.heuristic(); // g + h
}
// 启发式：曼哈顿距离
heuristic() {
let distance = 0;
const targetPositions = {
1: , 2: , 3: ,
4: , 5: , 6: ,
7: , 8: , 0:
};
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
const value = this.board;
if (value !== 0) {
const = targetPositions;
distance += Math.abs(targetX - i) + Math.abs(targetY - j);
}
}
}
return distance; // 返回总距离
}
// 优先队列比较函数
compareTo(other) {
return this.cost - other.cost; // 比较总代价
}
}
// 打印矩阵
function printMatrix(matrix) {
matrix.forEach(row => {
console.log(row.join(', ')); // 打印每一行
});
}
// 查找空白位置
function findBlankPosition(matrix) {
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (matrix === 0) {
return ; // 返回空白位置
}
}
}
return null;
}
// 检查拼图是否可解
function isSolvable(puzzle) {
let inversions = 0;
const flatPuzzle = puzzle.flat().filter(num => num !== 0);
for (let i = 0; i < flatPuzzle.length; i++) {
for (let j = i + 1; j < flatPuzzle.length; j++) {
if (flatPuzzle > flatPuzzle) {
inversions++; // 计算逆序对
}
}
}
return inversions % 2 === 0; // 可解条件
}
// 获取邻居状态
function getNeighbors(state) {
const neighbors = [];
const = state.zeroPos; // 当前空白位置
const directions = [[-1, 0, '下'], , , ];
for (const of directions) {
const newX = x + dx;
const newY = y + dy;
if (newX >= 0 && newX < 3 && newY >= 0 && newY < 3) {
const newBoard = state.board.map(row => row.slice());
, newBoard] = , newBoard];
neighbors.push(new PuzzleState(newBoard, , [...state.moves, move])); // 添加邻居状态
}
}
return neighbors;
}
// A* 算法
function aStar(start) {
const target = [, , ]; // 目标状态
const startState = new PuzzleState(start, findBlankPosition(start), []);
const priorityQueue = ;
const visited = new Set();
while (priorityQueue.length > 0) {
// 根据总代价排序优先队列
priorityQueue.sort((a, b) => a.compareTo(b));
const currentState = priorityQueue.shift(); // 取出当前状态
const currentTuple = JSON.stringify(currentState.board);
if (JSON.stringify(currentState.board) === JSON.stringify(target)) {
return currentState.moves; // 返回移动步骤
}
if (visited.has(currentTuple)) {
continue; // 如果已访问，跳过
}
visited.add(currentTuple);
for (const neighbor of getNeighbors(currentState)) {
priorityQueue.push(neighbor); // 添加邻居状态到优先队列
}
}
return []; // 如果没有找到解决方案，返回空数组
}
// 主函数
function main() {
// 获取 id 为 tiles 的 div
const tilesContainer = document.getElementById('tiles');
const results = [];
// 获取 tilesContainer 下的所有子 div
const childDivs = tilesContainer.children;
Array.from(childDivs).forEach(child => {
// 查找 .parentTile
const parentTiles = child.querySelectorAll('.parentTile');
if (parentTiles.length === 0) {
results.push('0'); // 如果没有 .parentTile，返回 0
} else {
let tileValues = [];
parentTiles.forEach(parent => {
// 查找 .tileNumber
const tileNumbers = parent.querySelectorAll('.tileNumber');
if (tileNumbers.length === 0) {
tileValues.push('0'); // 如果没有 .tileNumber，返回 0
} else {
// 获取 .tileNumber 的值
tileNumbers.forEach(tile => {
const value = tile.textContent.trim();
tileValues.push(value); // 收集每个 tileNumber 的值
console.log(`.tileNumber: ${value}`); // 打印每个 .tileNumber 的结果
});
}
});
// 拼接 tileNumber 的值
const tileResult = tileValues.join(',');
results.push(tileResult); // 将结果添加到结果数组中
console.log(`.parentTile: ${tileResult}`); // 打印对应的 .parentTile 的结果
}
});
const inputList = results.map(Number);
const puzzle = [];
for (let i = 0; i < 3; i++) {
puzzle.push(inputList.slice(i * 3, i * 3 + 3)); // 生成拼图矩阵
}
console.log("原始矩阵：");
printMatrix(puzzle);
if (!isSolvable(puzzle)) {
console.log("这个拼图无法解决。");
return; // 如果拼图不可解，结束
}
const moves = aStar(puzzle); // 获取还原步骤
console.log("还原步骤：");
moves.forEach((move, index) => {
setTimeout(() => {
console.log(move); // 打印每一步的移动
// 这里可以调用处理方法来执行每一步的移动
// 例如：executeMove(move);
if (move == "上") {
console.log("向上移动");
inputArrowUp();
}
if (move == "下") {
console.log("向下移动");
inputArrowDown();
}
if (move == "左") {
console.log("向左移动");
inputArrowLeft();
}
if (move == "右") {
console.log("向右移动");
inputArrowRight();
}
}, index * 500); // 每个移动之间停顿500ms
});
}
loadElements();
addButtonToMenu(); // 添加按钮
```
## 油猴脚本版本
### 需要浏览器中有油猴插件
``` javascript
// ==UserScript==
// @name 必应自动拼图
// @namespace Violentmonkey Scripts
// @match https://cn.bing.com/spotlight/*
// @grant none
// @version 1.0
// @author auuuu
// @description 2024/8/9 17:27:30
// ==/UserScript==
(function() {
'use strict';
let tiles;
const loadElements = () => {
tiles = document.getElementById("tiles").children; // 加载拼图元素
console.log(tiles);
};
const inputArrowUp = () => {
for (let i = 0; i < tiles.length; i++) {
const next = i - 3; // 上移
if (checkTileByIndex(next)) {
tiles.click(); // 点击移动
break;
}
}
};
const inputArrowDown = () => {
for (let i = 0; i < tiles.length; i++) {
const next = i + 3; // 下移
if (checkTileByIndex(next)) {
tiles.click(); // 点击移动
break;
}
}
};
const inputArrowLeft = () => {
for (let i = 0; i < tiles.length; i++) {
const next = i - 1; // 左移
if (checkTileByIndex(next)) {
tiles.click(); // 点击移动
break;
}
}
};
const inputArrowRight = () => {
for (let i = 0; i < tiles.length; i++) {
const next = i + 1; // 右移
if (checkTileByIndex(next)) {
tiles.click(); // 点击移动
break;
}
}
};
const checkTileByIndex = (index) => {
if (index < 0 || index >= tiles.length) {
return false; // 超出边界
}
const targetChildren = tiles.children;
return targetChildren.length === 0; // 返回是否为空白
};
// 添加按钮到 Tampermonkey 菜单
const addButtonToMenu = () => {
const button = document.createElement('button');
button.innerText = '开始自动拼图';
button.style.position = 'fixed';
button.style.top = '10px';
button.style.right = '10px';
button.style.zIndex = 1000;
button.style.padding = '10px';
button.style.backgroundColor = '#4CAF50';
button.style.color = 'white';
button.style.border = 'none';
button.style.borderRadius = '5px';
button.style.cursor = 'pointer';
button.onclick = () => {
main(); // 点击按钮时调用主函数
};
document.body.appendChild(button);
};
// 拼图状态类
class PuzzleState {
constructor(board, zeroPos, moves) {
this.board = board; // 当前拼图状态
this.zeroPos = zeroPos; // 空白位置
this.moves = moves; // 移动记录
this.cost = this.calculateCost(); // 计算总代价 (g + h)
}
// 计算总代价 (g + h)
calculateCost() {
return this.moves.length + this.heuristic(); // g + h
}
// 启发式：曼哈顿距离
heuristic() {
let distance = 0;
const targetPositions = {
1: , 2: , 3: ,
4: , 5: , 6: ,
7: , 8: , 0:
};
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
const value = this.board;
if (value !== 0) {
const = targetPositions;
distance += Math.abs(targetX - i) + Math.abs(targetY - j);
}
}
}
return distance; // 返回总距离
}
// 优先队列比较函数
compareTo(other) {
return this.cost - other.cost; // 比较总代价
}
}
// 打印矩阵
function printMatrix(matrix) {
matrix.forEach(row => {
console.log(row.join(', ')); // 打印每一行
});
}
// 查找空白位置
function findBlankPosition(matrix) {
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (matrix === 0) {
return ; // 返回空白位置
}
}
}
return null;
}
// 检查拼图是否可解
function isSolvable(puzzle) {
let inversions = 0;
const flatPuzzle = puzzle.flat().filter(num => num !== 0);
for (let i = 0; i < flatPuzzle.length; i++) {
for (let j = i + 1; j < flatPuzzle.length; j++) {
if (flatPuzzle > flatPuzzle) {
inversions++; // 计算逆序对
}
}
}
return inversions % 2 === 0; // 可解条件
}
// 获取邻居状态
function getNeighbors(state) {
const neighbors = [];
const = state.zeroPos; // 当前空白位置
const directions = [[-1, 0, '下'], , , ];
for (const of directions) {
const newX = x + dx;
const newY = y + dy;
if (newX >= 0 && newX < 3 && newY >= 0 && newY < 3) {
const newBoard = state.board.map(row => row.slice());
, newBoard] = , newBoard];
neighbors.push(new PuzzleState(newBoard, , [...state.moves, move])); // 添加邻居状态
}
}
return neighbors;
}
// A* 算法
function aStar(start) {
const target = [, , ]; // 目标状态
const startState = new PuzzleState(start, findBlankPosition(start), []);
const priorityQueue = ;
const visited = new Set();
while (priorityQueue.length > 0) {
// 根据总代价排序优先队列
priorityQueue.sort((a, b) => a.compareTo(b));
const currentState = priorityQueue.shift(); // 取出当前状态
const currentTuple = JSON.stringify(currentState.board);
if (JSON.stringify(currentState.board) === JSON.stringify(target)) {
return currentState.moves; // 返回移动步骤
}
if (visited.has(currentTuple)) {
continue; // 如果已访问，跳过
}
visited.add(currentTuple);
for (const neighbor of getNeighbors(currentState)) {
priorityQueue.push(neighbor); // 添加邻居状态到优先队列
}
}
return []; // 如果没有找到解决方案，返回空数组
}
// 主函数
function main() {
// 获取 id 为 tiles 的 div
const tilesContainer = document.getElementById('tiles');
const results = [];
// 获取 tilesContainer 下的所有子 div
const childDivs = tilesContainer.children;
Array.from(childDivs).forEach(child => {
// 查找 .parentTile
const parentTiles = child.querySelectorAll('.parentTile');
if (parentTiles.length === 0) {
results.push('0'); // 如果没有 .parentTile，返回 0
} else {
let tileValues = [];
parentTiles.forEach(parent => {
// 查找 .tileNumber
const tileNumbers = parent.querySelectorAll('.tileNumber');
if (tileNumbers.length === 0) {
tileValues.push('0'); // 如果没有 .tileNumber，返回 0
} else {
// 获取 .tileNumber 的值
tileNumbers.forEach(tile => {
const value = tile.textContent.trim();
tileValues.push(value); // 收集每个 tileNumber 的值
console.log(`.tileNumber: ${value}`); // 打印每个 .tileNumber 的结果
});
}
});
// 拼接 tileNumber 的值
const tileResult = tileValues.join(',');
results.push(tileResult); // 将结果添加到结果数组中
console.log(`.parentTile: ${tileResult}`); // 打印对应的 .parentTile 的结果
}
});
const inputList = results.map(Number);
const puzzle = [];
for (let i = 0; i < 3; i++) {
puzzle.push(inputList.slice(i * 3, i * 3 + 3)); // 生成拼图矩阵
}
console.log("原始矩阵：");
printMatrix(puzzle);
if (!isSolvable(puzzle)) {
console.log("这个拼图无法解决。");
return; // 如果拼图不可解，结束
}
const moves = aStar(puzzle); // 获取还原步骤
console.log("还原步骤：");
moves.forEach((move, index) => {
setTimeout(() => {
console.log(move); // 打印每一步的移动
// 这里可以调用处理方法来执行每一步的移动
// 例如：executeMove(move);
if (move == "上") {
console.log("向上移动");
inputArrowUp();
}
if (move == "下") {
console.log("向下移动");
inputArrowDown();
}
if (move == "左") {
console.log("向左移动");
inputArrowLeft();
}
if (move == "右") {
console.log("向右移动");
inputArrowRight();
}
}, index * 500); // 每个移动之间停顿500ms
});
}
loadElements();
addButtonToMenu(); // 添加按钮
})();
``` 很久之前就对A\*很感兴趣，但是一直不知道怎么使用。没想到必应的puzzle也能使用A\*，认真学习了一下，感谢大佬。
但是要优化一点的是，python版本的代码**没有使用**曼哈顿距离来设置代价，导致设置代价前后的运行时间差距**巨大**。
### 举例
#### 题目是：
#### 设置代价前：
> 当前排队 54579
> 正确解答： 耗费时间： 4.806465148925781
> 耗费步骤： 24
> 解答步骤： 下,左,上,上,右,下,右,下,左,左,上,上,右,下,右,下,左,左,上,右,右,上,左,左
#### 设置代价后：
>当前排队 1746
正确解答： 耗费时间： 0.03583407402038574
耗费步骤： 24
解答步骤： 下,左,上,上,右,下,右,下,左,左,上,上,右,下,右,下,左,左,上,右,右,上,左,左
所以参照了js版本的代码，将python类的代码修改一下即可：
```python
class PuzzleState:
def __init__(self, board, zero_pos, moves):
self.board = board
self.zero_pos = zero_pos
self.moves = moves
self.cost = self.calculate_cost()
# 计算总代价 (g + h)
def calculate_cost(self):
return len(self.moves) + self.heuristic()
# 启发式：曼哈顿距离
def heuristic(self):
distance = 0
target_positions = {
1: (0, 0), 2: (0, 1), 3: (0, 2),
4: (1, 0), 5: (1, 1), 6: (1, 2),
7: (2, 0), 8: (2, 1), 0: (2, 2)
}
for i in range(3):
for j in range(3):
value = self.board
if value != 0:
target_x, target_y = target_positions
distance += abs(target_x - i) + abs(target_y - j)
return distance# 返回总距离
def __lt__(self, other):
return self.cost < other.cost# 比较总代价
``` 感谢分享多版本源码 太厉害了,还有俩种版本写了一遍让我跃跃欲试的想用Java写一遍玩玩看 感谢分享，学习试玩 测试好用，有效，感谢分享 像大佬学习 谢谢分享，学习了 感谢分享 非常不错！ 挺有意思的拼图
页:
[1]
2