You need to enable JavaScript to run this app. 已掌握2×n、3×n铺法的n×n棋盘瓷砖平铺计数求解
优惠活动
大模型
产品
解决方案
定价
更多

已掌握2×n、3×n铺法的n×n棋盘瓷砖平铺计数求解

n×n棋盘2×1瓷砖平铺的求解方法

首先先做前置判断:

首先可以直接排除所有n为奇数的情况:棋盘总格子数为n²,奇数个格子没法被每块占2格的2×1瓷砖完全覆盖,此时方案数恒为0。


核心方法:状态压缩轮廓线DP

你之前算2×n、3×n平铺的方法本质就是列状态递推:因为棋盘某一侧的宽度固定很小(2或3),单整列的可能状态数极少,只要枚举相邻列的合法匹配关系,就能顺着列的方向做线性递推算方案数。但n×n棋盘的边长是n,当n超过3之后,单靠整列做状态单元的递推计算量会快速暴涨,这时候最通用、能落地的求解方法,就是状态压缩轮廓线DP——本质也是你已经熟悉的递推思路,只是把状态单元从整列细化成了逐格的铺砖边界。

具体操作步骤

  • 固定扫描顺序:从棋盘左上角开始,按照“从左到右扫完一整行,再从上到下移到下一行”的逐格顺序铺瓷砖,全程不跳格。
  • 定义状态:每处理到一个格子时,记录“已经铺完的区域和没铺的区域之间的边界(也就是轮廓线)”的覆盖情况。因为轮廓线的长度刚好等于棋盘边长n,所以可以用一个n位的二进制数做状态压缩:二进制位为1,代表轮廓线对应的位置已经被相邻铺的瓷砖覆盖,不需要额外处理;为0就代表对应位置是空的,需要后续铺砖填上。
  • 状态转移:每到一个待处理的格子,只考虑三种合法的操作,不会产生无效分支:
    1. 如果当前格子已经被之前铺的瓷砖覆盖,就直接跳过这个格子,把原来的轮廓线状态顺移到下一个待处理格,不做新的铺砖操作。
    2. 如果当前格子右侧的相邻格子没有被覆盖,可以选择横放一块2×1瓷砖,把这两个相邻格子一起覆盖,同步更新轮廓线的二进制状态。
    3. 如果当前格子下侧的相邻格子没有被覆盖,可以选择竖放一块2×1瓷砖,把这两个相邻格子一起覆盖,同步更新轮廓线的二进制状态。
  • 边界判定:初始状态是刚接触棋盘左上角时,轮廓线全为0(没有任何已覆盖的位置);当扫完棋盘最后一个格子时,只有轮廓线全为0(没有遗留的空位)的状态对应的计数,才是有效的平铺方案数。

补充说明

  • 这个方法的计算复杂度是O(n² * 2^n),对于n到10左右的规模,完全可以手动推导或者用简单的代码实现算出来结果。
  • 目前这类正方形棋盘的多米诺平铺,没有像2×n问题那样简洁的闭式通项公式,所有已知的方案数都是通过上述状态压缩DP方法计算得到的:比如n=2时方案数为2,n=4时为36,n=6时为6728,n=8时为12988816。

内容的提问来源于stack exchange,提问作者PauL

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.31 22:27:01