引言
拼图游戏是将一幅完整图像切割成若干碎片后重新组合的经典益智游戏。当碎片数量增加且允许旋转时，穷举所有组合的计算量会呈指数级增长。本文将使用Java实现基于模拟退火算法的拼图求解器，通过全局优化策略在庞大的解空间中寻找最优拼接方案，同时处理碎片的旋转对齐问题。
算法原理
拼图问题的数学建模
将一幅图像切割为 ( m \times n ) 的网格，每个碎片可以旋转0°、90°、180°、270°。定义状态为所有碎片的位置和旋转角度组合。目标是最大化相邻碎片边缘的匹配度。
边缘匹配度计算
对于两个相邻碎片，计算它们接触边缘的像素差异。使用均方误差（MSE）作为不兼容度度量：
[ \text{MSE}(e_1, e_2) = \frac{1}{k} \sum_{i=1}^{k} (p_{1i} – p_{2i})^2 ]
其中 ( p_{1i} ) 和 ( p_{2i} ) 是边缘对应位置的像素值，( k ) 是边缘长度。
模拟退火算法
模拟退火借鉴了金属退火的物理过程，通过温度参数控制接受劣解的概率：
- 初始状态：随机打乱碎片位置和旋转角度
- 邻域操作：随机交换两个碎片位置，或随机旋转一个碎片
- 能量函数：总不兼容度，即所有相邻碎片对MSE之和
- 接受准则：以概率 ( P = \exp(-\Delta E / T) ) 接受能量升高的状态
- 降温策略：温度按几何序列递减 ( T_{k+1} = \alpha \cdot T_k )
Java实现
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.*;
import javax.imageio.ImageIO;
/**
* 拼图碎片类，包含图像数据和旋转状态
*/
class PuzzlePiece {
private final int id;
private BufferedImage image;
private int rotation; // 0, 1, 2, 3 分别对应 0°, 90°, 180°, 270°
public PuzzlePiece(int id, BufferedImage image) {
this.id = id;
this.image = image;
this.rotation = 0;
}
public int getId() { return id; }
public int getRotation() { return rotation; }
public void setRotation(int rotation) { this.rotation = rotation & 3; }
public BufferedImage getImage() { return image; }
/**
* 获取指定方向的边缘像素数组
* direction: 0=上, 1=右, 2=下, 3=左
*/
public int[] getEdge(int direction) {
int actualDir = (direction - rotation + 4) & 3;
int w = image.getWidth();
int h = image.getHeight();
int[] edge;
switch (actualDir) {
case 0: // 上边缘
edge = new int[w];
for (int x = 0; x < w; x++) edge[x] = image.getRGB(x, 0);
break;
case 1: // 右边缘
edge = new int[h];
for (int y = 0; y < h; y++) edge[y] = image.getRGB(w - 1, y);
break;
case 2: // 下边缘
edge = new int[w];
for (int x = 0; x < w; x++) edge[x] = image.getRGB(x, h - 1);
break;
default: // 左边缘
edge = new int[h];
for (int y = 0; y < h; y++) edge[y] = image.getRGB(0, y);
break;
}
return edge;
}
/**
* 获取旋转后的对应边缘
* 当两块拼图相邻时，一块的右边缘对应另一块的左边缘（需考虑旋转）
*/
public int[] getMatchingEdge(int myDir, int otherRotation) {
// 计算在当前旋转下，myDir方向上的实际边缘
int actualDir = (myDir - rotation + 4) & 3;
// 考虑对方旋转后的匹配
int[] edge = getEdge(myDir);
// 如果对方旋转了180度，边缘需要反转
if ((otherRotation & 1) == 1) {
int[] reversed = new int[edge.length];
for (int i = 0; i < edge.length; i++) {
reversed[i] = edge[edge.length - 1 - i];
}
return reversed;
}
return edge;
}
}
/**
* 模拟退火拼图求解器
*/
public class PuzzleSolver {
private final int rows;
private final int cols;
private final List<PuzzlePiece> pieces;
private PuzzlePiece[][] board;
private final Random random = new Random();
// 模拟退火参数
private double initialTemperature = 10000.0;
private double coolingRate = 0.9995;
private int iterationsPerTemp = 1000;
public PuzzleSolver(int rows, int cols, List<PuzzlePiece> pieces) {
this.rows = rows;
this.cols = cols;
this.pieces = new ArrayList<>(pieces);
this.board = new PuzzlePiece[rows][cols];
initializeRandomBoard();
}
/**
* 随机初始化拼图板
*/
private void initializeRandomBoard() {
Collections.shuffle(pieces);
int idx = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
board[r][c] = pieces.get(idx++);
board[r][c].setRotation(random.nextInt(4));
}
}
}
/**
* 计算两个边缘的匹配误差（MSE）
*/
private double computeEdgeMSE(int[] edge1, int[] edge2) {
if (edge1.length != edge2.length) return Double.MAX_VALUE;
double sum = 0;
for (int i = 0; i < edge1.length; i++) {
int rgb1 = edge1[i];
int rgb2 = edge2[i];
int dr = ((rgb1 >> 16) & 0xFF) - ((rgb2 >> 16) & 0xFF);
int dg = ((rgb1 >> 8) & 0xFF) - ((rgb2 >> 8) & 0xFF);
int db = (rgb1 & 0xFF) - (rgb2 & 0xFF);
sum += dr * dr + dg * dg + db * db;
}
return sum / edge1.length;
}
/**
* 计算当前拼图板的总能量（不兼容度）
*/
private double computeTotalEnergy() {
double energy = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
// 右邻居
if (c + 1 < cols) {
energy += computeHorizontalMismatch(r, c, r, c + 1);
}
// 下邻居
if (r + 1 < rows) {
energy += computeVerticalMismatch(r, c, r + 1, c);
}
}
}
return energy;
}
/**
* 计算水平相邻的不匹配度
*/
private double computeHorizontalMismatch(int r1, int c1, int r2, int c2) {
PuzzlePiece left = board[r1][c1];
PuzzlePiece right = board[r2][c2];
int[] leftEdge = left.getEdge(1); // 右边缘
int[] rightEdge = right.getEdge(3); // 左边缘
return computeEdgeMSE(leftEdge, rightEdge);
}
/**
* 计算垂直相邻的不匹配度
*/
private double computeVerticalMismatch(int r1, int c1, int r2, int c2) {
PuzzlePiece top = board[r1][c1];
PuzzlePiece bottom = board[r2][c2];
int[] topEdge = top.getEdge(2); // 下边缘
int[] bottomEdge = bottom.getEdge(0); // 上边缘
return computeEdgeMSE(topEdge, bottomEdge);
}
/**
* 执行模拟退火优化
*/
public void solve() {
double temperature = initialTemperature;
double currentEnergy = computeTotalEnergy();
double bestEnergy = currentEnergy;
PuzzlePiece[][] bestBoard = copyBoard();
System.out.println("初始能量: " + currentEnergy);
int iteration = 0;
while (temperature > 1.0) {
for (int i = 0; i < iterationsPerTemp; i++) {
// 执行邻域操作
double deltaEnergy = performRandomMove();
// 接受准则
if (deltaEnergy < 0 || Math.random() < Math.exp(-deltaEnergy / temperature)) {
currentEnergy += deltaEnergy;
if (currentEnergy < bestEnergy) {
bestEnergy = currentEnergy;
bestBoard = copyBoard();
}
} else {
// 回退操作
undoLastMove();
}
iteration++;
}
temperature *= coolingRate;
if (iteration % 10000 == 0) {
System.out.printf("迭代 %d, 温度 %.2f, 当前能量 %.2f, 最优能量 %.2f%n",
iteration, temperature, currentEnergy, bestEnergy);
}
}
board = bestBoard;
System.out.println("最终最优能量: " + bestEnergy);
}
// 记录最后一次操作以支持回退
private int lastMoveType; // 0=交换, 1=旋转
private int lastR1, lastC1, lastR2, lastC2, lastRotation;
/**
* 执行随机邻域操作
* @return 能量变化量
*/
private double performRandomMove() {
double oldEnergy = computeLocalEnergy();
if (random.nextBoolean()) {
// 操作1：交换两个碎片的位置
lastMoveType = 0;
lastR1 = random.nextInt(rows);
lastC1 = random.nextInt(cols);
lastR2 = random.nextInt(rows);
lastC2 = random.nextInt(cols);
PuzzlePiece temp = board[lastR1][lastC1];
board[lastR1][lastC1] = board[lastR2][lastC2];
board[lastR2][lastC2] = temp;
} else {
// 操作2：随机旋转一个碎片
lastMoveType = 1;
lastR1 = random.nextInt(rows);
lastC1 = random.nextInt(cols);
lastRotation = board[lastR1][lastC1].getRotation();
board[lastR1][lastC1].setRotation(lastRotation + 1);
}
double newEnergy = computeLocalEnergy();
return newEnergy - oldEnergy;
}
/**
* 回退最后一次操作
*/
private void undoLastMove() {
if (lastMoveType == 0) {
PuzzlePiece temp = board[lastR1][lastC1];
board[lastR1][lastC1] = board[lastR2][lastC2];
board[lastR2][lastC2] = temp;
} else {
board[lastR1][lastC1].setRotation(lastRotation);
}
}
/**
* 计算局部能量（简化版本，仅计算受影响区域）
* 实际实现中应只计算与变动碎片相邻的边缘
*/
private double computeLocalEnergy() {
return computeTotalEnergy();
}
/**
* 复制当前拼图板状态
*/
private PuzzlePiece[][] copyBoard() {
PuzzlePiece[][] copy = new PuzzlePiece[rows][cols];
for (int r = 0; r < rows; r++) {
System.arraycopy(board[r], 0, copy[r], 0, cols);
}
return copy;
}
/**
* 生成结果图像
*/
public BufferedImage generateResultImage() {
int pieceWidth = board[0][0].getImage().getWidth();
int pieceHeight = board[0][0].getImage().getHeight();
BufferedImage result = new BufferedImage(cols * pieceWidth, rows * pieceHeight, BufferedImage.TYPE_INT_RGB);
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
BufferedImage pieceImg = board[r][c].getImage();
// 根据旋转角度绘制
int rotation = board[r][c].getRotation();
for (int y = 0; y < pieceHeight; y++) {
for (int x = 0; x < pieceWidth; x++) {
int srcX = x, srcY = y;
switch (rotation) {
case 1: srcX = pieceHeight - 1 - y; srcY = x; break;
case 2: srcX = pieceWidth - 1 - x; srcY = pieceHeight - 1 - y; break;
case 3: srcX = y; srcY = pieceWidth - 1 - x; break;
}
int rgb = pieceImg.getRGB(srcX, srcY);
result.setRGB(c * pieceWidth + x, r * pieceHeight + y, rgb);
}
}
}
}
return result;
}
/**
* 主程序：演示拼图求解
*/
public static void main(String[] args) throws Exception {
// 示例：创建3x3的测试拼图
int rows = 3, cols = 3;
BufferedImage original = new BufferedImage(300, 300, BufferedImage.TYPE_INT_RGB);
// 填充渐变颜色作为测试图像
for (int y = 0; y < 300; y++) {
for (int x = 0; x < 300; x++) {
int rgb = ((x * 255 / 300) << 16) | ((y * 255 / 300) << 8) | (128);
original.setRGB(x, y, rgb);
}
}
// 切割图像
List<PuzzlePiece> pieces = new ArrayList<>();
int pieceW = 100, pieceH = 100;
int id = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
BufferedImage piece = original.getSubimage(c * pieceW, r * pieceH, pieceW, pieceH);
pieces.add(new PuzzlePiece(id++, piece));
}
}
PuzzleSolver solver = new PuzzleSolver(rows, cols, pieces);
solver.solve();
BufferedImage result = solver.generateResultImage();
ImageIO.write(result, "png", new File("solved_puzzle.png"));
System.out.println("拼图求解完成，结果已保存至 solved_puzzle.png");
}
}
算法优化策略
1. 局部能量计算优化
在实际应用中，每次交换或旋转只影响相邻碎片的匹配度。因此可以只计算变动区域周围的能量变化，将单次评估复杂度从 ( O(mn) ) 降到 ( O(1) )。
2. 多尺度退火策略
先使用粗粒度拼图（较大碎片）进行初步对齐，再逐步细化到更小的碎片尺寸。这种分层策略可以显著减少陷入局部最优的概率。
3. 自适应温度调度
根据能量变化的历史统计动态调整冷却率：当能量长期停滞时提高温度以跳出局部最优，当能量快速下降时加速冷却。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | ( O(K \cdot mn) ) | ( K ) 为迭代次数，每次计算能量需遍历所有相邻对 |
| 空间复杂度 | ( O(mn) ) | 存储拼图板状态和碎片数据 |
| 局部优化后 | ( O(K) ) | 只计算变动区域的能量差 |
总结
本文通过模拟退火算法解决了带旋转的拼图求解问题。核心思路是将拼图重组建模为组合优化问题，利用模拟退火的全局搜索能力在庞大的解空间中寻找最优排列。通过边缘MSE匹配度度量和随机邻域操作（交换位置与旋转），算法能够有效地收敛到高质量的拼接方案。
模拟退火的关键在于温度调度策略的设计：初始温度要足够高以允许充分探索，冷却率要足够慢以保证收敛。对于实际应用，建议结合多尺度策略和局部能量优化来提升求解效率和结果质量。
