编程竞赛题:计数多利奥美罗

Question

请看我自己的答案，我想我做到了！

嗨,

一个编程竞赛的例子问题是编写一个程序，找出在给定数量的石头下，有多少多个多态元是可能的。

因此，对于两个石头(n = 2)，只有一个多聚体：

XX

您可能会认为这是第二个解决方案：

X
X

但事实并非如此。如果你能旋转，多子子并不是唯一的。

因此，对于4颗石头(n = 4)，有7种解决方案：

X
X   XX   X    X     X   X
X   X    XX   X    XX   XX   XX
X   X    X    XX   X     X   XX

应用程序必须能够找到1 <= n <=10的解决方案。

PS:不允许使用维基百科多数点列表 ;)

编辑:当然问题是:如何在Java，C/C++，C#中实现这一点

我是用Java开始这个项目的。但后来我不得不承认，我不知道如何使用高效的算法来构建多个元。

这就是我到目前为止所拥有的：

import java.util.ArrayList;
import java.util.List;


public class Main
{

    private int countPolyminos(int n)
    {
        hashes.clear();
        count = 0;
        boolean[][] matrix = new boolean[n][n];
        createPolyominos(matrix, n);
        return count;
    }

    private List<Integer> hashes = new ArrayList<Integer>();
    private int count;

    private void createPolyominos(boolean[][] matrix, int n)
    {
        if (n == 0)
        {
            boolean[][] cropped = cropMatrix(matrix); 
            int hash = hashMatrixOrientationIndependent(matrix);
            if (!hashes.contains(hash))
            {
                count++;
                hashes.add(hash);
            }
            return;
        }
    // Here is the real trouble!!
    // Then here something like; createPolyominos(matrix, n-1);
    // But, we need to keep in mind that the polyominos can have ramifications
    }

    public boolean[][] copy(boolean[][] matrix)
    {
        boolean[][] b = new boolean[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; ++i)
        {
            System.arraycopy(matrix[i], 0, b, 0, matrix[i].length);
        }
        return b;
    }

    public boolean[][] cropMatrix(boolean[][] matrix)
    {
        int l = 0, t = 0, r = 0, b = 0;
        // Left
        left: for (int x = 0; x < matrix.length; ++x)
        {
            for (int y = 0; y < matrix[x].length; ++y)
            {
                if (matrix[x][y])
                {
                    break left;
                }
            }
            l++;
        }
        // Right
        right: for (int x = matrix.length - 1; x >= 0; --x)
        {
            for (int y = 0; y < matrix[x].length; ++y)
            {
                if (matrix[x][y])
                {
                    break right;
                }
            }
            r++;
        }
        // Top
        top: for (int y = 0; y < matrix[0].length; ++y)
        {
            for (int x = 0; x < matrix.length; ++x)
            {
                if (matrix[x][y])
                {
                    break top;
                }
            }
            t++;
        }
        // Bottom
        bottom: for (int y = matrix[0].length; y >= 0; --y)
        {
            for (int x = 0; x < matrix.length; ++x)
            {
                if (matrix[x][y])
                {
                    break bottom;
                }
            }
            b++;
        }

        // Perform the real crop
        boolean[][] cropped = new boolean[matrix.length - l - r][matrix[0].length - t - b];
        for (int x = l; x < matrix.length - r; ++x)
        {
            System.arraycopy(matrix[x - l], t, cropped, 0, matrix[x].length - t - b);
        }
        return cropped;
    }

    public int hashMatrix(boolean[][] matrix)
    {
        int hash = 0;
        for (int x = 0; x < matrix.length; ++x)
        {
            for (int y = 0; y < matrix[x].length; ++y)
            {
                hash += matrix[x][y] ? (((x + 7) << 4) * ((y + 3) << 6) * 31) : ((((x+5) << 9) * (((y + x) + 18) << 7) * 53));
            }
        }
        return hash;
    }

    public int hashMatrixOrientationIndependent(boolean[][] matrix)
    {
        int hash = 0;
        hash += hashMatrix(matrix);
        for (int i = 0; i < 3; ++i)
        {
            matrix = rotateMatrixLeft(matrix);
            hash += hashMatrix(matrix);
        }
        return hash;
    }

