Dr.Fill: Crosswords and an Implemented Solver for Singly Weighted CSPs
Dr.Fill: Crosswords and an Implemented Solver for Singly Weighted CSPs
复制标题
Dr.Fill：填字游戏和单加权 CSP 的实现求解器
DOI：
10.1613/jair.3437
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
M. Ginsberg
中科院分区：
文献类型：
--
作者：
M. Ginsberg
我们描述填充博士，一个程序，解决美国式的填字游戏。从技术的角度来看，Fill博士的工作原理是将填字游戏转换为加权csp，然后使用各种新颖的技术来找到解决方案。这些技术包括变量和值选择的一般适用的算法，有限差异搜索的变体，以及后处理和分区思想。没有使用分支和界限，因为它与后处理不兼容，并且实验确定没有什么实用价值。Fill博士在美国填字游戏锦标赛上的填字游戏表现表明，它在世界上排名前50位左右。
We describe Dr. Fill, a program that solves American-style crossword puzzles. From a technical perspective, Dr. Fill works by converting crosswords to weighted csps, and then using a variety of novel techniques to find a solution. These techniques include generally applicable heuristics for variable and value selection, a variant of limited discrepancy search, and postprocessing and partitioning ideas. Branch and bound is not used, as it was incompatible with postprocessing and was determined experimentally to be of little practical value. Dr. Fill's performance on crosswords from the American Crossword Puzzle Tournament suggests that it ranks among the top fifty or so crossword solvers in the world.