这个算法问题对于算法菊苣们来讲不过是小菜一碟。发到博客主要是希望能够对未来拿到这个问题而毫无头绪的读者带来些许帮助。

这篇文章实际上是我的《算法分析与设计》课程的大作业，从 Word 粘贴到博客仅做了一些格式上的修改，因此文章风格会比较离谱（报告文档的风格），敬请谅解。

问题题目

项目需求

本项目旨在解决以下的算法问题：

完全覆盖：有一天acmj在玩一种游戏—-用21或12的骨牌把m*n的棋盘完全覆盖。但他感觉把棋盘完全覆盖有点简单，他想能不能把完全覆盖的种数求出来？由于游戏难度增加他自己已经没法解决了，于是他希望大家能用程序来帮他把问题解决了。

业务要求

解决目标算法问题。

输入有多组数据。每组数据占一行，有两个正整数n（0 < n < 12）,m ( 0 < m < 12)。当n，m等于0时输入结束。

输出每组数据输出占一行，输出完全覆盖的种数。

总体设计

解决此算法问题的程序分为算法类、单元测试、主函数三个模块。算法程序使用 Java 编写。

设计内容和要求

算法类：提供解决此算法问题的类。此类中包含解决此问题的全部代码。每一组输入数据对应一个类实例。类的构造方法及其所有成员方法均为私有。对外仅暴露静态方法 solve() 用于解决算法问题。

单元测试：基于 Junit 单元测试框架编写，提供多组测试用例用于测试算法类的正确性。

主函数：可执行程序的入口点，接收用户的输入，输出算法结果。

算法的详细设计思想

本算法问题是一个状态压缩的动态规划问题。把棋盘看成一个 m*n 的矩阵，由于输入规模总是不大于12，并且棋盘的一个格子只有“放”与“不放”两种状态，因此可以用一个整型来表示一列。用一维整型数组表示一个棋盘。用二维数组 status[line][method]，以行号、该行的摆放方式为键，可行的摆放方案数(覆盖种数)为值，来存储每种排列方法的覆盖种数的动态规划结果。显然，状态压缩可以使得列的排列方法method直接作为数组的键而无需其他复杂的设计。

定义，对横着放的骨牌，左右两个位置均置为 1，对竖着放的骨牌，上方置 1，下方置 0。从最后一行开始，先假设最后一行的“后”一行全 1（用来过转移条件的判断），求在第 line 行的总方案数。

易证，所有有效的放置办法的第一行必然全为 1。dpSolve() 函数接受两个参数，分别表示需要计算覆盖种数的行数 line、上一行的排列方法lastMethod，返回覆盖种数。函数从本行首列开始，枚举这行的列的所有排列情况。对于一个排列情况，在满足转移条件时递归求覆盖方法的个数。递归时行数递减，并传入枚举的排列方法，若到达第 0 行，当发现整个第 1 行（首行）骨牌全是 1，可知放置办法有效，返回1。否则放置方法无效。最终，每行递归返回的结果求和即为本行、上一行的排列方法对应的覆盖种数。结果保存到二维数组以便反复使用。

转移条件是：

1. 当前排列情况和之前的那一行的排列方式的“或”结果为全 1：确保不存在上下都是 0 的情况
2. 当前排列情况和之前的那一行的排列方式的“与”结果为每两个相邻 1 成对或每两个相邻 0 成对：确保不存在孤立 1 和 孤立 0 的情况。

同时满足上述条件时，事实上覆盖了所有有效的排列情况并排除了非法排列。对于最后一行，传入的全 1 可保证不出现孤立1 —— 最后一行不可能再往下竖着放。

当所有排列方法枚举和递归完成时，函数返回的结果即为m*n棋盘的覆盖种数。

源代码

DominoArrangeNumSolver.java

import java.util.Arrays;

/**
 * status[i][S] 表示到达第i行，当前覆盖状态为 S 的方案数
 * 对横着放的骨牌，左右两个位置均置为 1
 * 对竖着放的骨牌，上方置 1，下方置 0
 */
public final class DominoArrangeNumSolver {
    private final long[][] status;
    private final int colNum;

    private DominoArrangeNumSolver(int line, int col) {
        this.colNum = col;
        this.status = new long[line + 1][1 << col];
        Arrays.stream(status).forEach(it -> Arrays.fill(it, -1)); // 全部填充 -1 表示未访问过
    }

