魔法使いの弟子（その10-1） ～計算機に思考させる

【ミッション： ナンプレ自動解答システムを作ろう】

新生活の季節である。

思い起こせば5年前。ぼくは生活水準の変化に戸惑い、ホームシックに涙し、前途多難な新生活に肩を落としていた。

これは当時、過酷な新生活をリッチかつゴージャスに過ごすべく果敢に挑戦したぼくの記録である。

※ 当時は C の経験が浅く、Excel VBA で作った。今回の話を書くにあたり、改めて C 言語に書きなおした次第である。

---

ぼくは、実家暮らしだった頃、パズルを解いて懸賞に応募する雑誌を不定期購読していた。

もしもプログラムでパズルを自動的に解く事ができれば、ラクして幸せになれるんじゃないか。高額景品でウハウハになるのではないか。なんだこの完璧すぎる計画は。

そこでぼくは、数あるパズルの中でも比較的攻略が容易なナンバープレイスに目をつけた。

ルールをざっくり解説すると、

• 9×9のフィールドの中で、空欄になっているセルに1～9の数字を入れる
• ただし、各行・各列に同じ数字が重複して入ってはならない
• 太線で区切られた3×3のブロックに同じ数字が重複して入ってはならない

というものだ。

ヒント（元から入っている数字）の多さによって難易度が変わり、特に難しい問題では2万円相当の景品がもらえる場合もある。

というわけで、ナンバープレイスを力ずくで自動解答するプログラムをささっと作ってみよう。

---

【必要なデータ構造】

ナンバープレイスの9×9の盤面は、実装の都合上、1次元配列で表す事にした（こうすると余計な if 文が減るのだ）。2次元配列と1次元配列で、要素へのアクセスは以下のように対応する。

view plainprint?

1. field[i][j] ←→ field[i*9 + j]  

field[i][j] ←→ field[i*9 + j]

確定したマスには、それぞれ 1 ～ 9 の整数値が格納される。未確定のマスには 0 が入る。

まずは、定数マクロおよびグローバル変数を以下のように定義した。

view plainprint?

1. #include<stdio.h>  
2.   
3. #define FIELD_SIZE 9    // フィールド（9x9）  
4. #define BLOCK_SIZE 3    // ブロック（3x3）  
5.   
6. #define TRUE  1  
7. #define FALSE 0  
8.   
9. // フィールドはグローバル変数で管理  
10. char field[FIELD_SIZE * FIELD_SIZE];  

#include<stdio.h>

#define FIELD_SIZE 9    // フィールド（9x9）
#define BLOCK_SIZE 3    // ブロック（3x3）

#define TRUE  1
#define FALSE 0

// フィールドはグローバル変数で管理
char field[FIELD_SIZE * FIELD_SIZE];

さらに、フィールドの中身を出力する便利な関数 printField も作っておこう。

view plainprint?

1. // フィールドの状態を出力する関数  
2. void printField() {  
3.     for(int i = 0; i < FIELD_SIZE; ++i) {  
4.         for(int j = 0; j < FIELD_SIZE; ++j) {  
5.             if(field[i*FIELD_SIZE + j] == 0)  
6.                 printf("   ");  
7.             else printf("%d  ", field[i*FIELD_SIZE + j]);  
8.         }  
9.         printf("\n");  
10.     }  
11.     printf("\n\n");  
12. }  

// フィールドの状態を出力する関数
void printField() {
    for(int i = 0; i < FIELD_SIZE; ++i) {
        for(int j = 0; j < FIELD_SIZE; ++j) {
            if(field[i*FIELD_SIZE + j] == 0)
                printf("   ");
            else printf("%d  ", field[i*FIELD_SIZE + j]);
        }
        printf("\n");
    }
    printf("\n\n");
}

---

【アルゴリズム】

ナンバープレイスのルールとして、『各行・各列および、3×3のブロック内に同じ数字を入れてはいけない』とある。

今回は、セル一つひとつに順番に数字を代入していき、この条件を満たすか否かを逐次チェックするという原始的なアルゴリズムを採用した。

しかし、すべてのマスに対して数字の候補を代入する処理は、for 文で素直に実装すると81重ループになってしまう。

そこで、すっきり書くために再帰計算を行う事にした。

view plainprint?

1. // 数独を解き、答えを出力する関数。  
2. // 引数：  
3. //      int loc ... フィールドの対象セル  
4. //                  （最初は0を渡す）  
5. void solve(int loc) {  
6.   
7.     // 答えが見つかった場合はそれを出力  
8.     if (loc == FIELD_SIZE * FIELD_SIZE)  
9.         return printField();  
10.   
11.     // もともと数字が入っている場合は飛ばして次へ  
12.     if (field[loc] != 0) return solve(loc+1);  
13.       
14.     // 空欄の場合は力ずくでサーチ  
15.     for(int i = 1; i < FIELD_SIZE + 1; ++i) {  
16.         // 入れようとしている数字に重複がなければ…  
17.         if(checkAnswer(loc, i)) {  
18.             field[loc] = i; // その数字を解と仮定して  
19.             solve(loc+1);   // 次へ進む  
20.             field[loc] = 0; // ダメなら空欄に戻す  
21.         }  
22.     }  
23. }  

