如何解决将 11 个棋子放入 8x8 拼图中的问题?

人工智能 机器学习 人工智能设计 游戏-ai 组合游戏
2021-11-10 18:14:47

我试图弄清楚如何为将 11 个棋子放在一块板(8 x 8)中的难题创建一个求解器。我在http://www.xams.com.br/quebra创建了游戏每次逆时针旋转 90 度 ( Girar ) 并垂直镜像 ( Inverter ) 是可能的,因此该部分可以呈现 8 种形式。

单击求解器按钮(Resolver )时,它会尝试以粗暴的方法将棋子随机放入棋盘中(花费大量时间)。使用这种方法,我无法达到结果。

我想尝试比这更聪明的东西,并且有一个机器学习算法会很棒。我不知道如何表述这个问题。请问这个怎么开始?


编辑: 我仍在构建页面,还有很多需要改进的地方。您需要单击要放置棋子的 3x3 矩阵的中心。


编辑2: 在此处输入图像描述

1个回答

使用您的应用程序,我能够手动找到(剧透警报!)解决方案。至少现在你知道你的难题是可以解决的,而且你没有浪费你的钱 :)

不过,您的应用似乎有错误。我无法放最后一块,如图所示。我想知道您的求解器是否会找到解决方案。

现在的想法。它可能对您的求解器有用。

棋盘有 8x8=64 个方格。每件将占据 5 个方格,而您想要放置 11 件,因此最终位置将有 9 个空方格。将板分成左右两个 8x4 矩形。现在,一个矩形应该有 5 个空方格,而另一个有 4 个,这似乎是公平的;考虑到这一点,我开始先填充右侧部分,然后再填充左侧部分。经过一些尝试和错误,我很幸运。

我不知道您是否可以使用此方法获得所有解决方案。请注意,在上面给出的解决方案中,底部矩形将以 6 个空方块结束。

我也不知道如何编写一个有效的求解器。对于初学者:

  1. 建立一个不良配置列表:一小部分棋子/位置,这样每当你到达它们时,你就知道没有希望了。
  2. 在每一步,以这样的方式放置一块,它可以最大限度地减少强制空方格的数量。
  3. 上述想法的一种变体:将板分成四个 4x4 部分;每个部分至少应该有一个空方格,但没有那么多,这似乎是合理的;因此,寻找解决方案,迫使这些部分具有 (1,2,3,3) 或 (2,2,2,3) 空方格。
  4. 查找这个谜题是否已知。想到的名字:马丁·加德纳、伊恩·斯图尔特、山姆·劳埃德。

不能说您将能够看到所有可能解决方案的列表。

很好的拼图,你写的很好的应用程序,我玩得很开心。谢谢你。