引言
七巧板（Tangram）是中国古代流传至今的经典拼图玩具，由七块几何板组成：五块三角形、一块正方形和一块平行四边形。玩家需要将这七块板拼合成各种指定图形。本文用Java实现七巧板自动求解器，讲解计算几何中的多边形覆盖判定，以及带旋转与翻转的回溯搜索算法如何高效寻找拼合方案。
问题建模
将七巧板的每一块抽象为多边形（以顶点坐标序列表示），目标是在给定轮廓内无重叠地放置全部七块板。
七块板的标准尺寸（设大三角形直角边长为1）：
– 2块大三角形：直角边长1，面积 0.25
– 1块中三角形：直角边长 √2/2，面积 0.125
– 2块小三角形：直角边长0.5，面积 0.0625
– 1块正方形：边长 √2/4，面积 0.0625
– 1块平行四边形：边长0.5和√2/4，面积 0.0625
总面积恒为1，因此目标轮廓面积也必须为1才有解。
核心算法一：多边形表示与几何变换
import java.util.*;
public class TangramSolver {
/**
* 二维点
*/
static class Point {
double x, y;
Point(double x, double y) { this.x = x; this.y = y; }
Point rotate(double angle) {
double cos = Math.cos(angle);
double sin = Math.sin(angle);
return new Point(x * cos - y * sin, x * sin + y * cos);
}
Point translate(double dx, double dy) {
return new Point(x + dx, y + dy);
}
@Override public boolean equals(Object o) {
if (!(o instanceof Point)) return false;
Point p = (Point) o;
return Math.abs(x - p.x) < 1e-9 && Math.abs(y - p.y) < 1e-9;
}
}
/**
* 七巧板块：由顶点序列定义的多边形
*/
static class Piece {
String name;
List<Point> vertices; // 原始顶点（逆时针）
double area;
Piece(String name, List<Point> vertices) {
this.name = name;
this.vertices = vertices;
this.area = calculatePolygonArea(vertices);
}
/**
* 生成该板块的所有不同旋转/翻转形态
* 七巧板块通常有8种对称变换（4个旋转角度 × 是否翻转）
*/
List<List<Point>> generateTransforms() {
List<List<Point>> transforms = new ArrayList<>();
Set<String> seen = new HashSet<>();
double[] angles = {0, Math.PI/4, Math.PI/2, 3*Math.PI/4,
Math.PI, 5*Math.PI/4, 3*Math.PI/2, 7*Math.PI/4};
for (double angle : angles) {
// 原形态旋转
List<Point> rotated = rotatePiece(vertices, angle);
String key = normalizeKey(rotated);
if (!seen.contains(key)) {
seen.add(key);
transforms.add(rotated);
}
// 翻转后旋转
List<Point> flipped = flipPiece(vertices);
List<Point> flippedRotated = rotatePiece(flipped, angle);
String fkey = normalizeKey(flippedRotated);
if (!seen.contains(fkey)) {
seen.add(fkey);
transforms.add(flippedRotated);
}
}
return transforms;
}
List<Point> rotatePiece(List<Point> pts, double angle) {
List<Point> result = new ArrayList<>();
for (Point p : pts) result.add(p.rotate(angle));
return result;
}
List<Point> flipPiece(List<Point> pts) {
List<Point> result = new ArrayList<>();
for (Point p : pts) result.add(new Point(-p.x, p.y)); // 沿Y轴翻转
return result;
}
String normalizeKey(List<Point> pts) {
StringBuilder sb = new StringBuilder();
for (Point p : pts) sb.append(String.format("%.6f,%.6f;", p.x, p.y));
return sb.toString();
}
}
/**
* 计算多边形面积（鞋带公式）
*/
static double calculatePolygonArea(List<Point> vertices) {
int n = vertices.size();
double area = 0;
for (int i = 0; i < n; i++) {
Point p1 = vertices.get(i);
Point p2 = vertices.get((i + 1) % n);
area += p1.x * p2.y - p2.x * p1.y;
}
return Math.abs(area) / 2.0;
}
/**
* 创建标准七巧板的七块板
*/
static List<Piece> createStandardPieces() {
List<Piece> pieces = new ArrayList<>();
// 大三角形（2块）
pieces.add(new Piece("大三角1", Arrays.asList(
new Point(0, 0), new Point(1, 0), new Point(0, 1)
)));
pieces.add(new Piece("大三角2", Arrays.asList(
new Point(0, 0), new Point(1, 0), new Point(0, 1)
)));
// 中三角形
pieces.add(new Piece("中三角", Arrays.asList(
new Point(0, 0), new Point(0.5, 0.5), new Point(0, 1)
)));
// 小三角形（2块）
pieces.add(new Piece("小三角1", Arrays.asList(
new Point(0, 0), new Point(0.5, 0), new Point(0, 0.5)
)));
pieces.add(new Piece("小三角2", Arrays.asList(
new Point(0, 0), new Point(0.5, 0), new Point(0, 0.5)
)));
// 正方形
pieces.add(new Piece("正方形", Arrays.asList(
new Point(0, 0), new Point(0.25, 0.25), new Point(0, 0.5), new Point(-0.25, 0.25)
)));
// 平行四边形
pieces.add(new Piece("平行四边形", Arrays.asList(
new Point(0, 0), new Point(0.5, 0), new Point(0.75, 0.25), new Point(0.25, 0.25)
)));
return pieces;
}
核心算法二：多边形碰撞与覆盖检测
判断两块七巧板是否重叠，以及放置后的板是否完全在目标轮廓内，是回溯搜索的关键剪枝条件。
/**
* 判断点 p 是否在多边形 poly 内部（射线法）
*/
static boolean pointInPolygon(Point p, List<Point> poly) {
int n = poly.size();
boolean inside = false;
for (int i = 0, j = n - 1; i < n; j = i++) {
Point pi = poly.get(i), pj = poly.get(j);
if (((pi.y > p.y) != (pj.y > p.y)) &&
(p.x < (pj.x - pi.x) * (p.y - pi.y) / (pj.y - pi.y) + pi.x)) {
inside = !inside;
}
}
return inside;
}
/**
* 判断两条线段是否相交（跨立实验）
*/
static boolean segmentsIntersect(Point a1, Point a2, Point b1, Point b2) {
double d1 = direction(b1, b2, a1);
double d2 = direction(b1, b2, a2);
double d3 = direction(a1, a2, b1);
double d4 = direction(a1, a2, b2);
if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) {
return true;
}
// 检查共线情况
if (d1 == 0 && onSegment(b1, b2, a1)) return true;
if (d2 == 0 && onSegment(b1, b2, a2)) return true;
if (d3 == 0 && onSegment(a1, a2, b1)) return true;
if (d4 == 0 && onSegment(a1, a2, b2)) return true;
return false;
}
static double direction(Point p1, Point p2, Point p3) {
return (p3.x - p1.x) * (p2.y - p1.y) - (p2.x - p1.x) * (p3.y - p1.y);
}
static boolean onSegment(Point p1, Point p2, Point p3) {
return Math.min(p1.x, p2.x) <= p3.x && p3.x <= Math.max(p1.x, p2.x) &&
Math.min(p1.y, p2.y) <= p3.y && p3.y <= Math.max(p1.y, p2.y);
}
/**
* 判断两个多边形是否相交（边界相交或一方包含另一方顶点）
*/
static boolean polygonsIntersect(List<Point> poly1, List<Point> poly2) {
// 检查边界是否相交
int n1 = poly1.size(), n2 = poly2.size();
for (int i = 0; i < n1; i++) {
Point a1 = poly1.get(i), a2 = poly1.get((i + 1) % n1);
for (int j = 0; j < n2; j++) {
Point b1 = poly2.get(j), b2 = poly2.get((j + 1) % n2);
if (segmentsIntersect(a1, a2, b1, b2)) return true;
}
}
// 检查一个多边形的顶点是否在另一个内部
for (Point p : poly1) {
if (pointInPolygon(p, poly2)) return true;
}
for (Point p : poly2) {
if (pointInPolygon(p, poly1)) return true;
}
return false;
}
/**
* 将板块的变换形态平移到指定位置
*/
static List<Point> placePiece(List<Point> transformed, double dx, double dy) {
List<Point> placed = new ArrayList<>();
for (Point p : transformed) {
placed.add(p.translate(dx, dy));
}
return placed;
}
核心算法三：带旋转的回溯搜索
通过DFS枚举每块板的所有旋转形态和放置位置，利用碰撞检测进行剪枝。
/**
* 回溯搜索求解七巧板拼合
* @param target 目标轮廓多边形
* @param pieces 待放置的板块列表
* @return 每种板块的放置方案，若无解返回null
*/
static Map<String, PlacedPiece> solveTangram(List<Point> target, List<Piece> pieces) {
Map<String, PlacedPiece> solution = new HashMap<>();
boolean[] used = new boolean[pieces.size()];
// 预计算每块板的所有不同变换
List<List<List<Point>>> transforms = new ArrayList<>();
for (Piece p : pieces) transforms.add(p.generateTransforms());
// 目标轮廓的边界框，用于限制搜索范围
double minX = target.stream().mapToDouble(p -> p.x).min().orElse(0);
double maxX = target.stream().mapToDouble(p -> p.x).max().orElse(1);
double minY = target.stream().mapToDouble(p -> p.y).min().orElse(0);
double maxY = target.stream().mapToDouble(p -> p.y).max().orElse(1);
if (backtrack(target, pieces, transforms, used, solution, 0,
minX, maxX, minY, maxY)) {
return solution;
}
return null;
}
static boolean backtrack(List<Point> target, List<Piece> pieces,
List<List<List<Point>>> transforms,
boolean[] used,
Map<String, PlacedPiece> solution,
int placedCount,
double minX, double maxX, double minY, double maxY) {
if (placedCount == pieces.size()) {
return true; // 全部放置完成
}
// 选择未使用的板块（优先选择变换少的，减少分支）
int pieceIdx = -1;
int minTransforms = Integer.MAX_VALUE;
for (int i = 0; i < pieces.size(); i++) {
if (!used[i] && transforms.get(i).size() < minTransforms) {
minTransforms = transforms.get(i).size();
pieceIdx = i;
}
}
if (pieceIdx == -1) return false;
used[pieceIdx] = true;
Piece piece = pieces.get(pieceIdx);
// 枚举所有变换
for (List<Point> transform : transforms.get(pieceIdx)) {
// 计算变换后板块的大致中心
double cx = transform.stream().mapToDouble(p -> p.x).average().orElse(0);
double cy = transform.stream().mapToDouble(p -> p.y).average().orElse(0);
// 在目标区域内枚举放置位置（步长0.25）
for (double dx = minX - cx; dx <= maxX - cx; dx += 0.25) {
for (double dy = minY - cy; dy <= maxY - cy; dy += 0.25) {
List<Point> placed = placePiece(transform, dx, dy);
// 剪枝1：板块必须完全在目标轮廓内
boolean inside = true;
for (Point p : placed) {
if (!pointInPolygon(p, target)) {
inside = false;
break;
}
}
if (!inside) continue;
// 剪枝2：不能与其他已放置板块重叠
boolean overlap = false;
for (PlacedPiece other : solution.values()) {
if (polygonsIntersect(placed, other.vertices)) {
overlap = true;
break;
}
}
if (overlap) continue;
// 放置当前板块
solution.put(piece.name, new PlacedPiece(piece.name, placed, dx, dy));
if (backtrack(target, pieces, transforms, used, solution,
placedCount + 1, minX, maxX, minY, maxY)) {
return true;
}
solution.remove(piece.name);
}
}
}
used[pieceIdx] = false;
return false;
}
static class PlacedPiece {
String name;
List<Point> vertices;
double x, y; // 平移量
PlacedPiece(String name, List<Point> vertices, double x, double y) {
this.name = name; this.vertices = vertices; this.x = x; this.y = y;
}
}
复杂度分析与优化
| 算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 多边形碰撞检测 | O(V₁ × V₂) | O(1) |
| 回溯搜索（朴素） | O(7! × 8⁷ × G²) | O(7) |
| 带剪枝回溯 | 实际远低于上界 | O(7) |
其中 V 为多边形顶点数，G 为网格离散化粒度。七巧板求解的搜索空间虽大，但通过以下剪枝策略实际运行很快：
1. 面积守恒：目标轮廓面积必须为1
2. 凸包约束：每块板必须完全在目标轮廓内
3. 边界对齐：七巧板边长只有有限几种，可以大幅减少位置枚举
4. MRV启发式：优先放置变换少的板块
总结
七巧板自动求解是计算几何与组合搜索的经典结合。多边形表示与射线法为碰撞检测提供了精确基础，回溯搜索则 systematically 遍历所有可能的拼合方式。在实际应用中，还可以引入约束传播（如面积约束、角度约束）进一步缩减搜索空间。七巧板的魅力在于简单规则下蕴含的无限可能——而这正是算法之美所在。
