The "简单/幼稚的回溯暴力算法”、数独的“直接深度优先搜索”是众所周知并已实现的。
并且似乎不存在不同的实现。
(当我第一次写这个问题时..我想说我们可以完全标准化它,但措辞很糟糕..)
我认为这个人很好地描述了算法:https://stackoverflow.com/a/2075498/3547717 https://stackoverflow.com/a/2075498/3547717
编辑:所以让我用伪代码更详细地说明它......
var field[9][9]
set the givens in 'field'
if brute (first empty grid) = true then
output solution
else
output no solution
end if
function brute (cx, cy)
for n = 1 to 9
if (n doesn't present in row cy) and (n doesn't present in column cx) and (n doesn't present in block (cx div 3, cy div 3)) then
let field[cx][cy] = n
if (cx, cy) this is the last empty grid then
return true
elseif brute (next empty grid) = true then
return true
end if
let field[cx][cy] = empty
end if
next n
end function
我想找到最需要时间的谜题。对于这种特定的“标准化”算法,我们可以称其为“最难”,但这并不像那些要求“最难的数独”的问题。
事实上,只要简单地旋转或翻转,这个定义下的“困难”谜题就可能变得超级简单。
根据“对于每个网格尝试数字1到9”的规则,它从1开始尝试,所以我们可以以某种方式让它通过使用适当的数字尝试更多,这样就不会出现排列问题。
数独谜题必须是valid,即它应该有 1 个解。Some guy http://norvig.com/sudoku.html有一个谜题需要 1439 秒,但由于没有答案而无效。
我定义所需的时间(或者说时间复杂度)相当于输入递归函数的次数。 (在我的实现中,它与上面的伪代码略有不同,因为最后一个入口,并确保唯一的解决方案等)
有没有什么好的方法来构造它,或者我们必须使用启发式算法等近似方法来找到不精确的解决方案?
我已经使用朴素策略(我在上面称为“简单”,它是唯一的)和 Peter Norvig 的“最少候选者优先”策略(我的实现是确定性的,但不是唯一的。正如 Peter 也提到的那样)实现了回溯。 python dict 的顺序会极大地改变结果,以防候选人数量平局)。
https://github.com/farteryhr/labs/blob/master/sudoku.c https://github.com/farteryhr/labs/blob/master/sudoku.c
无解方案一:
.....5.8....6.1.43.........1.5.........1.6...3.......553..... 61.........4.........
在我的笔记本电脑上花了 60 秒才得出无解结论,输入递归函数 2549798781 次(后面称为“循环”)。通过我的 LCF 实现,78308087 个循环在 30 秒内结束。这是因为寻找候选数最少的网格需要更多的操作,LCF策略的单个周期使用大约16倍的时间。
最难列表中最上面的一个:
4.....8.5.3......7......2......6.....8.4......1...... ...6.3.7.5..2.....1.4......
耗时3.0s,在第9727397个周期找到解,第142738236个周期确保解唯一。 (我的 LCF:0.004 秒内为 981/7216)
“困难”列表中的许多仍然很容易天真,尽管其中很大一部分需要 10^7 到 10^9 周期。
On 维基百科:数独求解算法 https://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Backtracking (Original https://www.flickr.com/photos/npcomplete/2361922699)据说可以通过在开始时制作尽可能多的空网格和顶行 987654321 的排列来构造此类针对回溯算法的谜题。
好在测试..
......3.85..1.2......5.7.....4...1...9.......5.. ....73..2.1........4...9
需要1.4s,69175317个周期寻找解决方案,69207227个周期确保唯一解决方案。不如Peter提供的难点,但是还好,差不多找到解决方案后,搜索就结束了。这可能就是第一行按字典顺序排列的大小的工作原理。 (我的 LCF:0.023 秒内为 29206/46160)
是的,这些是显而易见的,我只是要求更好的方法......
还有其他方法 https://www.nature.com/articles/srep00725衡量数独难度的方法(通过求解)
数独分析师 http://www.stolaf.edu/people/hansonr/sudoku/analyst.htm会陷入Peter给出的多解谜题(天真的419195/419256,LCF 2529478/2529482,是的,有一些谜题让LCF做得更糟):
.....6..59.....82....8....45.........3.........6..3.54.. .325..6.................
这对于朴素回溯 (10008/76703) 和 LCF 回溯 (313/1144) 来说都很容易,但也会让 Sudoku Analyst 陷入困境。
..53.....8......2..7..1.5..4....53...1..7...6..32...8.. 6.5....9..4..3......97..
另一个更新:
最困难的数独谜题可通过简单的深度优先搜索算法快速解决 https://www.dcc.fc.up.pt/%7Eacm/sudoku.pdf
哈,终于有人也在找了,而且还给了一个超难的!以下有效谜题:
9..8......5......2..1...3.1.....6..4...... 7.7.86..3.1..4..2..
本文将该算法命名为SDFS,Straightforward Depth-First Search。作者所说的周期数是1553023932/1884424814,而我的实现是1305263522/1584688020。是的,在弹出计数器的确切位置上会有一些差异,但基本行为是一致的。在 repl.it 的服务器上,找到答案花了 97 秒,完成搜索花了 119 秒。