1

我收到了来自 lonpos.cc 的大脑拼图作为礼物。我很好奇有多少不同的解决方案，我非常喜欢编写算法和代码，所以我开始编写一个应用程序来蛮力它。

拼图看起来像这样：http ://www.lonpos.cc/images/LONPOSdb.jpg / http://cdn100.iofferphoto.com/img/item/191/498/944/u2t6.jpg

这是一个 20x14“点”的板。所有拼图都可以翻转和转动。我编写了一个应用程序，其中每个部分（和拼图）都呈现如下：

01010
00100
01110
01110
11111
01010

到目前为止，我的应用程序相当简单。

它采用棋子列表和一块空白板，棋子#0 的弹奏将其向各个方向翻转，并且该棋子尝试将其放置在每个 x 和 y 坐标上。如果它成功放置了一个棋子，它会传递一个新“棋盘”的副本，其中一些棋子被带到递归函数中，并为它们的棋子尝试所有组合。

用伪代码解释：

bruteForce(Board base, List pieces) {
    for (Piece in pieces.pop, piece.pop.flip, piece.pop.flip2...) {
        int x,y = 0;
        if canplace(piece, x, y) {
            Board newBoard = base.clone();
            newBoard.placePiece(piece, x, y);
            bruteForce(newBoard, pieces);
        }
        ## increment x until x > width, then y
    }
}

现在，我正在尝试找到更快的方法。到目前为止我想到的事情：

  1. 使其并行解决 - 已实现，现在使用 4 个线程。
  2. 对碎片进行排序，并且只尝试将适合的碎片放置在我们试图适应的 x,y 空间中。（也就是说，如果我们在最下面一行，并且从我们的位置到底部只有 4 个“点”，请不要尝试高 8 个的点）。
  3. 不复制板，而是使用 placePiece 和 removePiece 或类似的东西。
  4. 检查“无效”板，也就是如果一块无法触及（完全装箱）。

有人对我如何更快地做到这一点有任何创造性的想法吗？或者有什么方法可以数学计算有多少种不同的组合？

4

2 回答 2

3

我没有看到任何明显的快速做事的方法，但这里有一些提示可能会有所帮助。

首先，如果你忽略凹凸，你有一个 6x4 的网格来填充 1x2 块。每个块有 6 个位置，可以有一个凸起或一个孔。因此，您试图找到块的排列方式，以便在每个边缘处，凸起与孔相匹配。此外，您可以使用此信息更有效地表示片段。

接下来，我建议尝试所有方法将块放置在特定位置，而不是所有地方都可以在任何地方播放特定块。这将减少您走下的错误路线的数量。

于 2012-10-23T19:42:09.943 回答
1

这看起来像Exact Cover Problem。你基本上想用你给定的部分覆盖板上的所有字段。我可以推荐Donald Knuth 出版的Dancing Links 。在这篇论文中，你找到了一个关于pentomino 问题的清晰示例，它应该可以让你很好地了解它是如何工作的。

您基本上建立了一个系统来跟踪在板上放置特定块的所有可能方式。通过放置一个块，您将覆盖该领域的一组位置。这些位置不能用于放置任何其他块。在您放置另一个块之前，所有可能性都会从问题设置中删除。跳舞链接允许快速回溯和消除可能性。

于 2012-10-24T07:21:18.633 回答