每日算法 — 使用java实现七巧板：几何旋转变换与回溯拼图求解

引言

七巧板（Tangram）是中国古代流传至今的经典益智玩具，由七块几何板组成：五块等腰直角三角形（两块大三角形、一块中三角形、两块小三角形）、一块正方形和一块平行四边形。这七块板可以拼出上千种不同的图形，从简单的几何形状到复杂的人物动物。本文将用Java实现一个七巧板自动求解系统，核心算法涵盖二维几何旋转变换、多边形碰撞检测以及回溯搜索三大技术，帮助读者理解如何用计算几何与搜索算法解决经典拼图问题。

七巧板的几何建模

1. 基本几何定义

七巧板的所有板块都基于一个单位正方形的对角线分割：

大三角形：直角边 = 1，面积 = 1/4
中三角形：直角边 = √2/2，面积 = 1/8
小三角形：直角边 = 1/2，面积 = 1/16
正方形：边长 = √2/4，面积 = 1/8
平行四边形：底 = 1/2，高 = 1/4，面积 = 1/8

总面积恰好为1（假设外框为单位正方形）。

2. 多边形表示

import java.util.*;

/**
 * 二维点，支持旋转变换
 */
public class Point {
    public final double x, y;

    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    /**
     * 绕原点旋转指定角度（弧度）
     */
    public 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);
    }

    /**
     * 绕指定中心点旋转
     */
    public Point rotateAround(Point center, double angle) {
        return this.subtract(center).rotate(angle).add(center);
    }

    public Point add(Point p) {
        return new Point(x + p.x, y + p.y);
    }

    public Point subtract(Point p) {
        return new Point(x - p.x, y - p.y);
    }

    public Point multiply(double s) {
        return new Point(x * s, y * s);
    }

    public double dot(Point p) {
        return x * p.x + y * p.y;
    }

    public double cross(Point p) {
        return x * p.y - y * p.x;
    }

    public double distanceTo(Point p) {
        double dx = x - p.x, dy = y - p.y;
        return Math.sqrt(dx * dx + dy * dy);
    }

    @Override
    public String toString() {
        return String.format("(%.3f, %.3f)", x, y);
    }
}

/**
 * 多边形板块，由有序顶点定义
 */
public class Piece {
    private final String name;
    private final Point[] baseVertices; // 基准形状（原点为中心）
    private Point position; // 当前位置（平移量）
    private double rotation; // 当前旋转角度（弧度）
    private boolean flipped; // 是否翻转（平行四边形专用）

    public Piece(String name, Point[] vertices) {
        this.name = name;
        this.baseVertices = vertices;
        this.position = new Point(0, 0);
        this.rotation = 0;
        this.flipped = false;
    }

    /**
     * 获取当前变换后的顶点
     */
    public Point[] getTransformedVertices() {
        Point[] result = new Point[baseVertices.length];
        for (int i = 0; i < baseVertices.length; i++) {
            Point v = baseVertices[i];
            if (flipped) {
                v = new Point(-v.x, v.y); // X轴镜像翻转
            }
            result[i] = v.rotate(rotation).add(position);
        }
        return result;
    }

    public void setTransform(Point pos, double rot, boolean flip) {
        this.position = pos;
        this.rotation = rot;
        this.flipped = flip;
    }

    public String getName() { return name; }
    public Point getPosition() { return position; }
    public double getRotation() { return rotation; }

    /**
     * 计算多边形面积（有符号，可用于方向判断）
     */
    public double getArea() {
        Point[] v = baseVertices;
        double area = 0;
        for (int i = 0; i < v.length; i++) {
            int j = (i + 1) % v.length;
            area += v[i].cross(v[j]);
        }
        return Math.abs(area) / 2;
    }

    @Override
    public Piece clone() {
        Piece p = new Piece(name, baseVertices);
        p.setTransform(position, rotation, flipped);
        return p;
    }
}

3. 七巧板板块工厂

/**
 * 七巧板板块工厂，创建标准七巧板
 * 基于单位正方形 [0,1] × [0,1]
 */
public class TangramFactory {

