如何生成5x5数独谜题？

Question

我已经编写了算法来生成5x5数独游戏.下面是它的工作原理.在我的5x5数独游戏中,只有两个限制.每行和每列只能有一种项目.

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

2. 如果填补了位置,请返回1.

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

4. 如果行或列中已有此数字,请返回3.

5. 用数字填充位置

6. 如果剩下免费地点,请返回1.

7. 删除随机数.

有两个主要问题.

1. 此算法生成死锁,因此我检查尝试,如果有超过10次尝试填充位置,我重置一切并重试.

2. 太慢了.由于我为移动设备设计了数独游戏,我需要优化它.我的nexus 5需要长达5秒钟,而旧三星星系趋势需要长达2分钟.

Answer 1

您可以通过从已知的有效填充网格开始替换步骤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行和第3行:

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
    ^   ^

因此,只需从常规网格开始,然后在循环内部生成一对随机行和一对随机列,并交换它们.您也可以交换数字(例如将所有5s更改为3s,反之亦然).您将始终获得有效的结果.

然后,您可以继续执行第7步.

然而,步骤7比看起来更复杂,因为你需要你的谜题可以解决.换句话说,在每个点上,玩家应该可以在不猜测的情况下逻辑地推断出至少一个单元的值.

因此,您需要编写一个函数,使用约束来计算空单元格的有效值列表(您只需要列出同一行或列中不存在的所有值).在步骤7中删除数字时,在循环内:

• 选择一个随机单元格
• 根据网格中的其他非空单元格计算该单元格的有效可能值
• 如果只有一个可能的值(单元格中的值),则可以将其删除

可以推导出单元格值的另一种方式是它是否是其行或列中唯一可以使用该值的单元格.要验证这一点,您需要为单元所在的行或列中的每个单元计算有效值列表(在同一行或列中的其他非空单元格中不存在的值),即使cell包含多个可能的值,如果它是其行中唯一包含该列表中的值的单元格,或者列中唯一的单元格,则可以确定该值,因此可以将其删除.

您可以重复此操作,直到删除了所需数量的单元格.因为您删除的每个单元格都可以在删除时推断出(因为它是单元格为空时唯一可能的单元格值),所以玩家应该能够通过添加值来解决难题他们被删除的顺序相反.

如果这不是产生"有趣"足够的谜题,那么你可以采取"欺骗"方法,即拥有现有手工创建的谜题数据库,然后选择一个并通过随机交换行和列来加扰它,或者交换数字.这可能有一些版权问题作为"衍生作品",但这不是一个编程问题.