相信很多人思考过怎么hack最简深搜,但是这玩意并不好找……
我也思考,所以我在stackoverflow提了个问顺便收集现状。(谷歌爷爷Peter Norvig都写过博客关于找这样的题)
然而8年过去了还是只有我更新了两下问题,没人回答,但是最后一次更新找到了一篇论文试图找这样的数据,并分析卡在哪里。
至于用上位运算的基操dfs我也在这里写了一个。
首先为了优雅,肯定题目要是单解,难度就更加大,有一些虽然证明无二解要很长时间,但是找到第一个解就跑还是很快,于是要推迟找到首个解的时间。
上数据
搜完比较慢,但首解很快
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
比较强
..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9
论文找的超强
9..8...........5............2..1...3.1.....6....4...7.7.86.........3.1..4.....2..
建议加入数据,并希望大家也来探索(
其实另外在数独中间状态的“最基本判断”里,还有一个方面是对偶的,这个定义下的“最简单深搜”多数没有管:管了“一个格子没有侯选数”,但没管“某行某列某宫没有任何一格可能填这个数”。