    /**
     * 创建完整的七巧板套装
     */
    public static Piece[] createStandardSet() {
        Piece[] pieces = new Piece[7];

        // 大三角形 × 2（直角边 = 1/2）
        pieces[0] = createTriangle("大三角1", 0.5);
        pieces[1] = createTriangle("大三角2", 0.5);

        // 中三角形（直角边 = √2/4 ≈ 0.3536）
        pieces[2] = createTriangle("中三角", Math.sqrt(2) / 4);

        // 小三角形 × 2（直角边 = 1/4）
        pieces[3] = createTriangle("小三角1", 0.25);
        pieces[4] = createTriangle("小三角2", 0.25);

        // 正方形（边长 = √2/4）
        pieces[5] = createSquare();

        // 平行四边形
        pieces[6] = createParallelogram();

        return pieces;
    }

    private static Piece createTriangle(String name, double leg) {
        // 等腰直角三角形，直角在原点
        Point[] vertices = {
            new Point(0, 0),
            new Point(leg, 0),
            new Point(0, leg)
        };
        return new Piece(name, vertices);
    }

    private static Piece createSquare() {
        double s = Math.sqrt(2) / 4;
        // 正方形中心在原点
        Point[] vertices = {
            new Point(-s/2, -s/2),
            new Point(s/2, -s/2),
            new Point(s/2, s/2),
            new Point(-s/2, s/2)
        };
        return new Piece("正方形", vertices);
    }

    private static Piece createParallelogram() {
        double a = 0.25; // 短边
        double b = 0.25; // 另一边
        double angle = Math.PI / 4; // 45度夹角

        Point[] vertices = {
            new Point(0, 0),
            new Point(a, 0),
            new Point(a + b * Math.cos(angle), b * Math.sin(angle)),
            new Point(b * Math.cos(angle), b * Math.sin(angle))
        };
        return new Piece("平行四边形", vertices);
    }
}

几何碰撞检测

分离轴定理（SAT）

判断两个凸多边形是否碰撞的经典算法：

/**
 * 分离轴定理（Separating Axis Theorem）碰撞检测
 * 适用于任意凸多边形
 */
public class CollisionDetector {

    /**
     * 检测两个多边形是否相交
     */
    public static boolean intersect(Piece a, Piece b) {
        Point[] va = a.getTransformedVertices();
        Point[] vb = b.getTransformedVertices();

        // 获取所有分离轴（两多边形各边的法线）
        List<Point> axes = new ArrayList<>();
        axes.addAll(getAxes(va));
        axes.addAll(getAxes(vb));

        // 在每个轴上检测投影是否重叠
        for (Point axis : axes) {
            if (!overlapOnAxis(va, vb, axis)) {
                return false; // 存在分离轴，不相交
            }
        }

        return true; // 所有轴上都重叠，相交
    }

    /**
     * 获取多边形的所有边法线（作为分离轴）
     */
    private static List<Point> getAxes(Point[] vertices) {
        List<Point> axes = new ArrayList<>();
        for (int i = 0; i < vertices.length; i++) {
            Point p1 = vertices[i];
            Point p2 = vertices[(i + 1) % vertices.length];
            Point edge = p2.subtract(p1);
            // 法线：(-dy, dx)
            Point normal = new Point(-edge.y, edge.x);
            double len = Math.sqrt(normal.x * normal.x + normal.y * normal.y);
            axes.add(new Point(normal.x / len, normal.y / len));
        }
        return axes;
    }

    /**
     * 检测两个多边形在指定轴上的投影是否重叠
     */
    private static boolean overlapOnAxis(Point[] a, Point[] b, Point axis) {
        double[] projA = project(a, axis);
        double[] projB = project(b, axis);

        return !(projA[1] < projB[0] || projB[1] < projA[0]);
    }

    /**
     * 多边形在轴上的投影 [min, max]
     */
    private static double[] project(Point[] vertices, Point axis) {
        double min = vertices[0].dot(axis);
        double max = min;

        for (int i = 1; i < vertices.length; i++) {
            double p = vertices[i].dot(axis);
            min = Math.min(min, p);
            max = Math.max(max, p);
        }

        return new double[]{min, max};
    }

