最近在做scala99,其中有一道题目P97是sudoku(数独)。一开始我想到的是列举每个空格的可选数字,选择可选数字最少的的格子开始填写。每次填写,修改关联格子的可选数字。再次尝试填写。这里无解条件是存在没有可选数字的格子。还有就是easy或者normal级别的数独一般可选数字都是1个,分批填写很快就能完成。hard或以上就没有那么幸运了,必须猜测然后验证,存在回溯。
这里描述的算法其实就是搜索+启发。启发是选择性地从最少可选数的格子开始。猜测+验证,感觉这个问题属于NP问题。事实上也确实是,而且可以转化为NP完全的精确覆盖问题(Exact Cover),所以这个问题也是NP完全问题。
P97给的答案有两个,第一个就是搜索+启发,第二个是DLX。DLX是Exact Cover的高效解法。本文就是讲如何用DLX来解数独问题的。考虑到scala99上第二个实现大部分都是可变数据,所以我用Java实现了相应算法。