填字游戏发电机（瑞典填字游戏） - Java

我正在尝试创建一个简单的Java生成器填字游戏（瑞典填字游戏） - 只是为了好玩。我从网上下载了词汇单词（约300,000字）。这些词我保存在一个HashMap（按字长排序）。发生器的输入是X和Y的大小以及拼图。拼图我随机插入矩阵填字游戏发电机（瑞典填字游戏） - Java

但我不能找出一个工作算法来填补矩阵的其余部分。

例如：

X X X X 
X D O G 
X X X X

没有任何人有什么建议吗？或者在互联网上的一些有用的文章？谢谢。

你有什么，只要填充算法？任何尝试？ – wumpz

我没有发明任何东西，我只能将单词添加到拼图（在我们的例子DOG），而且不知道 – user3392947

可能重复[算法生成一个纵横]（http://stackoverflow.com/questions/943113/算法生成一个填字游戏） –

更新编译填字游戏（如瑞典，斯堪的纳维亚，等。）这里的算法描述（除其他外，当然:)）

：发布算法的主要步骤描述在给定的SO链路（每注释）

该算法的第一步是在随机选择一个空wordslot（栅格字）并从其相关联的单词表与候选字填充（RA （1）或O（N））
对于每个仍然为空的单词槽（与已经填充的单词槽有交点），计算一个约束率（这可能会有所不同，简单地说就是该步骤中可用解决方案的数量），并按照该比率（复杂度O（NlogN）或O（N））排序空单词空间。循环遍历在先前计算的空单词步骤，并为每一个尝试一些cancdidate解决方案（确保“弧一致性是保留”，即网格有一个解决方案后，这一步，如果这个单词被使用）和排序他们根据最大可用性下一步（即下一步一步有最大可能的溶胶如果utions这个词在那个地方使用在那个时候，等..）（复杂度为O（N * MaxCandidatesUsed））
填补字（标记为填补，转到步骤2）
如果没有发现满足步骤.3的标准的词，尝试回溯到某个先前步骤的另一个候选解决方案（标准可以在此变化）（复杂度O（N））
如果找到了回溯，重置可能需要重置的任何已填充的单词（将它们标记为未填充）（复杂度O（N））
如果发现没有回溯，无溶液可以发现（至少与该结构中，初始种子等）
否则当所有wordlots填充有的话溶液

该算法对问题的解决方案树执行随机一致的步骤。如果在某一时刻有死胡同，它会回溯到前一个节点并沿着另一条路线前进。直到找到的解决方案或用于各个节点的候选人数量都用尽。

一致性部分可确保找到一个解决办法确实是一个解决方案，并随机部分能够产生不同的执行，也的平均不同的解决方案有更好的表现。

PS试图避免复制粘贴不同的，所以答案之间回的往复，但确定可能是一些总结可能是有用的

2014-05-02 20:25:14

虽然这个链接可能回答这个问题，但最好在这里包含答案的重要部分，并提供供参考的链接。如果链接页面更改，则仅链接答案可能会失效。 –

@AndrewMedico好的，发布编辑后，你现在可以删除否定的投票吗？如果不是，那么也许你应该添加你的评论，并等待看看我是否修复这个帖子，如果没有，然后投票，只要你喜欢，够公平吗？ –

我没有投票。 –

回答