    /**
     * 检测点是否在多边形内部（射线法）
     */
    public static boolean pointInPolygon(Point p, Point[] polygon) {
        boolean inside = false;
        for (int i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
            Point pi = polygon[i], pj = polygon[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;
    }

    /**
     * 检测多边形是否完全在目标边界框内
     */
    public static boolean insideBounds(Piece piece, double minX, double minY, 
                                        double maxX, double maxY) {
        for (Point v : piece.getTransformedVertices()) {
            if (v.x < minX || v.x > maxX || v.y < minY || v.y > maxY) {
                return false;
            }
        }
        return true;
    }
}

回溯搜索求解器

1. 问题建模

七巧板求解问题可建模为约束满足问题（CSP）：
– 变量：7个板块的放置状态（位置 + 旋转 + 翻转）
– 约束：
1. 板块之间不能重叠（硬约束）
2. 所有板块必须完全在目标轮廓内（硬约束）
3. 板块总面积等于目标轮廓面积（剪枝条件）

2. 搜索算法

/**
 * 七巧板回溯求解器
 * 使用深度优先搜索 + 约束传播 + 启发式排序
 */
public class TangramSolver {
    private final double STEP = 0.125; // 位置搜索步长（基于七巧板边长）
    private final 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
    };

    private List<Solution> solutions = new ArrayList<>();
    private int maxSolutions;
    private int nodeCount = 0;

    public TangramSolver(int maxSolutions) {
        this.maxSolutions = maxSolutions;
    }

    /**
     * 求解七巧板拼图
     * @param targetOutline 目标轮廓多边形
     * @param pieces 七巧板板块
     * @return 所有找到的解
     */
    public List<Solution> solve(Point[] targetOutline, Piece[] pieces) {
        solutions.clear();
        nodeCount = 0;

        // 按面积从大到小排序（启发式：先放大的板块）
        Piece[] sorted = pieces.clone();
        Arrays.sort(sorted, (a, b) -> Double.compare(b.getArea(), a.getArea()));

        // 计算目标边界框
        double minX = Double.MAX_VALUE, minY = Double.MAX_VALUE;
        double maxX = -Double.MAX_VALUE, maxY = -Double.MAX_VALUE;
        for (Point p : targetOutline) {
            minX = Math.min(minX, p.x);
            minY = Math.min(minY, p.y);
            maxX = Math.max(maxX, p.x);
            maxY = Math.max(maxY, p.y);
        }

        // 计算目标面积（用于剪枝）
        double targetArea = polygonArea(targetOutline);
        double piecesArea = Arrays.stream(sorted).mapToDouble(Piece::getArea).sum();

        if (Math.abs(targetArea - piecesArea) > 1e-6) {
            System.out.println("面积不匹配：目标=" + targetArea + ", 板块=" + piecesArea);
            return solutions;
        }

        // 开始回溯搜索
        Piece[] current = new Piece[sorted.length];
        for (int i = 0; i < sorted.length; i++) {
            current[i] = sorted[i].clone();
        }

        backtrack(0, current, targetOutline, minX, minY, maxX, maxY);

        return solutions;
    }

    private void backtrack(int index, Piece[] current, Point[] targetOutline,
                           double minX, double minY, double maxX, double maxY) {
        nodeCount++;

        if (solutions.size() >= maxSolutions) return;

        if (index == current.length) {
            // 找到一个完整解
            solutions.add(new Solution(current.clone()));
            System.out.println("找到解 #" + solutions.size() + " (搜索节点: " + nodeCount + ")");
            return;
        }

        Piece piece = current[index];

        // 生成候选位置（网格采样）
        for (double x = minX; x <= maxX; x += STEP) {
            for (double y = minY; y <= maxY; y += STEP) {
                // 尝试所有旋转角度
                for (double angle : ANGLES) {
                    // 平行四边形可以翻转
                    boolean[] flipOptions = piece.getName().contains("平行") ? 
                        new boolean[]{false, true} : new boolean[]{false};

                    for (boolean flip : flipOptions) {
                        piece.setTransform(new Point(x, y), angle, flip);

                        // 约束检查
                        if (!CollisionDetector.insideBounds(piece, minX, minY, maxX, maxY)) {
                            continue;
                        }

                        boolean overlap = false;
                        for (int j = 0; j < index; j++) {
                            if (CollisionDetector.intersect(piece, current[j])) {
                                overlap = true;
                                break;
                            }
                        }
                        if (overlap) continue;

                        // 提前检查：剩余板块是否能放入剩余空间（简单面积剪枝）
                        if (!canFitRemaining(index, current, targetOutline)) {
                            continue;
                        }

                        // 递归
                        backtrack(index + 1, current, targetOutline, 
                                 minX, minY, maxX, maxY);

                        if (solutions.size() >= maxSolutions) return;
                    }
                }
            }
        }
    }

    /**
     * 简单剪枝：检查剩余面积是否能容纳剩余板块
     */
    private boolean canFitRemaining(int placed, Piece[] current, Point[] targetOutline) {
        // 简化版：仅检查面积和
        double remainingPieceArea = 0;
        for (int i = placed + 1; i < current.length; i++) {
            remainingPieceArea += current[i].getArea();
        }

        // 这里可以用更复杂的几何剪枝
        return true; // 面积已在前面验证相等
    }

    private double polygonArea(Point[] vertices) {
        double area = 0;
        for (int i = 0; i < vertices.length; i++) {
            int j = (i + 1) % vertices.length;
            area += vertices[i].cross(vertices[j]);
        }
        return Math.abs(area) / 2;
    }

    public int getNodeCount() { return nodeCount; }
}

/**
 * 解的表示
 */
public class Solution {
    private final Piece[] pieces;