// 数独を解き、答えを出力する関数。
// 引数：
//      int loc ... フィールドの対象セル
//                  （最初は0を渡す）
void solve(int loc) {

    // 答えが見つかった場合はそれを出力
    if (loc == FIELD_SIZE * FIELD_SIZE)
        return printField();

    // もともと数字が入っている場合は飛ばして次へ
    if (field[loc] != 0) return solve(loc+1);
    
    // 空欄の場合は力ずくでサーチ
    for(int i = 1; i < FIELD_SIZE + 1; ++i) {
        // 入れようとしている数字に重複がなければ…
        if(checkAnswer(loc, i)) {
            field[loc] = i; // その数字を解と仮定して
            solve(loc+1);   // 次へ進む
            field[loc] = 0; // ダメなら空欄に戻す
        }
    }
}

ただし、処理の途中でちゃんとルールに従っているかどうか、すなわち、これから代入しようとしている解候補が各行・各列、そして3×3のブロックに既に入っていないかどうかをチェックする必要がある。

ソースコード中の checkAnswer 関数（後述）がその役割を担っている。

---

【妥当性のチェック】

checkAnswer 関数は、対象セルのインデックス loc 、及び、代入しようとしている数 num を与えて、そのセルが属する行・列・ブロック内で既に同じ数字が存在するかどうかを判定する。

view plainprint?

1. // 暫定的な答えチェック関数。  
2. // 引数：  
3. //      int loc ... フィールドの対象セル  
4. //      int num ... 代入候補の数値  
5. // 戻り値：  
6. //      TRUE  ... 妥当な場合  
7. //      FALSE ... 妥当ではない場合  
8. int checkAnswer(int loc, int num) {  
9.     int row = loc / FIELD_SIZE;  
10.     int col = loc % FIELD_SIZE;  
11.   
12.     int index;      
13.     // 行と列のチェック  
14.     for(int i = 0; i < FIELD_SIZE; ++i) {  
15.         // 行のチェック  
16.         index = row * FIELD_SIZE + i;  
17.         // 同じ数字が見つかったらエラー  
18.         if(field[index] == num)  
19.             return FALSE;  
20.   
21.         // 列のチェック  
22.         index = i * FIELD_SIZE + col;  
23.         // 同じ数字が見つかったらエラー  
24.         if(field[index] == num)  
25.             return FALSE;  
26.     }  
27.       
28.     // ブロックのチェック  
29.     int blockRow = row / BLOCK_SIZE * BLOCK_SIZE;  
30.     int blockCol = col / BLOCK_SIZE * BLOCK_SIZE;  
31.     for(int i = blockRow; i < blockRow + BLOCK_SIZE; ++i) {  
32.         for(int j = blockCol; j < blockCol + BLOCK_SIZE; ++j) {  
33.             index = i * FIELD_SIZE + j;  
34.             if(field[index] == num)  
35.                 return FALSE;  
36.         }  
37.     }  
38.   
39.     return TRUE;  
40. }  

// 暫定的な答えチェック関数。
// 引数：
//      int loc ... フィールドの対象セル
//      int num ... 代入候補の数値
// 戻り値：
//      TRUE  ... 妥当な場合
//      FALSE ... 妥当ではない場合
int checkAnswer(int loc, int num) {
    int row = loc / FIELD_SIZE;
    int col = loc % FIELD_SIZE;

    int index;    
    // 行と列のチェック
    for(int i = 0; i < FIELD_SIZE; ++i) {
        // 行のチェック
        index = row * FIELD_SIZE + i;
        // 同じ数字が見つかったらエラー
        if(field[index] == num)
            return FALSE;

        // 列のチェック
        index = i * FIELD_SIZE + col;
        // 同じ数字が見つかったらエラー
        if(field[index] == num)
            return FALSE;
    }
    
    // ブロックのチェック
    int blockRow = row / BLOCK_SIZE * BLOCK_SIZE;
    int blockCol = col / BLOCK_SIZE * BLOCK_SIZE;
    for(int i = blockRow; i < blockRow + BLOCK_SIZE; ++i) {
        for(int j = blockCol; j < blockCol + BLOCK_SIZE; ++j) {
            index = i * FIELD_SIZE + j;
            if(field[index] == num)
                return FALSE;
        }
    }

    return TRUE;
}

---

【テスト】

ここまでで解答プログラムができたので、配列 field に適当なテストデータをセットして、プログラムに解かせてみた。

main 関数は（だいぶ端折ったが）こんな感じである。

view plainprint?

1. int main() {  
2.   
3.     // フィールド初期化  
4.     for(int i = 0; i < FIELD_SIZE * FIELD_SIZE; ++i)  
5.         field[i] = 0;  
6.   
7.   
8.     /* ここで問題を設定してね♪ */  
9.   
10.   
11.     // 問題出力  
12.     printf("【Question】\n");  
13.     printField();  
14.       
15.     // 解く。  
16.     printf("【Answer】\n");  
17.     solve(0);  
18.     return 0;  
19. }  

int main() {

    // フィールド初期化
    for(int i = 0; i < FIELD_SIZE * FIELD_SIZE; ++i)
        field[i] = 0;


    /* ここで問題を設定してね♪ */


    // 問題出力
    printf("【Question】\n");
    printField();
    
    // 解く。
    printf("【Answer】\n");
    solve(0);
    return 0;
}

とりあえずはWikipedia の『数独』のページに載っていた画像の問題で試してみた。

瞬殺である。真面目に解くのが馬鹿馬鹿しいくらいあっけなく終わる。

あ、ちなみに、意地悪して『すべてのセルが空欄』の状態で解かせたら、重解が多すぎてコマンドプロンプトが流星群のごとく流れ続けて止まらなくなった。

---

これでロジックの方は（一応）できたので、あとは問題の入力を容易にするためのインタフェースを適当に作ればよい。

でも今日はねむいからもうやめる。飽きたし。