数独空白网格背后的算法是什么?

数独的对称性中使用了数独空白网格,它需要 4×4,16×16 和更多的行和列，并带有小而不同的网格.

数独谜题可以通过数学研究来回答诸如 “多少个完整的数独网格?”, “真正的谜题中最少提示数是多少?” 和 “数独网格如何对称?” 通过使用组合和群论.

主要结果是经典数独, 完成的网格数为 6,670,903,752,021,072,936,960 (6.67×1021), 哪一个, 同时保留转换的有效性减少到 5,472,730,538 显着不同的组.

有 26 对称类型, 但它们只能在大约 0.005% 所有填充网格.

具有唯一解的谜题必须至少有 17 解决方案, 并且对于每个已解决的格子，不超过 21 解决方案. 找到的最大最小谜题有 40 线索.

类似的结果以变体和较小的网格而闻名. 数独的准确结果并不比经典的 9×9 网格更广为人知, 尽管有些估计被认为是相当准确的.

数独的计算解决方案

一个有趣的问题是, 有多少种方法可以 9 通过 9 数独网格被填充以满足单一规则?

换一种说法, 存在多少种不同的数独解决方案? 我们描述了 Bertram Felgenhauer 和 Fraser Jarvis 在早期使用的方法 2006 计算这个数字.

保持我们的语言标准, 我们称三行积木为一个网格，三列积木为栈. 此行中的一个单元格和 j 列被认为是 (一世,Ĵ).

我们称个别格数数独 N. 第一, 我们将网格块称为如下:

有多少种方法可以有效填写B1? 既然有 9 可以填B1的字符, 每个单元格中一个, 那是 9 第一个单元格的选项.

对于这些中的每一个 9 选项, 有 8 第二个单元格的选项. 对于这些中的每一个 8 选项, 有 7 留给第三个单元格.

基本上, 我们计算排列的数量 9 人物: 我们可以放置多少种方法 9 中的字符 9 地方, 或我们可以订购多少种方式 9 东西.

有 9 填写B1的方法. 从有效的B1块开始, 我们可以通过重新标记或重新排列数字来获得任何其他有效的B1块.

所以, 我们可以做的第一个简化假设是B1充满数字 1, 2, 3, …, 9 为了, 如下所示.

现在我们可以计算出这个特定的B1有多少个实际的网格结尾: 我们称之为N1. 实际的数独网格总数为N1×9!, 所以N1 = N / 9!…

让我们考虑填充 B2 和 B3 中第一行的方法. 以来 1, 2 和 3 出现在 B1 的第一行, 这些数字不能出现在其他行中.

因此, 只有数字 4, 5, 6, 7, 8 和 9 从B1的第二排和第三排可以在B2和B3的第一排相遇.

列出所有可能的方式来填充 B2 和 B3 中的第一行, 直到重新排列每个块中的数字. 提示: 有十种方式做到这一点让B2和B3的交换这十种方式给你十种方式, 一共二十个.

我们称其中两种可能性为纯顶线: 当数字 {4,5,6}, 如B1第二排, 一起存储在 B2, 和数字 {7,8,9}, 如B1第三排, 一起存储在 B3, 和这个的改变版本.

其他可能性是混合顶线, 当他们混合套装时 {4,5,6} 和 {7,8,9} 用于填充 B2 和 B3 的第一行时.

给定网格第一行的这二十种可能性 (直到重新排列每个块中的数字), 我们可以弄清楚如何填充第一行.

想想如何从纯顶行开始完成第一个乐队 1,2,3;{4,5,6};{7,8,9}.

(注意: 我们正在写一个,b,c 表示数字的有序三元组和 {一个,b,C} 以任何顺序表示它们。)

总共有多少种可能性, 在 B2 和 B3 的每一行中计算不同的数字排序? 这个数字是否与其他纯顶行相同, 1,2,3;{7,8,9};{4,5,6}?

记得, 我们希望保持 B1 不变，因为我们已经考虑了通过重新标记其中的九位数字可以获得的网格数量.

原来有 (3!)⁶ 用纯顶行盯着第一排的方法 1,2,3;{4,5,6};{7,8,9}.

这是因为我们被迫把 {7,8,9};{1,2,3} 在 B2 和 B3 的第二行和 {1,2,3};{4,5,6} 在第三行, 然后我们可以重新排列B2和B3六行中的每一行的三个数字，得到所有的配置.

另一个纯顶行的答案是一样的, 因为在这种情况下，我们所做的只是将 B2 与 B3 交换.

混合顶行的情况比较复杂. 让我们考虑第一行 1,2,3;{4,6,8};{5,7,9}. 这可以完成到第一个波段，如下图所示, 其中一个, b, 和 c 是数字 1, 2, 3 以任何顺序.

选择一个后, b 和 c 是任意顺序的剩余两个数字, 因为它们在同一行.

由于一个, 可以跳过B2和B3的六个集合中的每个集合中的三个数字，以获得不同的有效首页, 在这种情况下，配置总数为3×(3!)6.

