每日算法 — 使用java实现多米诺骨牌：回溯搜索与动态规划最优覆盖策略

引言

多米诺骨牌是由两个相连正方形组成的矩形牌块，是经典的组合数学研究对象。多米诺骨牌覆盖问题要求用 ( 1 \times 2 ) 或 ( 2 \times 1 ) 的骨牌完全覆盖一个给定的棋盘区域，且不重叠、不遗漏。本文将使用Java实现多米诺骨牌覆盖问题的求解器，结合回溯搜索与动态规划两种策略，分别处理小规模精确解和大规模最优覆盖问题。

算法原理

问题建模

给定一个 ( m \times n ) 的棋盘（某些格子可能被挖去），判断是否可以用多米诺骨牌完全覆盖。每枚骨牌恰好覆盖两个相邻的正方形格子。

必要条件：棋盘总格子数必须为偶数，否则不可能覆盖。

回溯搜索算法

对于小规模棋盘，使用深度优先搜索枚举所有可能的放置方式：

1. 找到当前棋盘中第一个未被覆盖的格子
2. 尝试向右或向下放置一枚骨牌（如果合法）
3. 递归搜索剩余格子
4. 回溯，撤销当前放置

状态压缩动态规划

对于宽度较小的棋盘（如 ( m \leq 10 )），可以使用轮廓线DP逐行扫描：

• 状态表示：用一个二进制数表示当前行的覆盖状态，第 ( i ) 位为1表示该列已被上一行的竖放骨牌覆盖
• 状态转移：对于当前行的每一列，可以选择横放（覆盖当前行两列）或竖放（覆盖当前行和下一行）
• 转移方程：( dp[i][mask] = \sum dp[i-1][prevMask] )，其中 ( prevMask ) 能合法转移到 ( mask )

棋盘完美匹配建模

多米诺覆盖问题等价于棋盘的网格图完美匹配问题。将每个格子视为顶点，相邻格子间添加边，则骨牌覆盖对应图中的一个匹配。

Java实现

import java.util.*;

/**
 * 多米诺骨牌覆盖求解器
 * 包含回溯搜索和状态压缩DP两种算法
 */
public class DominoTilingSolver {

    /**
     * 回溯搜索求解器（适用于小规模棋盘）
     */
    public static class BacktrackingSolver {
        private boolean[][] board;
        private boolean[][] covered;
        private int rows, cols;
        private long solutionCount;
        private List<boolean[][]> solutions;

        public BacktrackingSolver(boolean[][] board) {
            this.board = board;
            this.rows = board.length;
            this.cols = board[0].length;
            this.covered = new boolean[rows][cols];
            this.solutions = new ArrayList<>();
        }

        /**
         * 求解并返回方案数
         */
        public long solve() {
            solutionCount = 0;
            solutions.clear();

            // 检查格子数是否为偶数
            int count = 0;
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (board[r][c]) count++;
                }
            }
            if (count % 2 != 0) return 0;

