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 往下走 ....











arrow
arrow
    全站熱搜

    hedgezzz 發表在 痞客邦 留言(0) 人氣()