每日算法 — 使用java实现棋盘覆盖：分治策略与递归填充算法

引言

棋盘覆盖问题（Tiling Problem）是算法教学中的经典案例：给定一个 2^k × 2^k 的棋盘，其中恰好有一个方格是缺失的，要求用 L 形三格骨牌（tromino）完美覆盖剩余所有方格。本文用 Java 实现该问题的完整求解系统，深入讲解分治策略（Divide and Conquer）、递归填充与数学归纳法证明，帮助读者理解分治思想如何将复杂问题优雅地分解为可管理的子问题。

核心算法思路

问题分析

关键观察：2^k × 2^k 的棋盘可以被均分为四个 2^(k-1) × 2^(k-1) 的子棋盘。由于原棋盘只有一个缺失格，所以：
– 一个子棋盘包含缺失格
– 另外三个子棋盘是完整的

如果我们在三个完整子棋盘的交界处放置一个 L 形骨牌，每个子棋盘都会”恰好有一个缺失格”，从而将原问题递归地转化为四个规模减半的子问题。

数学归纳法证明

基础情况：k=1 时，2×2 棋盘缺一格，恰好用一个 L 形骨牌覆盖。

归纳假设：假设对于 2^(k-1) × 2^(k-1) 的缺一格棋盘可覆盖。

归纳步骤：对于 2^k × 2^k 棋盘，分治后四个子棋盘均为 2^(k-1) × 2^(k-1) 且各缺一格，根据归纳假设均可覆盖。

时间复杂度

递推式 T(k) = 4T(k-1) + O(1)，根据主定理得 T(k) = O(4^k) = O(n^2)，其中 n = 2^k 为棋盘边长。由于需要填充 n^2 – 1 个格子，该复杂度是最优的。

完整 Java 实现

import java.util.*;

/**
 * 棋盘覆盖问题求解器
 * 核心算法：分治递归 + L形骨牌填充
 */
public class ChessboardTiling {

    // 棋盘状态，0表示未填充，正整数表示骨牌编号
    private int[][] board;
    private int tileCount;
    private final int boardSize;

    // 用于可视化的骨牌颜色映射
    private final Map<Integer, String> colorMap = new HashMap<>();
    private final String[] colors = {
        "\u001B[41m", "\u001B[42m", "\u001B[43m", "\u001B[44m",
        "\u001B[45m", "\u001B[46m", "\u001B[47m", "\u001B[100m"
    };
    private static final String RESET = "\u001B[0m";

    public ChessboardTiling(int k) {
        this.boardSize = 1 << k; // 2^k
        this.board = new int[boardSize][boardSize];
        this.tileCount = 0;
    }

    /**
     * 公共接口：求解棋盘覆盖
     * @param missingRow 缺失格子的行坐标
     * @param missingCol 缺失格子的列坐标
     */
    public void solve(int missingRow, int missingCol) {
        tileCount = 0;
        board = new int[boardSize][boardSize];
        board[missingRow][missingCol] = -1; // 标记缺失格
        divideAndConquer(0, 0, missingRow, missingCol, boardSize);
    }

