如何生成5x5数独谜题?

4

我编写了一个生成5x5数独难题的算法。下面是它的工作原理:

我的5x5数独只有两个约束条件,每行和每列只能有一种数字。

  1. 生成随机位置(0,4)

  2. 如果该位置已填充,返回第1步

  3. 生成随机数字(1,5)

  4. 如果该行或该列中已经存在该数字,返回第3步

  5. 将数字填入位置

  6. 如果还有空位置,返回第1步

  7. 删除随机数字

这个算法有两个主要问题:

  1. 该算法会产生死锁。因此,我检查重试次数,如果尝试填充某个位置的次数超过10次,我就需要彻底重置并重新开始。

  2. 该算法速度太慢。由于我正在为移动设备设计数独游戏,所以需要进行优化。在我的Nexus 5上可能需要长达5秒,而在旧的三星Galaxy Trend上则可能需要长达2分钟。

1个回答

8
你可以通过使用保持约束条件的转换来替换步骤1-6,从而开始一个已知的有效填充网格。
例如,你可以从这个网格开始,通过将grid[i][j]设置为((i + j) % 5) + 1来轻松生成它:
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4

然后,如果你交换两行,你仍然会得到一个有效的网格,例如,交换第一行和第三行:
1 2 3 4 5
4 5 1 2 3 <
3 4 5 1 2
2 3 4 5 1 <
5 1 2 3 4

您还可以交换两列,仍然得到一个有效的网格,例如交换第2列和第4列:

1 2 5 4 3
4 5 3 2 1
3 4 2 1 5
2 3 1 5 4
5 1 4 3 2
    ^   ^

所以,首先使用常规网格,在循环内部生成随机行和列的对,并交换它们。您还可以交换数字(例如,将所有5更改为3,反之亦然)。您总是会得到有效的结果。
然后可以继续进行第7步。
但是,第7步比看起来更复杂,因为您需要使谜题可解。换句话说,每个时刻玩家都应该能够在不猜测的情况下逻辑推断出至少一个单元格的值。
因此,您需要编写一个函数,使用约束条件计算空单元格的有效值列表(您只需要一个所有未出现在同一行或列中的值的列表)。在第7步中删除数字时,在循环内部:
- 选择一个随机单元格 - 基于网格中的其他非空单元格计算该单元格的有效可能值 - 如果只有一个可能的值(即单元格中的值),则可以将其删除
单元格的值可以被推导出来的另一种方法是,如果它是该值在其行或列中唯一可能的单元格,则可以确定它。要验证这一点,您需要为该单元格所在行或列中的每个单元格计算一个有效值列表(不在同一行或列中的其他非空单元格中不存在的值),即使单元格包含多个可能的值,如果它是其行中包含该值列表的唯一单元格,或者是其列中的唯一单元格,则可以确定该值,因此可以将其删除。
您可以重复此过程,直到删除所需数量的单元格。因为每个已删除的单元格在其被删除时都能够被推导出来(因为它是单元格为空后仅可能的值),因此玩家应该能够通过以与删除顺序相反的顺序添加值来解决谜题。
如果这不产生足够“有趣”的谜题,则可以采用“欺骗”方法,即拥有一组手动创建的现有谜题数据库,然后选择一个并通过随机交换行和列或交换数字进行混淆。这可能会涉及某些版权问题,作为“衍生作品”,但这不是编程问题。

如果有多个,则替换为一个。 - zarcel
我是说把你移除的值放回去,然后尝试另一个随机单元格。 - samgak
2
你也可以对数字进行置换,但是即使这样,这种方法也无法生成每个可能的谜题,因为5阶拉丁方具有多个主类。 - David Eisenstat
1
@DavidEisenstat 很有趣。在这种情况下,您可以存储每个主类的起始配置(根据维基百科,5x5只有2个主类),然后随机选择其中一个。 - samgak

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接