java - 使用算法 X 解决精确覆盖问题的 Pentomino 求解算法

Question

我已经为此工作了好几天，最后决定在这里发布我的问题。我将向您详细解释我在做什么以及如何做。在继续之前。我浏览了维基百科和另外 20 个解释这个问题的网站，但没有帮助我。

Dancing Links - Wikipedia

Knuth's algorithm x .

一个更有用的网站:( Kanoodle )但是当涉及到我的问题时，解释很差。

问题:有多少种方法可以用 W-、I- 和 L-Pentominos 覆盖一个 5xn 的矩形。您可以翻转和旋转它们。您可能会问什么是 Pentominos？ Pentominos 由 5 个正方形组成，它们一起构成一个图形。例如 W-Pentomino。

   | A | B | C
---------------
a  | 1 | 0 | 0 |
-------------
b  | 1 | 1 | 0 |    Imagine all the 1s together they build a big "W".
-------------       If you look at my picture it will be clearer.
c  | 0 | 1 | 1 |

我没有在 5xn 区域中实现 W-、L- 和 I-Pentominos，而是削减了任务并开始考虑在 5x3 区域中填充“W”的所有可能方法。像这样。 我的下一步是考虑一个看起来类似于 Knuth 的 DLX 算法的矩阵，我想出了这个。黄色和橙色之间的绿线意味着您可以将两者放在一起以获得另一个有效的解决方案。我的下一篇文章描述了这条绿线。

我注意到，如果我取一行并检查该行下方或上方的任何其他行是否在同一列中没有 1，我就有一个有效的解决方案。但我不知道如何实现。经过数小时的研究，我找到了另一种描述我的问题的方法。我拿了一个子集(我的 W-Pentomino)并像这样定义它。

再一次，我在实现时遇到了麻烦。

所以这是我的问题:你将如何在 JAVA 中实现这个问题。我的方法好吗？你能接受我的想法吗？如果是，你会如何继续，如果不是，你能告诉我我思想上的失败在哪里吗？

这是给我的代码。

package data;

public class PentominoWILDLX
{
    static Node h;          // header element

    static int cnt;         // count solutions

    public PentominoWILDLX()
    {
        h = new Node();     // init header element
        cnt = 0;            // init counter
    }


    public static void search (int k)           // finds & counts solutions
    {
        if(h.R == h)                            // if empty: count & done
        {
            cnt++; return;                      // choose next column c
        }
        Node c = h.R;                           // remove c from clumns
        cover(c);                               // choose next colun c
        for (Node r=c.D; r!=c; r=r.D)           // forall rows with 1 in c
        {
            for(Node j=r.R; j!=r; j=j.R)        // forall 1-elements in row
            {
                cover(j.C);                     // remove clumn
            }
            search(k+1);                        // recursion with k+1 << hier überpfüen ob ich ändern muss
            for (Node j=r.L; j!=r; j=j.L)       // forall 1-elemnts in row
            {
                uncover(j.C);                   // backtrack . unremove? << googlen
            }
            uncover(c);                         // unremove f c to coulmns
        }
    }



    public static void cover (Node c)           // remove clumn c
    {
        c.R.L = c.L;                            // remove header
        c.L.R = c.R;                            // from row list
        for (Node i=c.D; i!=c; i=i.D)           // forall rows with 1
        {
            for (Node j=i.R; i!=j; j=j.R)       // forall elem in row
            {
                j.D.U = j.U;                    // rmove row elemnt
                j.U.D = j.D;                    // from column list
            }
        }
    }

    public static void uncover (Node c)         // undo remove col c
    {
        for (Node i=c.U; i!=c; i=i.U)           // forall rows with 1
        {
            for (Node j=i.L; i!=j; j=j.L)       // for all elem in row
            {
                j.D.U = j;                      // unremove row ele,
                j.U.D = j;                      // to lumn list
            }
            c.R.L = c;                          // unremove header
            c.L.R = c;                          // to row list
        }
    } // end of class

    class Node                  // represents 1 element or header
    {
        Node C;                 // reference to column-header << h?,
        Node L;                 // left
        Node R;                 // right
        Node U;                 // reference up
        Node D;                 // down reference down

        Node()
        {
            C=L=R=U=D=this;     // 2*double-linked circular list
        }
    }   // end of class

    public static void main(String[] args)
    {

    }

}

Answer 1

要找到将 Pentomino 放入矩形内的所有可能方式，您可以执行以下步骤:

1. 求出五联骨牌的长度和宽度，就好像您要根据其大小绘制一个矩形一样。
2. 现在找出该矩形可以放入较大矩形的次数。例如，您有一个 3x5 的矩形，较小的矩形用于 W 形，它是 3x3。 5-3+1 = 3。有 3 种可能的方法可以将 W 形状放入 3x5 正方形(不翻转或旋转)。如果矩形是 5x5 并且我们仍然使用相同的五联骨牌，那么将有 9 种可能的不同方式来放置形状而无需翻转或旋转。使用公式:x = a - b + 1； y = c - d + 1; xy = z(没有旋转的可能方式)。 a = 大矩形的长度； b = 小矩形的长度； c = 大矩形的宽度； d = 小矩形的宽度。
3. 由于我们处理的是矩形，因此您需要翻转形状并旋转它，每次执行此操作时都在第 3 步中进行相同的计算并将其添加到总数中。
4. 第 3 步提出了另一个问题。如果翻转或旋转的形状与之前的形状相同怎么办。要计算它，请采用 x 和 y 格式的形状，因此 w 形状为:{(0,0), (1,0), (1,1), (2,1), (2,2) } 如果原点在左上角。获取这些坐标并旋转它们。 (0, 0) -> (0, 3) 第一个点逆时针旋转 90 度。要将任何点旋转前 90 度，请执行以下操作:(y, w - x - 1) w = 矩形宽度。要旋转下一个 90 度，请执行以下操作:(y, h - x - 1) h = 矩形的高度。要旋转最后一次，请重复 (y, w - x - 1)。请记住，每次旋转时宽度和高度都必须交换，因为它是一个矩形而不是正方形。如果这些旋转图形中的任何一个具有相同的坐标(它们不必按相同顺序排列)，则不会在步骤 2 中检查该特定旋转。
5. 最后，您必须注意反射/翻转。这比旋转更容易。要水平翻转只需执​​行 (w - x - 1, y); w = 形状的宽度。

---

以下是我用来弄清楚并测试它的一些工作图片:

寻找可能性:

旋转(正方形和长方形):

翻转: