本文将主要介绍人工解数独时采用的唯余法的算法实现,并给出将其改造成迭代加深算法时,解所在最低层数的确定。
唯余法
当数独谜题中的某一个宫格,因为所处的列、行及九宫格中,合计已出现过不同的 8 个数字,使得这个宫格所能填入 的数字,就只剩下那个还没出现过的数字时,我们称这个宫格有唯余解。
可以看到,唯余法就是利用排除法得出数独某个位置可能的唯一解。但在人工用这种方法解数独时,可能会出现以下问题:
- 只剩唯一解的数独格子难以直接观察得到。采用唯余法观察时,行,列,宫格的重复性都要考虑,
对人的视力提出了巨大的挑战。 - 可能,而且很可能不存在能直接确定答案的数独格子。比如可能排除到最后,这个格子还剩 4 和 6 能填,确定不了具体需要填哪一个数。