http://codepad.org/GCTKUKRr
bool SolveSudoku(int grid[N][N]) { int row, col; // If there is no unassigned location, we are done if (!FindUnassignedLocation(grid, row, col)) return true; // success! // consider digits 1 to 9 for (int num = 1; num <= N; num++) { // if looks promising if (isSafe(grid, row, col, num)) { // make tentative assignment grid[row][col] = num; // return, if success, yay! if (SolveSudoku(grid)) return true; // failure, unmake & try again grid[row][col] = UNASSIGNED; } } return false; // this triggers backtracking }
1. FindUnassignedLocation 參數 row,col 是 reference , 主要是找尚未填值的欄位,
如果找到 return true , 並且將 row/col 填好 , 如果全部欄位都填了,return false ,
那就是數獨已經完成 .
2. isSafe 是判斷 num 填到 [row,col] 會不會違反數獨規則? 如果違反則 return false ,
那麼這個 num 不行 , 就再填下個 num , 從 1 試到 9 ....
3. 當這個值是 safe 時 , 就將 num 填入 grid[row][col] , 然後再呼叫 SolveSudoku ,
這個再次被呼叫的 SolveSudoku 會找到下一個沒被填值的欄位,就這樣遞迴下去 ,
如果下一個沒被填值的欄位,從 1 到 9 都不 safe , 會 return false , 那麼 我這一圈的
if (SolveSudoku(grid)) return true; 就不做 return true . 而是執行
grid[row][col] = UNASSIGNED; 再 把 num+1 往下走 ....
全站熱搜
留言列表