    /**
     * 分治递归核心函数
     * @param startRow 当前子棋盘左上角行坐标
     * @param startCol 当前子棋盘左上角列坐标
     * @param missingRow 缺失格在当前子棋盘中的行坐标
     * @param missingCol 缺失格在当前子棋盘中的列坐标
     * @param size 当前子棋盘边长
     */
    private void divideAndConquer(int startRow, int startCol,
                                   int missingRow, int missingCol, int size) {
        // 基础情况：只剩一个格子
        if (size == 1) {
            return;
        }

        tileCount++;
        int currentTile = tileCount;
        int half = size / 2;

        // 确定缺失格位于哪个象限
        boolean missingTopLeft = (missingRow < startRow + half) && (missingCol < startCol + half);
        boolean missingTopRight = (missingRow < startRow + half) && (missingCol >= startCol + half);
        boolean missingBottomLeft = (missingRow >= startRow + half) && (missingCol < startCol + half);
        boolean missingBottomRight = (missingRow >= startRow + half) && (missingCol >= startCol + half);

        // 在中心放置一个L形骨牌，覆盖三个没有缺失格的象限的角落
        // 中心位置为 (startRow + half - 1, startCol + half - 1) 附近

        // 左上象限
        if (missingTopLeft) {
            // 缺失格在左上，递归处理
            divideAndConquer(startRow, startCol, missingRow, missingCol, half);
        } else {
            // 在左下角的右下角放置骨牌的一角
            board[startRow + half - 1][startCol + half - 1] = currentTile;
            divideAndConquer(startRow, startCol, startRow + half - 1, startCol + half - 1, half);
        }

        // 右上象限
        if (missingTopRight) {
            divideAndConquer(startRow, startCol + half, missingRow, missingCol, half);
        } else {
            board[startRow + half - 1][startCol + half] = currentTile;
            divideAndConquer(startRow, startCol + half, startRow + half - 1, startCol + half, half);
        }

        // 左下象限
        if (missingBottomLeft) {
            divideAndConquer(startRow + half, startCol, missingRow, missingCol, half);
        } else {
            board[startRow + half][startCol + half - 1] = currentTile;
            divideAndConquer(startRow + half, startCol, startRow + half, startCol + half - 1, half);
        }

        // 右下象限
        if (missingBottomRight) {
            divideAndConquer(startRow + half, startCol + half, missingRow, missingCol, half);
        } else {
            board[startRow + half][startCol + half] = currentTile;
            divideAndConquer(startRow + half, startCol + half, startRow + half, startCol + half, half);
        }
    }

    /**
     * 验证覆盖是否正确
     */
    public boolean validate() {
        // 检查是否所有非缺失格都被填充
        for (int i = 0; i < boardSize; i++) {
            for (int j = 0; j < boardSize; j++) {
                if (board[i][j] == 0) {
                    return false;
                }
            }
        }

        // 检查每个骨牌是否恰好覆盖3个格子
        Map<Integer, Integer> tileCounts = new HashMap<>();
        for (int i = 0; i < boardSize; i++) {
            for (int j = 0; j < boardSize; j++) {
                if (board[i][j] > 0) {
                    tileCounts.merge(board[i][j], 1, Integer::sum);
                }
            }
        }
        for (int count : tileCounts.values()) {
            if (count != 3) {
                System.out.println("骨牌覆盖格子数错误: " + count);
                return false;
            }
        }

        // 检查每个骨牌的3个格子是否构成L形
        for (Map.Entry<Integer, List<int[]>> entry : getTilePositions().entrySet()) {
            if (!isLShape(entry.getValue())) {
                return false;
            }
        }

        return true;
    }

    private Map<Integer, List<int[]>> getTilePositions() {
        Map<Integer, List<int[]>> positions = new HashMap<>();
        for (int i = 0; i < boardSize; i++) {
            for (int j = 0; j < boardSize; j++) {
                if (board[i][j] > 0) {
                    positions.computeIfAbsent(board[i][j], k -> new ArrayList<>()).add(new int[]{i, j});
                }
            }
        }
        return positions;
    }

