Sudoku Solver

来源：Leetcode

原帖：http://oj.leetcode.com/problems/sudoku-solver/

题目：
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.
Solution: back-tracking... Recursion.
Note: Backtracking...
http://blog.csdn.net/linhuanmars/article/details/20748761
这道题的方法就是用在N-Queens中介绍的常见套路。简单地说思路就是循环处理子问题，对于每个格子，带入不同的9个数，然后判合法，如果成立就递归继续，结束后把数字设回空

代码：

 class Solution {  
 public:  
   typedef vector<vector<char>> BOARDTYPE;  
   const int N = 9;  
   
   void getNextEmpty(BOARDTYPE &board, int &row, int &col) {  
     do {  
       if (board[row][col] == '.') return;  
       row = (col == N - 1) ? row + 1 : row;  
       col = (col + 1) % N;  
     } while (row < N);  
   }  
     
   void getAvailable(BOARDTYPE &board, vector<bool> &avail, int row, int col) {  
     for (int i = 0; i < 9; ++i) {  
       if (board[row][i] != '.') {  
         avail[board[row][i] - '1'] = false;  
       }  
       if (board[i][col] != '.') {  
         avail[board[i][col] - '1'] = false;  
       }  
       int box_i = row/3*3 + i/3;  
       int box_j = col/3*3 + i%3;  
       if (board[box_i][box_j] != '.') {  
         avail[board[box_i][box_j] - '1'] = false;  
       }  
     }  
   }  
   
   bool solveSudokuHelper(BOARDTYPE &board, int row, int col) {  
     getNextEmpty(board, row, col); // get next empty position [row, col]  
     if (row == 9) return true;  
     vector<bool> avail(9, true);  
     getAvailable(board, avail, row, col); // available value at(row, col) in row/col/box check   
     for (int i = 0; i < 9; ++i) {  
       if (!avail[i]) continue;  
       board[row][col] = i + '1';  
       if (solveSudokuHelper(board, row, col)) return true;  
       board[row][col] = '.';  
     }  
     return false;  
   }  
     
   void solveSudoku(BOARDTYPE &board) {  
     solveSudokuHelper(board, 0, 0);  
   }  
 };