首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >Tetravex算法

问Tetravex算法
EN

Stack Overflow用户
提问于 2010-02-08 09:47:43
回答 5查看 2.6K关注 0票数 6

嗯,我正在考虑做一个Tetravex求解程序,以练习我的代码编写技能(语言可能是Visual Basic),我需要帮助找到一个求解它的算法。对于那些不知道什么是tetravex的人来说,可以看看这个http://en.wikipedia.org/wiki/TetraVex。我能想到的唯一算法是蛮力方式,将一个瓷砖随机放置在一个角落,然后尝试每一个可能的瓷砖旁边,继续相同的过程,如果它到达死胡同,恢复到以前的状态,并放置一个不同的瓷砖。那么有没有人能想出一个更好的算法呢?谢谢您抽时间见我。

EN

回答 5

Stack Overflow用户

回答已采纳

发布于 2010-02-09 03:10:17

这里有一些想法。

一种简单的暴力算法会尝试以递归的方式填充网格,方法是以固定的顺序枚举网格位置(例如,行大小),并总是尝试将每一个可能的部分都放在当前位置,然后递归。这就是你提到的,它的效率非常低。

一个改进是始终计算每个自由位置的拟合件数,然后在拟合最少的位置上递归;如果有零个拟合件,立即回溯;如果有一个只有一件拟合,则填充该位置并继续(未创建分支);否则选择具有最少拟合件的位置(≥2)并从那里继续。

一旦你有了这个算法,下一个问题就是如何进一步削减搜索空间。比方说,如果A块的顶部位置为"1“,B块的底部位置为"1”,并且A> B,则您知道"1 at top position“块中至少有A-B必须实际放置在顶行,因此您可以从任何其他位置排除它们。这有助于减少分支因素,并更早地发现死胡同。

您还应该在每个递归步骤中检查每个块是否至少有一个适合它的点(在验证没有任何块只适合于一个位置以提高速度后进行此检查)。如果有一块不适合任何地方,你需要立即回溯。您可以将其扩展到检查每一对块是否适合可能更好的早期死锁检查功能。

还有一种策略叫做“非时间顺序回溯”或“回跳”,它起源于对SAT求解的研究。这有助于您在到达死胡同时一次回溯多个级别;如果您愿意,您可以在google中搜索这些术语以找到更多,但您需要做一些脑力工作来将概念映射到您的问题空间中。

票数 4
EN

Stack Overflow用户

发布于 2010-02-08 09:51:02

第一个改进是计算有多少对匹配的数字,如果在正方形的顶部有5个"1“,但底部只有4个,那么一定有一个”1“指向网格的顶部。

票数 1
EN

Stack Overflow用户

发布于 2010-02-08 10:04:41

在任何给定的部分解决的棋盘上,我都会

  • 寻找一个没有剩余的牌可以玩的地方。如果找到,必须将棋盘展开到最后一个随机玩牌的地方。
  • 寻找一个只可以合法玩剩下的牌的地方。
  • 在棋盘上可以合法地玩最少数量的棋子的地方随机放置一个棋子。在铺设磁贴之前,请记住这个棋盘布局,我可能想要回退到这个棋盘并播放不同的磁贴。

在伪代码中,它将是

代码语言:javascript
复制
top:
  evaluate # of tiles that match at each empty square
  if any square has 0 matches, unwind to <prev>
  if any square has 1 match, lay tile, goto top
  save current board as <prev>
  play randomly at square with minimum number of matches, goto top

作为优化,您可以忽略不接触任何具有平铺的正方形的评估方块,因为它们将始终允许所有剩余的平铺。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/2219166

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档