前一段时间，我用 Haskell 编写了一个数独求解器，就像许多其他人所做的那样 - 这是一个很好的实践项目。它使用简单的蛮力算法：找到一个空方块（如果没有空方块，则谜题已解决），确定空方块中可以放入哪些值，然后对于每个可能的值，将值放入该方块中并求解递归生成的网格。这一切都运行得很好，大约需要三秒钟就能解决这个在 2012 年被称为有史以来最难的数独谜题的谜题。
由于我喜欢做杀手数独谜题，因此我将注意力转向扩展求解器，以便它也可以解决杀手数独。如果您不熟悉这个变体，我应该解释一下，杀手数独网格分为多个区域，每个区域包括 2 到 9 个方格，并具有与之相关的总数。在有效的解决方案中，每个区域中的方格都包含不同的值，这些值加起来就是该区域的总和。这是对普通数独规则的补充，即 1 到 9 中的每个值必须在每行、每列和每框中出现一次；区域给出的附加信息意味着杀手网格没有必要使用解决方案中的某些值进行播种。
我通过扩展解决常规谜题的算法来实现这一点，以便在常规谜题和杀手谜题上以多态方式工作。从本质上讲，这意味着计算出哪些数字可以放入特定的空正方形中需要考虑包含该正方形的区域以及行、列和框的约束。
我单独测试了解决方案中的每个功能，它们似乎都有效；但是当我在一个杀手谜题示例上运行求解器时，它永远不会终止，我不明白为什么。不过，解决常规谜题仍然可以完成。所以我的问题是：
代码中是否有任何我没有发现的内容（https://github.com/hicksjduk/sudoku-haskell/blob/main/sudoku.hs），哪些内容会使求解器挂起？
我可以使用哪些工具来检查代码的执行情况，并找出导致挂起的原因？
有关信息，我通过将代码文件加载到
ghcisudoku puzzlesudoku killerPuzzle感谢那些回复的人。现在看来很清楚，我的算法没有任何问题，只是它的效率不够高，无法在可接受的时间内运行。我知道这一点是因为我已经针对一个杀手谜题运行了它，该谜题在我找到它的网站上被评为“简单”，尽管花了几分钟，但找到了正确的解决方案。 （我最初使用的谜题被评为“令人震惊”，并且仍然需要比我准备等待的时间更长的时间来解决。）
我已经实现了一项优化，旨在首先用最少的选项求解正方形 - 区域列表按每个区域可以包含的可能值的数量升序排序，并且在查找空正方形时，将在其中搜索正方形它们的区域在排序的区域列表中出现的顺序。但由于大多数区域可以包含所有可能的值，这显然是不够的。
将应用于标准谜题的算法与应用于 Killer 谜题的算法进行比较，很明显，对出现在正方形中的值的额外约束（与区域相关）是花费大量额外时间的部分，所以我认为这就是我需要集中优化工作的地方。我尝试了另一种优化，通过缓存
combinations因此，当时间允许时，我将继续寻找进一步的优化，如果找到，我将更新此答案。