1

你有 12 种形状:

在此处输入图像描述

你可以用五个相同的正方形来制作。

您需要将 12 块组合成一个矩形。您可以形成四个不同的矩形:2339 个解决方案 (6x10)、2 个解决方案 (3x20)、368 个解决方案 (4x15)、1010 个解决方案 (5x12)。

在此处输入图像描述

我需要构建 3X20 矩形:

我的问题是可能的最大状态数(即分支因子)是多少?

我的中途计算:

在我看来,每个形状都有 4 个操作:转动 90/180/270 度和镜像(将其倒置)。然后,您必须将形状放在板上,在 3X20 板上的某个位置。非法状态将是形状不适合董事会的状态,但它们仍然是状态。

第一步,您可以以 4 种方式选择每个形状,即 4X12 方式,然后您需要乘以该形状可以处于的位置数,即您拥有的状态数。但是如何计算职位数量?

请帮我计算这个非常重要,这不是我试图避免的某种家庭作业。

4

1 回答 1

1

我认为没有简单且“智能”的方式来列出五联拼图的解决方案(或状态)。你必须尝试所有的可能性。递归编程或回溯是实现它的方法。您应该检查这个也有可用的 java 源代码的解决方案。希望这会为您指明正确的方向。

还有一个可能更具可读性的 python解决方案。

于 2012-06-24T10:21:32.143 回答