数独网格背后的概率模型是什么?

计算科学 组合学 约束
2021-11-26 16:54:54

我说的是香草数独游戏,9x9 网格平均分为 9 个区域。

我尝试了几种方法来估计特定数字在特定位置的概率,但我似乎无法找到正确的模式。

假设我有这个(部分)网格:

部分数独网格

什么样的计算或方法可以帮助我找到在任何空闲位置获得 8 的概率?

直觉上,我认为在最左边的两个方格的任何空闲位置都有 50% 的机会出现 8,但我不太确定对于最右边的几乎空的方格该怎么想。

(我确实意识到这个具体的例子有多种解决方案;我想不出一个只有一个解决方案但不容易解决的方案。)


编辑我还意识到,由于“好”数独只有一个解决方案,正如 Thomas Andrews 指出的那样,某个位置包含 8 的概率是 0 或 1。

因此,让我们假设当且仅当它可以通过裸单或隐藏单技术找到时,我可以 100% 确定地确定正方形的值(即,数字要么是正方形的唯一可能选项,要么没有其他地方可以编号)。这两种技术只够解决最基本的数独问题。

如果我选择只使用这两种技术来观察网格,即使我会卡在某个状态,仍然可以列举几个起初看起来合法的后续状态,而且很明显,它们中的许多会结果重叠。例如,以上面的部分网格为例,几个后继州在第二个方格中会有一个 8。通过计算第二个正方形中 8 值的每一次出现,除以看似合法的继承状态的数量,我将得到我所说的 8 存在的概率。

问题是,即使对于计算机,计算这些也很慢。所以我想知道我可以使用什么样的数学来得到正确的答案,而无需求助于手动计数,只知道约束。

1个回答

我猜你正在寻找的概率是“给定与该行兼容的所有可能的数独谜题,其中有多少百分比在这个单一位置有 8。”

对于你给出的谜题,我倾向于 0.5 到左侧和中心正方形中的四个位置(这些显然是相关的),以及 1/3 到最右边 3x3 正方形中的三个中间行位置(它们又是相关)。

但要准确计算出这些数字需要大量的工作。