最近，新加坡总理李显龙也写了一份代码公布出来，大致瞧了一眼，竟然是解数独题的代码！前几天刚刚写过，数独主要算法当然是使用回溯法。回溯法当时初学的时候在思路上比较拧，不容易写对。写了几个回溯法的算法之后心里总算有了点底。回溯法的代码一般都是长成下面这样子：
void backtracking(int[] arr, int boundary, int current, int[] result)
{
if(current>=boundary) //到达终止条件
{
//判断result是否符合要求
//如果符合，记录结果,即result数组的值 return;
} for(int i=0; i<arr.length;i++)
{
STEP 1： //从arr中取出第i个元素
STEP 2： //用第i个元素加入到result中
STEP 3： backtracking(arr, boundary, current+1, result); //进入下一步探索
STEP 4： //把第i个元素从result中拿出来
STEP 5： //把第i个元素再放回arr中去
}
}
回溯法代码特点非常鲜明，一上来先判断递归的终止条件，到达终止条件，就检查结果是否合格，合格就记录下来。而回溯法的精髓就在下面的for循环中，一共有5个步骤，后两个步骤刚好是前两个步骤的反操作，因此才被成为‘回溯’。我们可以认为，回溯法就是暴力（brute force）搜索的一种优化方式。
扯了点闲话，来看Sudoku Solver题：
/*************************Question**************************
* Write a program to solve a Sudoku puzzle by filling the empty cells.
* Empty cells are indicated by the character '.'.
* You may assume that there will be only one unique solution.
*
* 5 3 . . 7 . . . .
* 6 . . 1 9 5 . . .
* . 9 8 . . . . 6 .
* 8 . . . 6 . . . 3
* 4 . . 8 . 3 . . 1
* 7 . . . 2 . . . 6
* . 6 . . . . 2 8 .
* . . . 4 1 9 . . 5
* . . . . 8 . . 7 9
* A sudoku puzzle...
* 5 3 4 6 7 8 9 1 2
* 6 7 2 1 9 5 3 4 8
* 1 9 8 3 4 2 5 6 7
* 8 5 9 7 6 1 4 2 3
* 4 2 6 8 5 3 7 9 1
* 7 1 3 9 2 4 8 5 6
* 9 6 1 5 3 7 2 8 4
* 2 8 7 4 1 9 6 3 5
* 3 4 5 2 8 6 1 7 9
*
* ...and its solution.
***********************************************************/
我的代码如下：
bool isValid(char *board[], int row, int column, char number){
for(int i = ; i < ; i++){
if(board[row][i] == number){
return false;
}
if(board[i][column] == number){
return false;
}
}
for (int i = ; i < ; i++){
int a = (row / ) * + i / ;
int b = (column / ) * + i % ;
if(board[a][b] == number){
return false;
}
}
return true;
}
bool sudokuSolution(char *board[], int row, int column){
if(row >= ){
return true;
}
if(board[row][column] != '.'){
if(column >= ){
return sudukuSolution(board, row+, );
}else {
return sudukuSolution(board, row, column+);
}
}
for(int i=; i<;i++){
if(isValid(board, row, column, (char)(''+i))){
board[row][column] = (char)(''+i);
if(column >= && sudukuSolution(board, row+, )){
return true;
}else if (sudukuSolution(board, row, column +)){
return true;
}
board[row][column] = '.';
}
}
return false;
}
void solveSudoku(char *board[]){
if(sudokuSolution(board, , )){
//successfully find the solution
} else {
// cannot find a solution
}
return;
}
代码使用C语言编写，其中bool sudokuSolution函数就很明显有回溯法的函数结构。