    private boolean isLShape(List<int[]> cells) {
        if (cells.size() != 3) return false;
        // L形的特征是：三个格子中有两个在同一行/列，第三个与其中一个相邻
        int[][] c = cells.toArray(new int[3][]);
        // 检查是否连通
        int connections = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = i + 1; j < 3; j++) {
                int dist = Math.abs(c[i][0] - c[j][0]) + Math.abs(c[i][1] - c[j][1]);
                if (dist == 1) connections++;
            }
        }
        // L形有2条边连接（3个节点2条边构成链），但不是直线（3条边就是直线了）
        return connections == 2;
    }

    /**
     * 可视化输出棋盘
     */
    public void printBoard() {
        System.out.println("\n棋盘覆盖结果 (" + boardSize + "x" + boardSize + "):");
        System.out.println("-1 表示缺失格，其他数字表示骨牌编号");
        System.out.println();

        for (int i = 0; i < boardSize; i++) {
            for (int j = 0; j < boardSize; j++) {
                if (board[i][j] == -1) {
                    System.out.printf("%4s", "X");
                } else {
                    System.out.printf("%4d", board[i][j]);
                }
            }
            System.out.println();
        }
        System.out.println("\n总骨牌数: " + tileCount);
        System.out.println("理论骨牌数: " + ((boardSize * boardSize - 1) / 3));
    }

    /**
     * 彩色可视化（终端支持ANSI颜色时）
     */
    public void printColored() {
        System.out.println("\n彩色棋盘覆盖:");
        for (int i = 0; i < boardSize; i++) {
            for (int j = 0; j < boardSize; j++) {
                int val = board[i][j];
                String color;
                if (val == -1) {
                    color = "\u001B[30;47m";
                } else {
                    color = colors[val % colors.length];
                }
                System.out.printf("%s %3d %s", color, val, RESET);
            }
            System.out.println();
        }
    }

    /**
     * 统计各骨牌覆盖位置（调试用）
     */
    public void printTileDetails() {
        Map<Integer, List<int[]>> positions = getTilePositions();
        System.out.println("\n各骨牌覆盖位置:");
        for (Map.Entry<Integer, List<int[]>> entry : positions.entrySet()) {
            System.out.print("骨牌 " + entry.getKey() + ": ");
            for (int[] pos : entry.getValue()) {
                System.out.print("(" + pos[0] + "," + pos[1] + ") ");
            }
            System.out.println();
        }
    }

    /**
     * 对比不同规模棋盘的求解时间
     */
    public static void benchmark() {
        System.out.println("=== 性能测试 ===");
        for (int k = 1; k <= 6; k++) {
            int size = 1 << k;
            ChessboardTiling solver = new ChessboardTiling(k);
            long start = System.nanoTime();
            solver.solve(size / 2, size / 2);
            long end = System.nanoTime();
            boolean valid = solver.validate();
            System.out.printf("k=%d (size=%dx%d): %.3f ms, 验证=%b%n",
                    k, size, size, (end - start) / 1e6, valid);
        }
    }

    public static void main(String[] args) {
        // 示例1: 4x4 棋盘
        ChessboardTiling solver4 = new ChessboardTiling(2);
        solver4.solve(1, 1);
        solver4.printBoard();
        System.out.println("验证结果: " + solver4.validate());

        // 示例2: 8x8 棋盘
        ChessboardTiling solver8 = new ChessboardTiling(3);
        solver8.solve(3, 4);
        solver8.printBoard();
        System.out.println("验证结果: " + solver8.validate());

        // 性能测试
        benchmark();
    }
}

算法复杂度分析

扩展思考

1. 多缺失格扩展：若棋盘有 m 个缺失格（m ≡ 1 mod 3），是否仍可覆盖？这是一个NP完全问题的变种，对于一般情况没有多项式算法，但可用回溯搜索或SAT求解器处理小规模实例。
2. 其他骨牌形状：使用直三格骨牌（I-tromino）或四格骨牌（tetromino）时，覆盖条件与L形完全不同，涉及模运算约束与染色论证。
3. 三维扩展：2^k × 2^k × 2^k 立方体缺一角，用三维L形四格骨牌覆盖。递归思路相同，但几何复杂度大幅增加。

总结

棋盘覆盖问题完美展示了分治算法的威力：通过巧妙的中心骨牌放置，将一个大问题分解为四个完全相同的子问题。这种”自相似”的结构是分治思想的精髓。掌握此类问题，有助于理解快速排序、归并排序、线段树等更多经典分治算法的本质——找到合适的分割点，使得子问题与原问题同构。