您可以类似地处理其余十七个前排案例中的每个案例，以得出相同的数字.

现在我们有了B1定义的可能的首页数量: 这是2×(3!)6+18×3×(3!)6= 2612736, 其中总和的第一部分是来自净顶行的第一页完成的数量，第二部分是来自混合顶行的第一页完成的数量.

而不是计算其中每一个的首页完成次数 2612736 特征, Felgenhauer 和 Jarvis 从顶部空白处确定哪些首页的首页完成次数相同.

这种分析减少了计算时要考虑的首页数量.

这是一些使第一个范围网格的结尾数保持不变的操作: 记下数字, 聆听第一范围内的任何障碍, 侦听任何块中的列并侦听范围的三行. 随着这些B1的任何变化, 我们可以重新标记数字以恢复其标准格式.

安排B1, B2和B3保留网格结尾的数量, 因为如果我们从任何实际的数独网格开始, 保持真实的唯一方法是标记B4, B5, B6和B7, B8, B9 分别使堆栈保持不变.

换一种说法, 每个实际的首页网格终止都给出了一个实际的首页网格终止, 即. 任何 B1, B2, B3 排列.
确保在下一个 Sudoko 网格中将 B2 更改为 B3, 保持网格有效的唯一方法是将 B5 更改为 B6 并将 B7 更改为 B8. 这将保持堆栈相同, 虽然他们的位置已经改变.

如果您有一个有效的数独网格并且您正在跳过任何 B1 中的列, B2 和 B3, 您将如何处理 Sudoku 网格其余部分的列以使其保持有效? 例如, 如果您更改了列 1 和 2 上述网格上的 B2, 您将如何修复生成的网格以使其满足单一规则?

最后一个练习告诉我们，前排网格的每次填充都会对前排网格进行独特的填充，并且在块内跳过列.

这样的考虑使我们可以减少计数时要考虑的特定首页的数量.

跟随费尔根豪尔和贾维斯, 我们滚动浏览 B2 和 B3 列，以便每列的顶行条目按升序排列, 然后根据需要交换 B2 和 B3 以使第一个 B2 条目小于 B3 条目.

这称为字典缩写.

由于这两个块中的每一个都有 6 列重排和块重排的两种方式, 字典速记告诉我们, 给定第一页, 有 62×2=72 个其他首页具有相同数量的网格结尾.

所以现在我们只需要考虑 2612736/72=36288 个首页.

对于这些可能性中的每一种，让我们看看所有三个顶部块的重新排列: 有 6. 他们每个人都有 63 每个块内的列重新排列.

执行这些操作后, 我们重新标记以将 B1 恢复为其标准形式.

同样, 我们可以覆盖该组的前三行并重新标记以将 B1 恢复为标准形式. 这些操作节省了前排网格完成的数量.

Felgenhauer 和 Jarvis 使用计算机程序确定这些操作减少了要考虑的首页数量 36288 只 416.

让我们考虑第一组.

对其执行各种操作以保存其网格结尾的数量. 你可以从以下开始: 交换第一排和第二排. 重新标记它，使 B1 处于其标准形式. 按字典顺序减少此网格.

最重要的是，您开始的组和您完成的其他组具有相同数量的完成数，直到完整的数独网格.

从而, 而不是计算每个组的网格结束数, 我们只能为其中之一计算.

还有更多步骤可以减少要考虑的网格数量. 如果我们有一对数字 {一个,b} 在一列中，a 在第 i 行，b 在第 j 行, 并且同一对在另一列中，b 在第 i 行，a 在第 j 行, 每对将有一个与原始网格末端数量相同的乐队.

这是因为每一对都位于同一列, 当两者同时改变时, 保存一条规则, 这也满足所涉及的行.

举个例子, 看数字 8 和 9 上例的第六列和第九列. 考虑所有可能的左费根豪尔和贾维斯的情况 174 第一个 416 组继续.

他们还考虑了位于两个不同列或行中的同一组数字的其他配置, 可以在它们的列或行中省略, 保持网格末端的数量不变.

这将首页的数量减少到 71, 并搜索其中的每一个 71 案例向他们表明，实际上只有 44 要找到网格完成数的首页.

这些中的每一个 44 乐队在整个网格中具有相同数量的结尾.

让 C 表示其中之一 44 条纹. 然后你可以计算出C可以完成完整数独网格的方式数: 称它为nc.

我们还需要共享该网格 nC 结尾数的 mC 头版的数量. 然后, 数独网格的总数只是 N=ΣCmCnC, 或所有 mCnC 的总和 44 条纹.

Felgenhauer 和 Jarvis 编写了一个计算机程序来进行最终计算.

他们以标准形式计算了 B1 的 N1 有效完成数, 从...开始 44 车道. 然后他们将这个数字乘以 9! 得到答案.

他们发现可能的数量 9 通过 9 数独网格为 N=6670903752021072936960, 大约是 6.671×1021.

文章和图像信用:

HTTP://pi.math.cornell.edu/~mec/Summer2009/Mahmood/Count.html