前些时间在手机上下了个数独游戏(Sudoku)，用以在火车上消遣时间，游戏设置了easy，medium， hard和very hard4个难度等级。一开始玩easy的，大概6-7分钟，后来试着来个hard，竟然花了30分钟，太被打击了，后来就想着来段code来节省点脑细胞。
数据游戏规则
数独游戏是一个9x9的网格，每个格子是1-9中的任意一个数，游戏开始时，部分格子是填好数字的，游戏内容就是将空白格子填上数字，使得
- 每行都没有重复数字
- 每列都没有重复数字
- 每个3x3的网格内也没有重复数字
如下图所示，这是一个Very Hard级别的数独。
游戏求解
如何来求解这个问题呢?一开始想着根据自己玩游戏的方法来处理。最直观的一条规则：
先分析出每个位置的可能值，将那些可能取值仅有1个的格子确定下来
这样就会减少该格子所在行列和子块的空格的可能取值，采用递归的方式就可以依次得到其他格子的数字。如下面图中填写的红色数字。
想法是美好的，可现实却是残酷的，搞好一运行，部分easy的可以解决，可大部分的游戏都解决不了，更不用说最前面那个Very Hard图中的那个例子了。
显然，上述规则还不够完备，导致某些问题解决不了，再仔细想想自己玩游戏的时候的思路，由于网格是9x9的，那么每行，每列和每个子块都必然包含1-9的所有数字，下面考虑同一行中的情况（同列和同子块类似）：若某个格子可取值123，但该行其他所有空行都不可能去1，那么该格子必须取1
这条规则写起来比第一个稍微复杂点，但还不算难，写好后一测，easy的基本都ok，可hard的还是搞不定，只能继续挖了。最后想到还有另外一条规则:
若同一行中，A格子可取12，B可取12，C可取123，那么可以确定AB必然1个是1另一个是2，那么C中的12就可以消掉了
规则是想到了，可不好用code来表达，结果也就这么不了了之了。
后来的某天，想到可以换个思路，电脑运算能力那么NB的，让它去遍历应该可以问题不大（当然要是写个81重的循环估计是要崩溃的，不信可以试试），简单的方式是采用深度优先的递归调用来实现，具体思路如下：
- 从上到下从左到右遍历网格，到第一个空格子出，计算出空格子可能的取值
- 给空格子依次赋一个可能值后递归调用，若该值错误，则递归到某一步会导致一个空格子没有可取的值
直接上代码：
#define SUDOKU_DIM 9#define BLOCK_SIZE 3#define SUDOKU_VALUE 9bool Solve(byte *pSudoku){ byte *pSudokuTmp = pSudoku; //======find first empty====== int idx, r, c; pSudokuTmp = pSudoku; for(idx = 0; idx < SUDOKU_DIM * SUDOKU_DIM; idx++, pSudokuTmp++) { if(pSudoku[idx] == 0) break; } if(idx == SUDOKU_DIM * SUDOKU_DIM) return true; r = idx / SUDOKU_DIM; c = idx % SUDOKU_DIM; //======find prossiable value====== bool bValuePossiable[SUDOKU_VALUE + 1]; memset(bValuePossiable, 1, sizeof(bool) * (SUDOKU_VALUE + 1)); //row pSudokuTmp = pSudoku + r * SUDOKU_DIM; for(int i = 0; i < SUDOKU_DIM; i++) { bValuePossiable[pSudokuTmp[i]] = false; } //col pSudokuTmp = pSudoku + c; for(int i = 0; i < SUDOKU_DIM; i++, pSudokuTmp += SUDOKU_DIM) { bValuePossiable[*pSudokuTmp] = false; } //block int startRow = (r / BLOCK_SIZE) * BLOCK_SIZE; int startCol = (c / BLOCK_SIZE) * BLOCK_SIZE; pSudokuTmp = pSudoku + startRow * SUDOKU_DIM + startCol; for(int i = 0; i < BLOCK_SIZE; i++, pSudokuTmp += SUDOKU_DIM) { for(int j = 0; j < BLOCK_SIZE; j++) { bValuePossiable[pSudokuTmp[j]] = false; } } //======try to decide====== for(int i = 1; i <= SUDOKU_VALUE; i++) { if(!bValuePossiable[i]) continue; pSudoku[idx] = i; bool bret = Solve(pSudoku); if(bret) return true; } pSudoku[idx] = 0; return false;} 下面是测试代码，由于这里主要关注求解方法，测试代码写得有点水，输入一个数独游戏比较麻烦：
void print_Sudoku(byte *pu8Sudoku){ printf("==============begin===============\n\n"); for(int i = 0; i < SUDOKU_DIM; i++) { for(int j = 0; j < SUDOKU_DIM; j++, pu8Sudoku++) { printf("%d ", *pu8Sudoku); if((j + 1) % BLOCK_SIZE == 0) { printf(" "); } } printf("\n"); if((i+1)%BLOCK_SIZE == 0) { printf("\n"); } } printf("============== end ===============\n");}void test_sudoku(){ byte au8Sudoku[SUDOKU_DIM * SUDOKU_DIM]={//5, 0, 0, 4, 1, 0, 0, 8, 0,//9, 0, 0, 0, 0, 0, 1, 0, 0,//8, 0, 0, 6, 7, 9, 0, 0, 5,//0, 4, 0, 7, 0, 0, 5, 9, 1,//0, 8, 0, 0, 6, 0, 0, 7, 0,//7, 9, 1, 0, 0, 3, 0, 2, 0,//1, 0, 0, 2, 5, 6, 0, 0, 9,//0, 0, 7, 0, 0, 0, 0, 0, 3,//0, 5, 0, 0, 3, 7, 0, 0, 6//0, 0, 0, 9, 0, 0, 1, 0, 2,4, 0, 0, 1, 0, 6, 0, 0, 0,0, 8, 0, 0, 2, 0, 0, 0, 5,6, 3, 0, 0, 0, 0, 5, 0, 0,0, 0, 4, 5, 0, 7, 9, 0, 0,0, 0, 5, 0, 0, 0, 0, 3, 1,9, 0, 0, 0, 6, 0, 0, 1, 0,0, 0, 0, 8, 0, 9, 0, 0, 7,7, 0, 6, 0, 0, 2, 0, 0, 0// 0, 0, 0, 4, 0, 0, 3, 0, 6,// 0, 0, 0, 7, 1, 3, 0, 0, 4,// 5, 4, 3, 9, 0, 0, 1, 0, 0,// 3, 9, 0, 0, 0, 0, 6, 0, 0,// 0, 7, 8, 6, 0, 5, 9, 2, 0,// 0, 0, 6, 0, 0, 0, 0, 3, 7,// 0, 0, 1, 0, 0, 9, 7, 8, 2,// 7, 0, 0, 3, 6, 2, 0, 0, 0,// 9, 0, 5, 0, 0, 1, 0, 0, 0}; bool bret = Solve(au8Sudoku); printf("%s\n", bret? "Ok":"NO"); print_Sudoku(au8Sudoku);} 运行结果如下：
速度也比我想象的快多了，毕竟是电脑哪。当然，假如数独有多个解，上面的算法也就只能得到一个解。