            dfs(0, 0);
            return solutionCount;
        }

        /**
         * 深度优先搜索
         * @param r 当前扫描行
         * @param c 当前扫描列
         */
        private void dfs(int r, int c) {
            // 找到下一个未覆盖的可放置格子
            while (r < rows && (c >= cols || !board[r][c] || covered[r][c])) {
                if (c >= cols) {
                    r++;
                    c = 0;
                } else {
                    c++;
                }
            }

            // 所有格子已覆盖，找到一种方案
            if (r >= rows) {
                solutionCount++;
                if (solutions.size() < 5) { // 最多保存5个方案
                    saveSolution();
                }
                return;
            }

            // 尝试向右放置（横放）
            if (c + 1 < cols && board[r][c + 1] && !covered[r][c + 1]) {
                covered[r][c] = true;
                covered[r][c + 1] = true;
                dfs(r, c + 2);
                covered[r][c] = false;
                covered[r][c + 1] = false;
            }

            // 尝试向下放置（竖放）
            if (r + 1 < rows && board[r + 1][c] && !covered[r + 1][c]) {
                covered[r][c] = true;
                covered[r + 1][c] = true;
                dfs(r, c + 1);
                covered[r][c] = false;
                covered[r + 1][c] = false;
            }
        }

        private void saveSolution() {
            boolean[][] sol = new boolean[rows][cols];
            for (int r = 0; r < rows; r++) {
                System.arraycopy(covered[r], 0, sol[r], 0, cols);
            }
            solutions.add(sol);
        }

        public List<boolean[][]> getSolutions() { return solutions; }
    }

    /**
     * 状态压缩动态规划求解器（适用于宽度较小的棋盘）
     */
    public static class DPSolver {
        private int rows, cols;
        private boolean[][] board;
        private long[][] dp; // dp[row][mask] 表示处理到第row行，当前轮廓状态为mask的方案数

        public DPSolver(boolean[][] board) {
            this.board = board;
            this.rows = board.length;
            this.cols = board[0].length;
            this.dp = new long[rows + 1][1 << cols];
        }

        /**
         * 使用状态压缩DP计算覆盖方案数
         */
        public long solve() {
            // 检查格子数是否为偶数
            int count = 0;
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (board[r][c]) count++;
                }
            }
            if (count % 2 != 0) return 0;

            dp[0][0] = 1; // 初始状态：第0行上方无覆盖

            for (int r = 0; r < rows; r++) {
                for (int mask = 0; mask < (1 << cols); mask++) {
                    if (dp[r][mask] == 0) continue;

                    // 从当前mask出发，搜索第r行的所有合法覆盖方式
                    // nextMask表示第r行被竖放骨牌覆盖的列（即延伸到第r+1行的部分）
                    searchRow(r, 0, mask, 0, dp[r][mask]);
                }
            }

            // 最终状态：最后一行没有延伸到下一行的骨牌
            return dp[rows][0];
        }

        /**
         * 搜索当前行的覆盖方式
         * @param r 当前行
         * @param c 当前列
         * @param prevMask 上一行遗留的覆盖状态
         * @param nextMask 当前行竖放延伸到下一行的状态
         * @param ways 到达当前状态的方案数
         */
        private void searchRow(int r, int c, int prevMask, int nextMask, long ways) {
            // 跳过已被覆盖或不可放置的格子
            while (c < cols && ((prevMask >> c) & 1) == 1 || !board[r][c]) {
                if (c < cols && !board[r][c]) {
                    // 不可放置的格子必须已经被覆盖（由prevMask覆盖）
                    if (((prevMask >> c) & 1) == 0) return; // 非法状态
                }
                c++;
            }

            if (c >= cols) {
                // 当前行处理完毕
                dp[r + 1][nextMask] += ways;
                return;
            }

            // 当前格子(r,c)需要被覆盖

            // 尝试横放：覆盖(r,c)和(r,c+1)
            if (c + 1 < cols && ((prevMask >> (c + 1)) & 1) == 0 && board[r][c + 1]) {
                searchRow(r, c + 2, prevMask, nextMask, ways);
            }

            // 尝试竖放：覆盖(r,c)和(r+1,c)，延伸到下一行
            if (r + 1 < rows && board[r + 1][c]) {
                searchRow(r, c + 1, prevMask, nextMask | (1 << c), ways);
            }
        }
    }

    /**
     * 二分图匹配求解器（适用于带障碍的棋盘）
     * 将棋盘染色为二分图，求最大匹配
     */
    public static class BipartiteMatchingSolver {
        private boolean[][] board;
        private int rows, cols;
        private int[] match; // 每个格子的匹配对象编号
        private boolean[] visited;
        private int totalCells;

        public BipartiteMatchingSolver(boolean[][] board) {
            this.board = board;
            this.rows = board.length;
            this.cols = board[0].length;
            this.totalCells = rows * cols;
            this.match = new int[totalCells];
            Arrays.fill(match, -1);
        }

        /**
         * 使用匈牙利算法（DFS增广路）求最大匹配
         * @return 最大匹配数，若等于总格子数/2则存在完美覆盖
         */
        public int solve() {
            int matching = 0;

            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (!board[r][c]) continue;
                    // 只对黑色格子（按棋盘染色）发起匹配
                    if ((r + c) % 2 == 0) {
                        visited = new boolean[totalCells];
                        if (dfs(r, c)) {
                            matching++;
                        }
                    }
                }
            }

            return matching;
        }

        private boolean dfs(int r, int c) {
            int id = r * cols + c;
            visited[id] = true;

            // 四个方向的邻居
            int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                if (!board[nr][nc]) continue;

                int nid = nr * cols + nc;
                if (visited[nid]) continue;

                if (match[nid] == -1 || dfs(match[nid] / cols, match[nid] % cols)) {
                    match[id] = nid;
                    match[nid] = id;
                    return true;
                }
            }

            return false;
        }

        /**
         * 判断是否存在完美覆盖
         */
        public boolean hasPerfectTiling() {
            int count = 0;
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (board[r][c]) count++;
                }
            }
            return solve() * 2 == count;
        }

        /**
         * 获取匹配结果
         */
        public List<int[]> getMatchingPairs() {
            List<int[]> pairs = new ArrayList<>();
            boolean[] used = new boolean[totalCells];

            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    int id = r * cols + c;
                    if (!board[r][c] || used[id]) continue;

                    if (match[id] != -1) {
                        int mid = match[id];
                        pairs.add(new int[]{id, mid});
                        used[id] = true;
                        used[mid] = true;
                    }
                }
            }

            return pairs;
        }
    }

    /**
     * 打印棋盘状态
     */
    public static void printBoard(boolean[][] board, boolean[][] covered) {
        int rows = board.length;
        int cols = board[0].length;

        System.out.println("  " + "0 1 2 3 4 5 6 7".substring(0, cols * 2));
        for (int r = 0; r < rows; r++) {
            System.out.print(r + " ");
            for (int c = 0; c < cols; cols++) {
                if (!board[r][c]) {
                    System.out.print("# ");
                } else if (covered != null && covered[r][c]) {
                    System.out.print("■ ");
                } else {
                    System.out.print("□ ");
                }
            }
            System.out.println();
        }
    }

    /**
     * 打印匹配方案
     */
    public static void printMatching(boolean[][] board, List<int[]> pairs, int cols) {
        int rows = board.length;
        char[][] display = new char[rows][cols];
        for (int r = 0; r < rows; r++) {
            Arrays.fill(display[r], '.');
            for (int c = 0; c < cols; c++) {
                if (!board[r][c]) display[r][c] = '#';
            }
        }

        char label = 'A';
        for (int[] pair : pairs) {
            int r1 = pair[0] / cols, c1 = pair[0] % cols;
            int r2 = pair[1] / cols, c2 = pair[1] % cols;
            display[r1][c1] = label;
            display[r2][c2] = label;
            label++;
        }

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                System.out.print(display[r][c] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 主程序：演示多米诺骨牌覆盖
     */
    public static void main(String[] args) {
        System.out.println("=== 多米诺骨牌覆盖问题求解器 ===\n");

        // 示例1：4x4标准棋盘
        System.out.println("【示例1】4x4标准棋盘");
        boolean[][] board1 = new boolean[4][4];
        for (int r = 0; r < 4; r++) Arrays.fill(board1[r], true);

        BacktrackingSolver bt1 = new BacktrackingSolver(board1);
        long count1 = bt1.solve();
        System.out.println("回溯搜索方案数: " + count1);

        DPSolver dp1 = new DPSolver(board1);
        long count1dp = dp1.solve();
        System.out.println("状态压缩DP方案数: " + count1dp);

        // 示例2：带障碍的棋盘
        System.out.println("\n【示例2】5x5带障碍棋盘");
        boolean[][] board2 = new boolean[5][5];
        for (int r = 0; r < 5; r++) Arrays.fill(board2[r], true);
        // 挖去中心格子
        board2[2][2] = false;

        BacktrackingSolver bt2 = new BacktrackingSolver(board2);
        long count2 = bt2.solve();
        System.out.println("回溯搜索方案数: " + count2);

        BipartiteMatchingSolver bm2 = new BipartiteMatchingSolver(board2);
        boolean perfect2 = bm2.hasPerfectTiling();
        System.out.println("是否存在完美覆盖: " + perfect2);

        // 示例3：2xN棋盘的DP求解
        System.out.println("\n【示例3】2x10棋盘的DP方案数");
        boolean[][] board3 = new boolean[2][10];
        for (int r = 0; r < 2; r++) Arrays.fill(board3[r], true);

        DPSolver dp3 = new DPSolver(board3);
        long count3 = dp3.solve();
        System.out.println("状态压缩DP方案数: " + count3);
        System.out.println("（斐波那契数列：F(11) = 89）");

        // 示例4：使用二分图匹配求解带障碍棋盘
        System.out.println("\n【示例4】6x6带多个障碍的棋盘 - 二分图匹配");
        boolean[][] board4 = new boolean[6][6];
        for (int r = 0; r < 6; r++) Arrays.fill(board4[r], true);
        // 挖去一些格子形成不规则形状
        board4[1][1] = false;
        board4[1][4] = false;
        board4[4][1] = false;
        board4[4][4] = false;

        BipartiteMatchingSolver bm4 = new BipartiteMatchingSolver(board4);
        int match4 = bm4.solve();
        int cells4 = 0;
        for (boolean[] row : board4) for (boolean cell : row) if (cell) cells4++;
        System.out.println("总格子数: " + cells4 + ", 最大匹配数: " + match4);
        System.out.println("是否存在完美覆盖: " + (match4 * 2 == cells4));

        if (match4 * 2 == cells4) {
            System.out.println("一种覆盖方案：");
            printMatching(board4, bm4.getMatchingPairs(), 6);
        }
    }
}

算法分析

棋盘染色的理论保证

将棋盘按国际象棋方式黑白染色，每枚多米诺骨牌恰好覆盖一个黑格和一个白格。因此完美覆盖的必要条件是黑格数等于白格数。对于矩形棋盘，这等价于总格子数为偶数。

特殊棋盘的方案数

复杂度对比

总结

本文从三个角度解决了多米诺骨牌覆盖问题：回溯搜索适用于小规模棋盘的精确计数，状态压缩DP利用轮廓线技巧高效处理狭长棋盘，二分图匹配则将问题转化为图论模型快速判断覆盖可行性。

三种方法各有优势，实际应用中应根据棋盘规模和问题类型选择合适算法。对于需要枚举所有方案的场景，回溯搜索是最直接的选择；对于大规模计数问题，状态压缩DP在时间效率上具有明显优势；而对于仅需要判断可行性的场景，二分图匹配的匈牙利算法最为高效。