Sudoku Solver Backtracking

このブログはよく分析します
 
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.
遡及法の思想!!(枝切り＋遡及＋再帰運用)
分析:
まず九宮格全体を巡り、マーク!
rowValid[row][val]は1に等しい:row行valは既に存在する(定義ドメイン、rowは0~8、valは1~9)
colValid[col][val]は1に等しい:col列valはすでに存在する
subGrid[row/3*3+col/3][val]は1に等しい:第w/3*3+col/3子九宮格にはvalがすでに存在する
indexを利用してアルゴリズム検索制御を行います!数独には81の数字があり、0~80です.従ってindex>80の場合、アルゴリズムは解があり、終了する.
 

 1 class Solution {
 2 public:
 3     void solveSudoku(vector<vector<char>>& board)
 4     {
 5         for(int i=0;i<9;i++)
 6         for(int j=0;j<9;j++)
 7         {
 8             if(board[i][j]!='.')
 9                 handle(i,j,board[i][j]-'0');
10         }
11         solve(board,0);
12     }
13     
14     bool solve(vector<vector<char>>& board,int index)
15     {
16         if(index>80)
17             return true;
18         int row=index/9;
19         int col=index-index/9*9;
20         if(board[row][col]!='.')
21             return solve(board,index+1);
22         for(int num='1';num<='9';num++)//int num='1';num<'10';num++, ，'10' ？  // 9 
23         {
24             if(isValid(row,col,num-'0'))
25             {
26                 board[row][col]=num;
27                 handle(row,col,num-'0');
28                 if(solve(board,index+1)) return true;
29                 reset(row,col,num-'0');
30             }
31         }
32         board[row][col]='.';
33         return false;
34     }
35     bool isValid(int row,int col,int val)
36     {
37         if(rowValid[row][val]==0 && colValid[col][val]==0 && subGrid[row/3*3+col/3][val]==0)
38             return true;
39         return false;
40     }
41     void handle(int row,int col,int val)
42     {
43         rowValid[row][val]=1;
44         colValid[col][val]=1;
45         subGrid[row/3*3+col/3][val]=1;
46     }
47     void reset(int row,int col,int val)
48     {
49         rowValid[row][val]=0;
50         colValid[col][val]=0;
51         subGrid[row/3*3+col/3][val]=0;
52     }
53     
54 private:
55     int rowValid[9][10];
56     int colValid[9][10];
57     int subGrid[9][10];
58 };