的快速算法创建一个谜 [英] A fast algorithm for creating a puzzle
问题描述
我发现<一个拼图href="http://www.puzzles.ca/wordsearch/transportation.html">http://www.puzzles.ca/wordsearch/transportation.html其中一个必须找到字在网格和他（她）可以从8个方向读单词。提出了我的脑海里以下问题：
I found a puzzle in http://www.puzzles.ca/wordsearch/transportation.html where one has to find word in a grid and (s)he can read words from 8 directions. The following question raised to my mind:
我们一直在给一组字。查找算法放入 n×m个的那些话电网，其中 N 和 M 给出。有没有人有建议的算法，创建合适的网格，这个问题似乎很难如果网格的大小仅刚够容纳字母的网格，字彼此重叠？
We have been given a set of words. Find an algorithm which puts those words in n x m grid where n and m are given. Does anyone have suggestions for an algorithm to create suitable grid as the problem seems difficult if size of the grid is only just enough to fit alphabets to the grid and words overlaps each others?
推荐答案
这是算法在此等问题还介绍
An algorithm is described in this SO question also
<一个href="http://stackoverflow.com/a/23435654/3591273">http://stackoverflow.com/a/23435654/3591273
希望这有助于
更新：的算法摘要（如previous链接中给出）
UPDATE: Summary of an algorithm (as given in previous link)
-
随机选择的第一个空wordslot从网格填充并用合适的词填入
Randomly select the first empty wordslot to be filled from the grid and fill it with a suitable word
查找有交点所有空wordslots已经充满wordslots
Find all empty wordslots that have intersections to already filled wordslots
通过约束率（可用的解决方案为每一位如数字）进行排序
Sort them by a constraint ratio (eg number of available solutions for each one)
遍历previous一步的空槽，并尝试了一些候选词（从可用的话）
Loop through the empty slots of previous step and try a number of candidate words (from the available words)
选择的wordslot和字来填补，其保存格一致性（即网格具有这个字槽填充有该单词后的溶液），并在接下来的步骤解的数目是最大（这在最小化bactracks接下来的步骤），然后转到步骤2
Select the wordslot and the word to fill that retains grid consistency (ie grid has a solution after this word slot is filled with this word) and also the number of solutions in next step is maximum (this minimises bactracks in next steps) and go to step 2
如果没有字previous一步发现，试图原路返回到previous字和使用替代人选（除非考生可用尽）
If no word found in previous step, try to backtrack to a previous word and use an alternative candidate (unless available candidates are exhausted)
可选复位，可能需要原路返回后重置任何字槽（即它们标记为再次空），然后转到步骤2
Optionally reset any word slots that might need reset after the backtrack (ie mark them as empty again) and go to step 2
如果没有原路返回，然后找到这个配置无解
If no backtrack found then this configuration has no solution
如果所有的空槽填满你有一个解决方案
If all empty slots are filled you have one solution
这篇关于的快速算法创建一个谜的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