    /**
     * 检查排列方法是否存在不成对的孤立 0 或 1
     * @param method 该列的排列方式
     * @return boolean true：没有孤立 0 或 1
     */
    private boolean isMethodPaired(int method) {
        for (int col = 0; col < colNum; col++) { // 查找 1 的下一个是否为 0 来检查是否不成对
            if ((method & (1 << col)) != 0) { // 第 col 列骨牌是 1
                if (col == colNum - 1 || (method & (1 << (col + 1))) == 0) //是最后一列或 col + 1 列是 0
                    return false;

                col++; //跳过下一列，直接进入 col + 2
            }
        }

        return true;
    }

    /**
     * 求在第 line 行的总方案数。
     * 注：函数内的“之前的那一行”指的是函数递归调用前的那一行的排列，意义上为 line + 1 行的排列。
     * @param line 行
     * @param lastMethod 之前的一行的排列（即 line + 1 的排列）
     * @return 方案数
     */
    private long dpSolve(int line, int lastMethod) {
        if (status[line][lastMethod] != -1) // 是否已经计算过目的行的排列
            return status[line][lastMethod];

        // 递归停止条件。易证所有有效的放置办法第一行必然全为 1
        if (line == 0) { //若为第 0 行
            if (lastMethod == ((1 << colNum) - 1)) // 整个第 1 行（首行）骨牌全是 1，也就是放置办法有效。
                return status[line][lastMethod] = 1; // 需要指出，放置时从末行放置，而检查时从首行检查。不可能有首行为 0 的任何有效表示
            else // 其他情况放置的肯定不成立。
                return status[line][lastMethod] = 0;
        }

        status[line][lastMethod] = 0;
        for (int cond = 0; cond < (1 << colNum); cond++) { // 枚举这行的列的所有排列情况
            // 转移条件【同时满足时转移】检查是否存在不合理的排列
            // 1. 当前排列情况和之前的那一行的排列方式的“或”结果为全 1：确保不存在上下都是 0 的情况
            // 2. 当前排列情况和之前的那一行的排列方式的“与”结果为每两个相邻 1 成对或每两个相邻 0 成对：确保不存在孤立 1 和 孤立 0 的情况。
            // 同时满足上述条件时，事实上覆盖了所有有效的排列情况并排除了非法排列
            // 对于最后一行，传入的全 1 可保证不出现孤立1 —— 最后一行不可能再往下竖着放
            if ((cond | lastMethod) == ((1 << colNum) - 1) && isMethodPaired(cond & lastMethod))
                status[line][lastMethod] += dpSolve(line - 1, cond); // 递归求 line - 1 行的放置
        }

        return status[line][lastMethod];
    }

    public static long solve(int line, int col) {
        if (line == 0 || col == 0 || (line % 2 != 0 && col % 2 != 0))
            return 0;

        if (col > line) { // 让较小者成为列，减少情况数。
            int temp = line;
            line = col;
            col = temp;
        }

        // 从最后一行开始，先假设最后一行的“后”一行全 1，用来过转移条件的判断。
        return new DominoArrangeNumSolver(line, col).dpSolve(line, (1 << col) - 1);
    }
}

DominoArrangeNumTest.java

import org.junit.Assert;
import org.junit.Test;

import java.util.Scanner;

public final class DominoArrangeNumTest {
    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            int col;
            int line;

            do {
                col = scanner.nextInt();
                line = scanner.nextInt();

                System.out.println(DominoArrangeNumSolver.solve(line, col));
            } while (col != 0 || line != 0);
        }
    }

    @Test
    public void test() {
        Assert.assertEquals(51205, DominoArrangeNumSolver.solve(4, 11));
        Assert.assertEquals(3, DominoArrangeNumSolver.solve(2, 3));
        Assert.assertEquals(2, DominoArrangeNumSolver.solve(2, 2));
        Assert.assertEquals(5, DominoArrangeNumSolver.solve(2, 4));
        Assert.assertEquals(144, DominoArrangeNumSolver.solve(2, 11));
        Assert.assertEquals(0, DominoArrangeNumSolver.solve(1, 3));
        Assert.assertEquals(0, DominoArrangeNumSolver.solve(3, 3));
        Assert.assertEquals(53060477521960000L, DominoArrangeNumSolver.solve(12, 12));
    }
}