    public Solution(Piece[] pieces) {
        this.pieces = pieces;
    }

    public void print() {
        System.out.println("=== 七巧板解 ===");
        for (Piece p : pieces) {
            System.out.println(p.getName() + ": 位置=" + p.getPosition() 
                + ", 旋转=" + String.format("%.1f°", Math.toDegrees(p.getRotation()))
                + (p.getName().contains("平行") && p.getPosition().x < 0 ? ", 已翻转" : ""));
        }
    }
}

目标轮廓定义与演示

public class TangramDemo {
    public static void main(String[] args) {
        System.out.println("=== 七巧板回溯求解器启动 ===\n");

        // 创建七巧板
        Piece[] pieces = TangramFactory.createStandardSet();
        System.out.println("七巧板板块:");
        for (Piece p : pieces) {
            System.out.println("  " + p.getName() + ": 面积=" + String.format("%.4f", p.getArea()));
        }

        double totalArea = Arrays.stream(pieces).mapToDouble(Piece::getArea).sum();
        System.out.println("总面积: " + String.format("%.4f", totalArea));

        // 定义目标轮廓：正方形 [0,1] × [0,1]
        Point[] squareOutline = {
            new Point(0, 0),
            new Point(1, 0),
            new Point(1, 1),
            new Point(0, 1)
        };

        System.out.println("\n目标: 正方形拼回原形");

        // 求解
        TangramSolver solver = new TangramSolver(1);
        List<Solution> solutions = solver.solve(squareOutline, pieces);

        System.out.println("\n搜索节点数: " + solver.getNodeCount());
        System.out.println("找到解数: " + solutions.size());

        if (!solutions.isEmpty()) {
            solutions.get(0).print();
        }

        // 测试碰撞检测
        System.out.println("\n=== 碰撞检测测试 ===");
        Piece tri1 = pieces[0].clone();
        Piece tri2 = pieces[1].clone();
        tri1.setTransform(new Point(0, 0), 0, false);
        tri2.setTransform(new Point(0.6, 0), 0, false);

        System.out.println("大三角1 与 大三角2 碰撞? " + CollisionDetector.intersect(tri1, tri2));

        tri2.setTransform(new Point(0.1, 0), 0, false);
        System.out.println("大三角1 与 偏移后大三角2 碰撞? " + CollisionDetector.intersect(tri1, tri2));

        // 验证SAT的正确性
        System.out.println("\n=== SAT验证 ===");
        Piece smallTri = pieces[3].clone();
        smallTri.setTransform(new Point(0.3, 0.3), Math.PI / 2, false);
        System.out.println("小三角变换后顶点:");
        for (Point v : smallTri.getTransformedVertices()) {
            System.out.println("  " + v);
        }
    }
}

复杂度分析

七巧板求解是NP-hard问题。对于正方形目标，由于对称性较高，通常能在数百万节点内找到解。

扩展方向

1. ** dancing links（DLX）**：将七巧板精确覆盖问题转化为DLX矩阵，使用Algorithm X高效求解
2. 模式数据库：预计算常见子结构的合法放置方式，加速搜索
3. 形状匹配：使用Hu矩或傅里叶描述子进行目标轮廓相似度匹配
4. 用户交互求解：实现拖拽放置和实时碰撞检测的可视化界面

总结

本文通过Java实现了七巧板自动求解系统：
– 二维几何变换：实现旋转、平移和翻转操作，保持数值稳定性
– 分离轴定理（SAT）：精确检测凸多边形碰撞，是游戏物理和计算几何的基础工具
– 回溯搜索：结合面积剪枝和启发式排序（从大到小），有效缩小搜索空间
– 约束满足建模：将拼图问题转化为CSP，便于扩展更复杂的约束条件

这些算法广泛应用于拼图游戏AI、CAD/CAM系统、机器人路径规划和计算机图形学中的碰撞检测。