q****x
发帖数: 7404 | 1 贪心法，选所在行、列和3x3方阵已定元素最多的格子起？
看了一下，相当复杂。45分钟只能上递归吧？
http://en.wikipedia.org/wiki/Sudoku_algorithms |
s****j
发帖数: 67 | 2 dancing link，速度很快
【在 q****x 的大作中提到】
: 贪心法，选所在行、列和3x3方阵已定元素最多的格子起？
: 看了一下，相当复杂。45分钟只能上递归吧？
: http://en.wikipedia.org/wiki/Sudoku_algorithms
|
f*******t
发帖数: 7549 | |
q****x
发帖数: 7404 | 4 这玩意能现想出来，那比Knuth还牛了。
【在 f*******t 的大作中提到】
: 好像有个什么dancing link
|
s****j
发帖数: 67 | 5 dancing link关键是建模，不是后面的递归。后面的准备两套模板套上去就行，一个针
对不能重叠的exact cover，一个针对可以重叠的。dlx的精妙在于前面模型的转化。
当然你要说45分钟完整写出程序，那确实很困难。
【在 q****x 的大作中提到】
: 这玩意能现想出来，那比Knuth还牛了。
|
q****x
发帖数: 7404 | 6 写了个递归的完整版，120行，用wiki上的例子测试通过，共用一个多小时。
面试肯定要写伪码。其实递归函数本身也就15行。
【在 s****j 的大作中提到】
: dancing link关键是建模，不是后面的递归。后面的准备两套模板套上去就行，一个针
: 对不能重叠的exact cover，一个针对可以重叠的。dlx的精妙在于前面模型的转化。
: 当然你要说45分钟完整写出程序，那确实很困难。
|
B*******1
发帖数: 2454 | 7 贴个代码瞧瞧，让大家review学习一下吧。
【在 q****x 的大作中提到】
: 写了个递归的完整版，120行，用wiki上的例子测试通过，共用一个多小时。
: 面试肯定要写伪码。其实递归函数本身也就15行。
|
