生成最小/束缚数独 [英] Generating minimal/irreducible Sudokus

问题描述

一个数独题是最小的（也称不可约），如果它有一个独特的解决方案，但是，消除任何数字将产生多个解决方案的难题。换句话说，每一个数字是必要确定该溶液中。

A Sudoku puzzle is minimal (also called irreducible) if it has a unique solution, but removing any digit would yield a puzzle with multiple solutions. In other words, every digit is necessary to determine the solution.

我有一个基本的算法来生成最小的数独：

I have a basic algorithm to generate minimal Sudokus:

• 生成一个完整的拼图。
• 访问每个小区随机顺序。对于每一个所在小区：
  • 姑且删除其位
  • 在解决这一难题使用递归回溯算法的两倍。一个求解尝试数字1-9以正向顺序，其他顺序相反。在某种意义上，该解算器遍历包含所有可能的配置搜索树，但是从相对的两端。这意味着的两个解决方案将匹配当且仅当拼图有一个独特的解决方案
  • 如果这个难题有一个独特的解决方案，永久删除的数字;否则，将它放回
  • Generate a completed puzzle.
  • Visit each cell in a random order. For each visited cell:
    • Tentatively remove its digit
    • Solve the puzzle twice using a recursive backtracking algorithm. One solver tries the digits 1-9 in forward order, the other in reverse order. In a sense, the solvers are traversing a search tree containing all possible configurations, but from opposite ends. This means that the two solutions will match iff the puzzle has a unique solution.
    • If the puzzle has a unique solution, remove the digit permanently; otherwise, put it back in.

    此方法保证产生最小的难题，但它很慢（100毫秒我的电脑上，几秒钟的智能手机）。我想，以减少解决了一些，但都是明显的方式我能想到的不正确。例如：

    This method is guaranteed to produce a minimal puzzle, but it's quite slow (100 ms on my computer, several seconds on a smartphone). I would like to reduce the number of solves, but all the obvious ways I can think of are incorrect. For example:

    • <强>添加的位数而不是删除它们。这样做的优点是，由于极小的难题需要至少17填充位时，第一17位都保证没有唯一的解决方案，减少的量求解。不幸的是，因为细胞被访问以随机的顺序，许多不必要的数字将是锁定了的独特的解决方案的其中一个重要数字之前加入。例如，如果第一9细胞中加入都是在同一列，有一个很大的冗余信息在那里。
    • 如果没有其他数字都可以替换当前，保持并没有解决这一难题。由于检查是否一个位置是合法的数千倍比解决这一难题的两倍快，这可能是一个巨大的节省时间。然而，仅仅因为没有其他合法的数字现在并不意味着就不会有后来有一次，我们删除其他数字。
    • 由于我们产生了原来的解决方案，解决问题，只是每个单元一次，看看它原来的匹配。这不工作，因为原来的解决方案可能是可能的解决方案的搜索树内的任何地方。例如，如果原始溶液是邻近树的左侧，我们开始从左侧搜索，我们将错过右侧树的解决方案。
    • Adding digits instead of removing them. The advantage of this is that since minimal puzzles require at least 17 filled digits, the first 17 digits are guaranteed to not have a unique solution, reducing the amount of solving. Unfortunately, because the cells are visited in a random order, many unnecessary digits will be added before the one important digit that "locks down" a unique solution. For instance, if the first 9 cells added are all in the same column, there's a great deal of redundant information there.
    • If no other digit can replace the current one, keep it in and do not solve the puzzle. Because checking if a placement is legal is thousands of times faster than solving the puzzle twice, this could be a huge time-saver. However, just because there's no other legal digit now doesn't mean there won't be later, once we remove other digits.
    • Since we generated the original solution, solve only once for each cell and see if it matches the original. This doesn't work because the original solution could be anywhere within the search tree of possible solutions. For example, if the original solution is near the "left" side of the tree, and we start searching from the left, we will miss solutions on the right side of the tree.

    我也想优化求解算法本身。困难的部分是确定一个解决方案是独一无二的。我可以让微优化，如创建法定存款为每个小区的位掩码，如<一个描述href="http://webcache.googleusercontent.com/search?q=cache%3awww.byteauthor.com/2010/08/sudoku-solver/">this精彩的帖子。然而，更先进的算法，如舞蹈链或模拟退火算法的设计并不确定唯一性，但只是为了找到的任意的解决方案。

    I would also like to optimize the solving algorithm itself. The hard part is determining if a solution is unique. I can make micro-optimizations like creating a bitmask of legal placements for each cell, as described in this wonderful post. However, more advanced algorithms like Dancing Links or simulated annealing are not designed to determine uniqueness, but just to find any solution.

    我如何优化最少的数独发生器？

    推荐答案

    下面是我在速度（高度近似）百分比的增加实现的主要优化：

    Here are the main optimizations I implemented with (highly approximate) percentage increases in speed:

    • 使用位掩码以跟踪哪些约束（行，列，框）被满足每个小区中。这使得它更快地查找一个位置是否是合法的，但速度较慢，使一个位置。在产生的困惑与位掩码，而不是仅仅解决这些问题，一个复杂的因素是，数字可能要被删除，这意味着你需要跟踪的三种类型的约束不同的位的。一个小的进一步优化是拯救口罩每个数字和阵列每个约束。 40％
    • 定时出来的一代，如果时间过长重新启动。请参见这里。最佳的策略是增加超时期间每个失败产生之后，以减少它的推移无限期的机会。 30％，主要是从减少最坏情况下的运行时间。
    • mbeckish和user295691的建议（见注释到原来的职位）。 25％
    • Using bitmasks to keep track of which constraints (row, column, box) are satisfied in each cell. This makes it much faster to look up whether a placement is legal, but slower to make a placement. A complicating factor in generating puzzles with bitmasks, rather than just solving them, is that digits may have to be removed, which means you need to keep track of the three types of constraints as distinct bits. A small further optimization is to save the masks for each digit and each constraint in arrays. 40%
    • Timing out the generation and restarting if it takes too long. See here. The optimal strategy is to increase the timeout period after each failed generation, to reduce the chance that it goes on indefinitely. 30%, mainly from reducing the worst-case runtimes.
    • mbeckish and user295691's suggestions (see the comments to the original post). 25%

    这篇关于生成最小/束缚数独的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！