我在http://www.puzzles.ca/wordsearch/transportation.html找到了一个谜题,其中一个人必须在网格中找到单词,并且他可以从8个方向读取单词.我想到了以下问题:
我们得到了一套词.找到一个算法,将这些单词放在n x m网格中n并m给出.有没有人建议算法创建合适的网格,因为如果网格的大小只是足以使字母符合网格并且单词彼此重叠,问题似乎很难？
在该SO问题中也描述了算法
希望这可以帮助
更新:算法摘要(如前一个链接所示)
从网格中随机选择要填充的第一个空字槽,并用合适的字填充它
找到所有与已填充的单词交叉点的空单词
按约束比率对它们进行排序(例如每个可用解决方案的数量)
循环上一步的空槽并尝试一些候选词(来自可用的词)
选择单词时间和要填充的单词保留网格一致性(即网格在此单词插槽填充此单词后有解决方案),并且下一步中的解决方案数量最大(这可以最大限度地减少后续步骤中的bactracks)并转到第2步
如果在上一步中找不到任何单词,请尝试回溯到前一个单词并使用备用候选项(除非可用的候选项已用尽)
可选择重置在回溯后可能需要重置的任何字槽(即再次将其标记为空)并转到步骤2
如果没有找到回溯,则此配置没有解决方案
如果所有空插槽都已填满,则您有一个解决方案