Sudoku (數獨)

Requirements

  1. Sudoku 是一個 1986 起盛行於日本的遊戲。 在一個九乘九的棋盤中，有些格子是空的，其他則已填有1到9的數字（如下圖所示）。
    [sudoku]
  2. 遊戲的要求是將空的格子用1到9的數字填滿，使得每一行、每一例，以及每三行三列形成的九個三乘三小棋盤中，1到9的數都正好出現一次。
  3. 輸入時，用0代表空白的格子。例如上面那個棋盤，會輸入為 
    
0 3 0 2 7 0 4 6 1
4 5 0 0 0 0 7 0 0
2 0 0 0 0 0 0 8 0
0 0 0 0 5 6 2 1 0
0 0 8 9 0 2 5 0 0
0 2 5 7 1 0 0 0 0
0 1 0 0 0 0 0 0 4
0 0 7 0 0 0 0 5 6
6 8 2 0 9 4 0 3 0
  4. 符合要求的可能不只一組解。輸出時，只需要印出一組解即可。 
    
8 3 9 2 7 5 4 6 1
4 5 6 8 3 1 7 9 2
2 7 1 4 6 9 3 8 5
7 9 4 3 5 6 2 1 8
1 6 8 9 4 2 5 7 3
3 2 5 7 1 8 6 4 9
5 1 3 6 8 7 9 2 4
9 4 7 1 2 3 8 5 6
6 8 2 5 9 4 1 3 7

Design

  1. 最簡單的方法是「暴力窮舉法」(brute force)。每一格都從1到9試試看。
  2. 可是程式中要寫81個 for-loop 實在太辛苦了。所以我們使用「遞迴」(recursive)的寫法，程式可以簡潔一些。
  3. 我們設計一個遞迴的 void try_number(int n, int sudoku[9][9]) 函式。把整個棋盤用一個九乘九的陣列 sudoku[9][9] 傳入，n則代表目前要試第幾格 (n = 0..80 共81格)。
  4. 如果遞迴跑了81次，代表棋盤中已成功填有81個數字，且皆合乎規則，就可以呼叫 show_sudoku()印出。
  5. 根據 n, 可以換算成是第幾列第幾行。row = n / 9; col = n % 9。
  6. 如果 sudoku[row][col] 已填有數字，則遞迴呼叫 try_number(n+1, sudoku); 處理下一格。
  7. 相反地，如果 sudoku[row][col] 為0 （未填有數字）
    1. 用個迴圈，在這格逐一試著填1至9的數字。假設我們把目前試著要填入的數字叫 t 。
    2. 如果 t 已出現在目前這個 row 中， 或是 t 已出現在目前這個 column 中， 或是 t 已出現在目前 3x3 的小棋盤中，就換下一個 t.
    3. 如果 t 尚未「撞到」已出現的數字，就令 sudoku[row][col] = t， 並遞迴呼叫 try_number(n+1, sudoku);
    4. 當迴圈跑完後如果沒一個 t 是適合的，代表這一步失敗。 將 sudoku[row][col] 清成 0 以恢復原狀，return 回上一步。
  8. 要判斷 t 是否已出現，可定義 appear_on_row(t, row, sudoku), appear_on_column(), appear_in_block() 這三個布林函式來協助判斷。
  9. try_number() 函式的流程圖如下（請助教幫忙美化一下）：
    [Flowchart]
  10. 有了這個遞迴函式，主程式就很簡單： 
    
int main(void)
{
    int i, j;
    int sudoku[9][9];
    for (i=0; i<9; i++)
        for (j=0; j<9; j++)
            cin >> sudoku[i][j];
    try_number(0, sudoku);
    return 0;
}