引言
七巧板是中国传统智力玩具，由七块几何板组成：五块三角形、一块正方形和一块平行四边形。玩家需要将这七块板拼成各种指定形状。从算法角度看，七巧板是一个二维几何拼图问题，涉及旋转、翻转、平移等几何变换，以及空间覆盖的优化搜索。本文用Java实现一个七巧板自动拼图求解器，讲解几何变换的矩阵表示与贪心最优覆盖策略。
算法原理
几何变换矩阵
每块七巧板可以用一组二维坐标点表示。旋转 $\theta$ 角度可用旋转矩阵：
$$R(\theta) = \begin{bmatrix} \cos\theta & -\sin\theta \ \sin\theta & \cos\theta \end{bmatrix}$$
翻转可用矩阵 $F = \begin{bmatrix} -1 & 0 \ 0 & 1 \end{bmatrix}$。平移则直接加上偏移向量。
由于七巧板只涉及 $45^\circ$ 倍数旋转，可以用整数坐标精确表示，避免浮点误差。
贪心最优覆盖
求解策略采用回溯搜索 + 贪心启发式：每次选择面积最大的未放置板块，尝试将其放入目标轮廓的每个可行位置。优先放置大块可以减少后续搜索空间，因为大块的位置选择更少。
碰撞检测
使用网格化（Rasterization）方法：将目标区域和板块都映射到单位网格上，通过位运算快速检测重叠。
Java实现
import java.util.*;
/**
* 七巧板自动拼图求解器：几何变换 + 贪心回溯 + 网格碰撞检测
*/
public class TangramSolver {
static class Point {
int x, y;
Point(int x, int y) { this.x = x; this.y = y; }
Point rotate90() { return new Point(-y, x); }
Point rotate180() { return new Point(-x, -y); }
Point rotate270() { return new Point(y, -x); }
Point flip() { return new Point(-x, y); }
Point add(Point p) { return new Point(x + p.x, y + p.y); }
}
static class Piece {
String name;
List<Point> vertices; // 相对于原点的顶点
int area;
Piece(String name, List<Point> v) {
this.name = name;
this.vertices = v;
this.area = computeArea(v);
}
// 使用鞋带公式计算面积
int computeArea(List<Point> v) {
int a = 0;
int n = v.size();
for (int i = 0; i < n; i++) {
Point p1 = v.get(i), p2 = v.get((i + 1) % n);
a += p1.x * p2.y - p2.x * p1.y;
}
return Math.abs(a) / 2;
}
// 生成所有旋转和翻转变体（去重）
List<List<Point>> generateVariants() {
Set<String> seen = new HashSet<>();
List<List<Point>> variants = new ArrayList<>();
List<Point> current = new ArrayList<>(vertices);
for (int flip = 0; flip < 2; flip++) {
for (int rot = 0; rot < 4; rot++) {
String key = normalize(current);
if (!seen.contains(key)) {
seen.add(key);
variants.add(new ArrayList<>(current));
}
// 旋转90度
for (int i = 0; i < current.size(); i++) {
current.set(i, current.get(i).rotate90());
}
}
// 翻转
for (int i = 0; i < current.size(); i++) {
current.set(i, current.get(i).flip());
}
}
return variants;
}
String normalize(List<Point> v) {
// 平移到最小坐标为原点，然后排序
int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE;
for (Point p : v) {
minX = Math.min(minX, p.x);
minY = Math.min(minY, p.y);
}
List<Point> shifted = new ArrayList<>();
for (Point p : v) shifted.add(new Point(p.x - minX, p.y - minY));
shifted.sort((a, b) -> a.x != b.x ? a.x - b.x : a.y - b.y);
StringBuilder sb = new StringBuilder();
for (Point p : shifted) sb.append(p.x).append(",").append(p.y).append(";");
return sb.toString();
}
}
static class Board {
int width, height;
boolean[][] occupied;
Board(int w, int h) {
this.width = w; this.height = h;
this.occupied = new boolean[h][w];
}
Board copy() {
Board b = new Board(width, height);
for (int i = 0; i < height; i++)
System.arraycopy(occupied[i], 0, b.occupied[i], 0, width);
return b;
}
}
static class Placement {
String pieceName;
List<Point> points;
int offsetX, offsetY;
Placement(String n, List<Point> p, int ox, int oy) {
pieceName = n; points = p; offsetX = ox; offsetY = oy;
}
}
List<Piece> pieces;
List<Placement> solution;
public TangramSolver() {
pieces = createPieces();
solution = new ArrayList<>();
}
List<Piece> createPieces() {
List<Piece> list = new ArrayList<>();
// 两块大三角形（面积8）
list.add(new Piece("大三角1", Arrays.asList(new Point(0,0), new Point(4,0), new Point(0,4))));
list.add(new Piece("大三角2", Arrays.asList(new Point(0,0), new Point(4,0), new Point(0,4))));
// 一块中三角形（面积4）
list.add(new Piece("中三角", Arrays.asList(new Point(0,0), new Point(2,0), new Point(0,2))));
// 两块小三角形（面积2）
list.add(new Piece("小三角1", Arrays.asList(new Point(0,0), new Point(2,0), new Point(0,2))));
list.add(new Piece("小三角2", Arrays.asList(new Point(0,0), new Point(2,0), new Point(0,2))));
// 正方形（面积4）
list.add(new Piece("正方形", Arrays.asList(new Point(0,0), new Point(2,0), new Point(2,2), new Point(0,2))));
// 平行四边形（面积4）
list.add(new Piece("平行四边形", Arrays.asList(new Point(0,0), new Point(2,0), new Point(4,2), new Point(2,2))));
return list;
}
/**
* 将板块顶点网格化为占用格子
*/
Set<String> rasterize(List<Point> verts, int offsetX, int offsetY) {
Set<String> cells = new HashSet<>();
// 使用扫描线填充多边形
int minY = verts.stream().mapToInt(p -> p.y).min().orElse(0);
int maxY = verts.stream().mapToInt(p -> p.y).max().orElse(0);
for (int y = minY; y <= maxY; y++) {
List<Integer> xInts = new ArrayList<>();
int n = verts.size();
for (int i = 0; i < n; i++) {
Point p1 = verts.get(i), p2 = verts.get((i + 1) % n);
if ((p1.y <= y && p2.y > y) || (p2.y <= y && p1.y > y)) {
int xInt = p1.x + (y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y);
xInts.add(xInt);
}
}
Collections.sort(xInts);
for (int i = 0; i < xInts.size(); i += 2) {
for (int x = xInts.get(i); x <= xInts.get(i + 1); x++) {
cells.add((x + offsetX) + "," + (y + offsetY));
}
}
}
return cells;
}
/**
* 检查板块是否可以放置在指定位置
*/
boolean canPlace(Board board, List<Point> variant, int offsetX, int offsetY) {
Set<String> cells = rasterize(variant, offsetX, offsetY);
for (String cell : cells) {
String[] parts = cell.split(",");
int x = Integer.parseInt(parts[0]);
int y = Integer.parseInt(parts[1]);
if (x < 0 || x >= board.width || y < 0 || y >= board.height) return false;
if (board.occupied[y][x]) return false;
}
return true;
}
/**
* 将板块放置到棋盘上
*/
void place(Board board, List<Point> variant, int offsetX, int offsetY) {
Set<String> cells = rasterize(variant, offsetX, offsetY);
for (String cell : cells) {
String[] parts = cell.split(",");
int x = Integer.parseInt(parts[0]);
int y = Integer.parseInt(parts[1]);
board.occupied[y][x] = true;
}
}
/**
* 贪心回溯求解：优先放置面积大的板块
*/
public boolean solve(Board target, List<Piece> remaining) {
if (remaining.isEmpty()) {
// 检查是否完全覆盖
for (int y = 0; y < target.height; y++)
for (int x = 0; x < target.width; x++)
if (!target.occupied[y][x]) return false;
return true;
}
// 贪心：选择面积最大的板块
remaining.sort((a, b) -> b.area - a.area);
Piece piece = remaining.get(0);
List<Piece> nextRemaining = new ArrayList<>(remaining);
nextRemaining.remove(0);
List<List<Point>> variants = piece.generateVariants();
for (List<Point> variant : variants) {
// 计算边界框
int minX = variant.stream().mapToInt(p -> p.x).min().orElse(0);
int minY = variant.stream().mapToInt(p -> p.y).min().orElse(0);
int maxX = variant.stream().mapToInt(p -> p.x).max().orElse(0);
int maxY = variant.stream().mapToInt(p -> p.y).max().orElse(0);
int w = maxX - minX, h = maxY - minY;
for (int ox = -minX; ox < target.width - maxX; ox++) {
for (int oy = -minY; oy < target.height - maxY; oy++) {
Board next = target.copy();
if (canPlace(next, variant, ox, oy)) {
place(next, variant, ox, oy);
if (solve(next, nextRemaining)) {
solution.add(new Placement(piece.name, variant, ox, oy));
return true;
}
}
}
}
}
return false;
}
void printSolution() {
System.out.println("七巧板拼图方案:");
for (Placement p : solution) {
System.out.printf(" %s: 偏移(%d,%d)%n", p.pieceName, p.offsetX, p.offsetY);
}
}
public static void main(String[] args) {
// 目标：拼成一个8x8的正方形（七巧板总面积=32，但这里演示用4x4=16的小目标）
// 实际上标准七巧板拼成正方形是边长为4*sqrt(2)的倾斜正方形
// 这里简化为一个4x4的区域供演示
Board target = new Board(4, 4);
// 标记目标区域全部需要填充
for (int y = 0; y < 4; y++)
for (int x = 0; x < 4; x++)
target.occupied[y][x] = false;
TangramSolver solver = new TangramSolver();
// 选择部分板块拼成4x4区域
List<Piece> subset = new ArrayList<>();
subset.add(solver.pieces.get(0)); // 大三角1
subset.add(solver.pieces.get(2)); // 中三角
subset.add(solver.pieces.get(5)); // 正方形
subset.add(solver.pieces.get(6)); // 平行四边形
if (solver.solve(target, subset)) {
solver.printSolution();
} else {
System.out.println("未找到拼图方案");
}
}
}
复杂度分析
- 几何变换生成：每块板块最多8种变体（4种旋转 $\times$ 2种翻转，去重后通常少于8种）。
- 网格化：$O(V \times H)$，$V$ 为顶点数，$H$ 为边界框高度。
- 回溯搜索：$O(P! \times V^P \times W \times H)$，$P$ 为板块数，$V$ 为每块变体数，$W \times H$ 为目标区域大小。贪心策略（优先放置大块）有效降低实际搜索量。
总结
本文实现了七巧板自动拼图求解器，核心技术包括几何变换的矩阵表示、网格化碰撞检测和贪心回溯策略。通过优先放置面积较大的板块，算法在合理时间内找到可行解。该框架可扩展至任意多边形拼图问题，如拼图游戏、服装裁剪优化、建筑平面布局等实际应用场景。