    public boolean[][] rotateMatrixRight(boolean[][] matrix)
    {
        /* W and H are already swapped */
        int w = matrix.length;
        int h = matrix[0].length;
        boolean[][] ret = new boolean[h][w];
        for (int i = 0; i < h; ++i)
        {
            for (int j = 0; j < w; ++j)
            {
                ret[i][j] = matrix[w - j - 1][i];
            }
        }
        return ret;
    }

    public boolean[][] rotateMatrixLeft(boolean[][] matrix)
    {
        /* W and H are already swapped */
        int w = matrix.length;
        int h = matrix[0].length;
        boolean[][] ret = new boolean[h][w];
        for (int i = 0; i < h; ++i)
        {
            for (int j = 0; j < w; ++j)
            {
                ret[i][j] = matrix[j][h - i - 1];
            }
        }
        return ret;
    }

}

Answer 1

刚刚在java里也解决了这个问题。因为这里似乎都有性能问题。我也给你我的。

板评论：

2整数数组。行1，列1。

• 旋转：column[i]=row[size-(i+1)]，row[i] = reverse(column[i])，其中反向是根据大小反转的位(对于大小=4和前2位取为：rev(1100) = 0011)
• 移位块：row[i-1] = row[i]，col[i]<<=1
• 检查是否设置了位：(row[r] & (1<<c)) > 0
• 板唯一性:当数组行是唯一的时，板是唯一的。
• 板哈希:数组行的哈希代码
• 。。

所以这使得所有的操作都变得更快。他们中的许多人应该是2D数组表示中的O(size²)而不是现在的O(size)。

算法：

• 从大小为1的块开始
• 对于每一个大小，从块开始，少1英石。
• 如果可以加石头的话。检查它是否已经添加到集合中。
• 如果还没加进去。将其添加到此大小的解决方案中。
  • 将块添加到集合及其所有旋转中。(3次轮调，共计4次)
  • 重要的是，每次旋转后，块尽可能左/顶移动。

​

• +特殊情况:对接下来的2种情况执行相同的逻辑
  • 将块1向右移动，并在第一列中添加石头
  • 将块1移到底部，并在第一行中添加石头

​

Performance:

• N=5，时间: 3ms
• N=10，时间:58
• N=11，时间:166
• N=12，时间:538
• N=13，时间: 2893ms
• N=14，时间:17266ms
• N=15，NA (堆外)

代码：https://github.com/Samjayyy/logicpuzzles/tree/master/polyominos

Answer 2

只有4,461个大小为10的多项式，所以我们可以把它们全部列举出来。

从一块石头开始。若要将其扩展一石，请尝试将新的石头添加到与现有石头相邻的所有空细胞中。递归地这样做，直到达到所需的大小。

为了避免重复，保留一个哈希表，列出我们已经列举过的所有大小的多项式。当我们将一个新的多项式组合在一起时，我们检查它是否还在哈希表中。我们还需要检查它的3个旋转(可能是它的镜像)。虽然重复检查的最终大小是唯一严格必要的检查，检查在每一步修剪递归分支，将产生一个新的多项式。

下面是一些伪代码：

polynomino = array of n hashtables
function find_polynominoes(n, base):
  if base.size == n:
    return
  for stone in base:
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
      new_stone.x = stone.x + dx
      new_stone.y = stone.y + dy
      if new_stone not in base:
        new_polynomino = base + new_stone
        is_new = true
        for rotation in [0, 90, 180, 270]:
          if new_polynomino.rotate(rotation) in polynomino[new_polynomino.size]:
            is_new = false
            break
        if is_new:
          polynomino[new_polynomino.size].add(new_polynomino)

Answer 3

最天真的解决方案是从一个X开始，对于每个迭代，构建唯一可能的下一个状态列表。从该列表中，通过添加另一个X来构建唯一状态列表。继续这样做，直到你想要的迭代。

不过，我不确定这是否在N=10的合理时间内运行。可能吧，这取决于你的需求。