问题背景
骨牌覆盖（Domino Tiling）是一个经典的组合数学问题：给定一个 $m \times n$ 的棋盘，能否用 $1 \times 2$ 的多米诺骨牌将其完全覆盖，且骨牌之间不重叠、不越界？如果棋盘有缺失格子，又该如何判定？
这个问题表面上是几何铺砌问题，本质上可以转化为二分图匹配问题。每个格子看作图中的一个顶点，相邻格子之间连边，求一个完美匹配即对应一种合法的骨牌覆盖方案。
核心算法思路
棋盘染色与二分图建模
将棋盘按国际象棋规则进行黑白染色：坐标 $(i,j)$ 的格子颜色为 $(i+j) \bmod 2$。相邻格子颜色必然不同，因此棋盘天然构成一个二分图：
– 黑色格子构成左部顶点集
– 白色格子构成右部顶点集
– 相邻格子之间连一条边
一个 $1 \times 2$ 的骨牌恰好覆盖一黑一白两个相邻格子，因此完美覆盖等价于二分图的完美匹配。
匈牙利算法求解最大匹配
使用匈牙利算法（Hungarian Algorithm for Maximum Bipartite Matching）在二分图中寻找最大匹配。若最大匹配数等于总格子数的一半，则存在完美覆盖；否则不存在。
匈牙利算法的核心思想是：不断寻找增广路来扩大匹配。增广路是一条交替路径，其起点和终点都是未匹配点，路径上的边交替地属于非匹配边和匹配边。将增广路上的匹配状态翻转，即可使匹配数增加1。
Java 完整实现
import java.util.*;
/**
* 骨牌覆盖问题求解器
* 将棋盘转化为二分图，使用匈牙利算法求最大匹配
*/
public class DominoTiling {
// 棋盘行数和列数
private int rows;
private int cols;
// 标记缺失的格子，true表示该格子存在，false表示缺失
private boolean[][] available;
// 每个格子的编号，-1表示缺失
private int[][] id;
// 总格子数
private int totalCells;
// 左部顶点数量（黑色格子）
private int leftCount;
// 邻接表：左部顶点 -> 相邻的右部顶点列表
private List<Integer>[] graph;
// 右部顶点的匹配对象，-1表示未匹配
private int[] match;
// DFS访问标记
private boolean[] visited;
/**
* 构造函数
* @param rows 棋盘行数
* @param cols 棋盘列数
* @param missing 缺失格子的坐标列表，每个元素为 int[]{row, col}
*/
public DominoTiling(int rows, int cols, List<int[]> missing) {
this.rows = rows;
this.cols = cols;
this.available = new boolean[rows][cols];
for (int i = 0; i < rows; i++) {
Arrays.fill(available[i], true);
}
if (missing != null) {
for (int[] pos : missing) {
available[pos[0]][pos[1]] = false;
}
}
buildGraph();
}
/**
* 构建二分图
*/
@SuppressWarnings("unchecked")
private void buildGraph() {
id = new int[rows][cols];
for (int i = 0; i < rows; i++) {
Arrays.fill(id[i], -1);
}
// 给黑色格子（(i+j)%2==0）编号作为左部顶点
leftCount = 0;
int rightCount = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (available[i][j]) {
if ((i + j) % 2 == 0) {
id[i][j] = leftCount++;
} else {
id[i][j] = rightCount++;
}
}
}
}
totalCells = leftCount + rightCount;
graph = new ArrayList[leftCount];
for (int i = 0; i < leftCount; i++) {
graph[i] = new ArrayList<>();
}
// 四个方向：上、下、左、右
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
// 为每个黑色格子建立邻接关系
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (!available[i][j] || (i + j) % 2 != 0) continue;
int u = id[i][j];
for (int d = 0; d < 4; d++) {
int ni = i + dx[d];
int nj = j + dy[d];
if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && available[ni][nj]) {
int v = id[ni][nj];
graph[u].add(v);
}
}
}
}
}
/**
* 匈牙利算法：寻找增广路
* @param u 当前左部顶点
* @return 是否找到增广路
*/
private boolean findAugmentingPath(int u) {
for (int v : graph[u]) {
if (visited[v]) continue;
visited[v] = true;
// 如果v未匹配，或者v的匹配点可以找到新的匹配
if (match[v] == -1 || findAugmentingPath(match[v])) {
match[v] = u;
return true;
}
}
return false;
}
/**
* 求解最大匹配数
* @return 最大匹配数
*/
public int maxMatching() {
match = new int[rightCount()];
Arrays.fill(match, -1);
int result = 0;
for (int u = 0; u < leftCount; u++) {
visited = new boolean[rightCount()];
if (findAugmentingPath(u)) {
result++;
}
}
return result;
}
/**
* 获取右部顶点数量
*/
private int rightCount() {
int count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (available[i][j] && (i + j) % 2 == 1) {
count++;
}
}
}
return count;
}
/**
* 判断是否存在完美覆盖
* @return true 如果存在完美覆盖
*/
public boolean hasPerfectTiling() {
// 首先，总格子数必须是偶数
if (totalCells % 2 != 0) return false;
// 黑色和白色格子数必须相等
if (leftCount != rightCount()) return false;
return maxMatching() == leftCount;
}
/**
* 获取具体的覆盖方案
* @return 每个黑色格子的配对坐标，int[]{blackRow, blackCol, whiteRow, whiteCol}
*/
public List<int[]> getTilingSolution() {
List<int[]> solution = new ArrayList<>();
if (!hasPerfectTiling()) return solution;
// match[v] = u 表示右部顶点v匹配了左部顶点u
// 需要反向查找坐标
int[][] leftPos = new int[leftCount][2];
int[][] rightPos = new int[rightCount()][2];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (!available[i][j]) continue;
int idx = id[i][j];
if ((i + j) % 2 == 0) {
leftPos[idx] = new int[]{i, j};
} else {
rightPos[idx] = new int[]{i, j};
}
}
}
for (int v = 0; v < match.length; v++) {
if (match[v] != -1) {
int u = match[v];
solution.add(new int[]{
leftPos[u][0], leftPos[u][1],
rightPos[v][0], rightPos[v][1]
});
}
}
return solution;
}
/**
* 打印覆盖方案的可视化结果
*/
public void printSolution() {
List<int[]> sol = getTilingSolution();
if (sol.isEmpty()) {
System.out.println("不存在完美覆盖方案");
return;
}
// 为每个骨牌分配一个编号
int[][] dominoId = new int[rows][cols];
for (int i = 0; i < rows; i++) {
Arrays.fill(dominoId[i], -1);
}
for (int k = 0; k < sol.size(); k++) {
int[] d = sol.get(k);
dominoId[d[0]][d[1]] = k;
dominoId[d[2]][d[3]] = k;
}
System.out.println("骨牌覆盖方案（相同数字表示同一块骨牌）：");
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (!available[i][j]) {
System.out.print(" X ");
} else {
System.out.printf("%-3d", dominoId[i][j]);
}
}
System.out.println();
}
}
// ==================== 主程序 ====================
public static void main(String[] args) {
// 示例1：4x4 完整棋盘，存在完美覆盖
System.out.println("=== 示例1：4x4 完整棋盘 ===");
DominoTiling tiling1 = new DominoTiling(4, 4, null);
System.out.println("是否存在完美覆盖: " + tiling1.hasPerfectTiling());
tiling1.printSolution();
// 示例2：4x4 棋盘缺失对角两个格子，不存在完美覆盖
System.out.println("\n=== 示例2：4x4 缺失(0,0)和(3,3) ===");
List<int[]> missing2 = Arrays.asList(new int[]{0, 0}, new int[]{3, 3});
DominoTiling tiling2 = new DominoTiling(4, 4, missing2);
System.out.println("是否存在完美覆盖: " + tiling2.hasPerfectTiling());
// 示例3：3x4 棋盘，存在完美覆盖
System.out.println("\n=== 示例3：3x4 完整棋盘 ===");
DominoTiling tiling3 = new DominoTiling(3, 4, null);
System.out.println("是否存在完美覆盖: " + tiling3.hasPerfectTiling());
tiling3.printSolution();
// 示例4：经典问题 8x8 棋盘缺失对角，判定
System.out.println("\n=== 示例4：8x8 缺失对角(0,0)和(7,7) ===");
List<int[]> missing4 = Arrays.asList(new int[]{0, 0}, new int[]{7, 7});
DominoTiling tiling4 = new DominoTiling(8, 8, missing4);
System.out.println("是否存在完美覆盖: " + tiling4.hasPerfectTiling());
System.out.println("（原因：缺失的两个格子同色，导致黑白数量不平衡）");
}
}
算法复杂度分析
时间复杂度：匈牙利算法的时间复杂度为 $O(V \cdot E)$，其中 $V$ 是左部顶点数，$E$ 是边数。对于 $m \times n$ 的棋盘，$V \approx mn/2$，$E \approx 2mn$，因此总复杂度约为 $O(m^2 n^2)$。对于一般规模的棋盘（如 $8 \times 8$）可以瞬间完成。
空间复杂度：$O(mn)$，用于存储图的邻接表和匹配数组。
关键结论与扩展
- 必要条件：棋盘总格子数必须为偶数，且黑白格子数相等。缺失同色格子必然导致无法完美覆盖。
- 充分条件：对于矩形棋盘，上述必要条件也是充分的（可通过构造证明）。
- 扩展问题：可以进一步求解覆盖方案的总数，这需要使用转移矩阵法或轮廓线动态规划（Plug DP），时间复杂度更高。
- 实际应用：骨牌覆盖的模型在电路板设计、瓷砖铺设、蛋白质折叠等领域都有应用。
总结
本文将骨牌覆盖问题转化为二分图完美匹配问题，使用匈牙利算法进行求解。通过棋盘染色技巧，我们将几何问题巧妙地转化为图论问题，这是算法设计中”建模转换”思想的经典体现。掌握这种转换思维，能够帮助你在面对复杂问题时找到更简洁的解决路径。
