トップページ Maxima とは リンク集 関数と変数 ちっぷす imaxima 数独
ナンバープレース（数独）

Maxima を使って、数独表(*1を発生させる関数を定義してみました。ファイル sudoku.mac を適当なフォルダ(*2に置いて、以下のように実行します。 

(%i1) load("sudoku.mac");
(%o1)                             sudoku.mac

(%i2) sudoku();
                         [ 9  2  1  5  3  7  6  8  4 ]
                         [                           ]
                         [ 4  3  7  8  2  6  1  5  9 ]
                         [                           ]
                         [ 6  8  5  4  9  1  3  2  7 ]
                         [                           ]
                         [ 2  1  8  7  6  9  4  3  5 ]
                         [                           ]
(%o2)                    [ 3  9  4  2  8  5  7  6  1 ]
                         [                           ]
                         [ 7  5  6  1  4  3  2  9  8 ]
                         [                           ]
                         [ 5  4  9  3  7  2  8  1  6 ]
                         [                           ]
                         [ 8  6  3  9  1  4  5  7  2 ]
                         [                           ]
                         [ 1  7  2  6  5  8  9  4  3 ]
生成できなかった場合は -1 を返します。5 割くらいの確率で失敗します（＾＾；。

*1）　数独ルールにのっとって 81 個の数字を並べた表のことを数独表と呼ぶことにします。
*2）　Windows の場合は C:\Documents and Settings\User Name に置きます。

sudoku.mac 概説

数独のルールは、

というものでした。

9 2 1 5 3 7 6 8 4
4 3 7 8 2 6 1 5 9
6 8 5 4 9 1 3 2 7
2 1 8 7 6 9 4 3 5
3 9 4 2 8 5 7 6 1
7 5 6 1 4 3 2 9 8
5 4 9 3 7 2 8 1 6
8 6 3 9 1 4 5 7 2
1 7 2 6 5 8 9 4 3

【数独表生成法】

sudoku.mac で用いている数独表生成法を簡単に述べると、次のようになります。

この操作を STEP9-9 まで実行します。この方法はたびたび破綻します。そこで、STEPi-j で破綻した場合、STEPi-1 まで遡って処理を繰り返し、100 回破綻した場合には -1 を返すようにしています。

【ブロックインデックスとラインインデックス】

上記の手順を実装する場合、各数字が「第何行目の第何列目か」と「第何ブロックの何番目か」を常に把握する必要があります。そこで、前者をラインインデックス（マトリックスインデックス）、後者をブロックインデックスと呼ぶことにし、

ラインインデックス ブロックインデックス
[1,1] [1,2] [1,3] [1,4] [1,5] [1,6] [1,7] [1,8] [1,9]
[2,1] [2,2] [2,3] [2,4] [2,5] [2,6] [2,7] [2,8] [2,9]
[3,1] [3,2] [3,3] [3,4] [3,5] [3,6] [3,7] [3,8] [3,9]
[4,1] [4,2] [4,3] [4,4] [4,5] [4,6] [4,7] [4,8] [4,9]
[5,1] [5,2] [5,3] [5,4] [5,5] [5,6] [5,7] [5,8] [5,9]
[6,1] [6,2] [6,3] [6,4] [6,5] [6,6] [6,7] [6,8] [6,9]
[7,1] [7,2] [7,3] [7,4] [7,5] [7,6] [7,7] [7,8] [7,9]
[8,1] [8,2] [8,3] [8,4] [8,5] [8,6] [8,7] [8,8] [8,9]
[9,1] [9,2] [9,3] [9,4] [9,5] [9,6] [9,7] [9,8] [9,9]
[1,1] [1,2] [1,3] [2,1] [2,2] [2,3] [3,1] [3,2] [3,3]
[1,4] [1,5] [1,6] [2,4] [2,5] [2,6] [3,4] [3,5] [3,6]
[1,7] [1,8] [1,9] [2,7] [2,8] [2,9] [3,7] [3,8] [3,9]
[4,1] [4,2] [4,3] [5,1] [5,2] [5,3] [6,1] [6,2] [6,3]
[4,4] [4,5] [4,6] [5,4] [5,5] [5,6] [6,4] [6,5] [6,6]
[4,7] [4,8] [4,9] [5,7] [5,8] [5,9] [6,7] [6,8] [6,9]
[7,1] [7,2] [7,3] [8,1] [8,2] [8,3] [9,1] [9,2] [9,3]
[7,4] [7,5] [7,6] [8,4] [8,5] [8,6] [9,4] [9,5] [9,6]
[7,7] [7,8] [7,9] [8,7] [8,8] [8,9] [9,7] [9,8] [9,9]

これらの間の相互変換関数 LtoB(x, y)、BtoL(x, y) を作成します。ラインインデックスの [i,j] を L[i,j]、ブロックインデックスの [i,j] を B[i,j] と書くことにします（プログラムの中では 2 次元リスト L[i][j]、B[i][j] にしています）。

【関数 LtoB(x, y)】

関数 LtoB(x, y) を作成するため、便宜上、ラインインデックスの各インデックスに一律に 2 を加えて考えます。例えば、L[7,6] は B[8,3] に対応しますが、2 を加えて考えるので、L+[9, 8] = B[8, 3] となります（2 を加えたインデックスを + 記号をつけて表しています）。まずはじめに、L+[9, 8] に対応するブロック数 8 を求めてみます。3 による割り算

9 ÷ 3 ＝ 3 … 0　および　8 ÷ 3 ＝ 2 … 2

の商に注目し、(3-1) × 3 ＋ 2 ＝ 8 により求まります。要するに、自分自身が属しているのは、上から何ブロック目か、そして、左から何ブロック目かを求めればよいわけです。

ラインインデックス+
[3,3] [3,4] [3,5] [3,6] [3,7] [3,8] [3,9] [3,10] [3,11]
[4,3] [4,4] [4,5] [4,6] [4,7] [4,8] [4,9] [4,10] [4,11]
[5,3] [5,4] [5,5] [5,6] [5,7] [5,8] [5,9] [5,10] [5,11]
[6,3] [6,4] [6,5] [6,6] [6,7] [6,8] [6,9] [6,10] [6,11]
[7,3] [7,4] [7,5] [7,6] [7,7] [7,8] [7,9] [7,10] [7,11]
[8,3] [8,4] [8,5] [8,6] [8,7] [8,8] [8,9] [8,10] [8,11]
[9,3] [9,4] [9,5] [9,6] [9,7] [9,8] [9,9] [9,10] [9,11]
[10,3] [10,4] [10,5] [10,6] [10,7] [10,8] [10,9] [10,10] [10,11]
[11,3] [11,4] [11,5] [11,6] [11,7] [11,8] [11,9] [11,10] [11,11]

次に、ブロック内番号 3 を求めてみます。今度は、3 による割り算

9 ÷ 3 ＝ 3 … 0　および　8 ÷ 3 ＝ 2 … 2

の余りに注目し、0 × 3 ＋ (2 ＋ 1) ＝ 3 により求まります。

【関数 BtoL(x, y)】

関数 LtoB(x, y) の場合と同様、便宜上、ブロックデックスの各インデックスに一律に 2 を加えて考えます。

ブロックインデックス+
[3,3] [3,4] [3,5] [4,3] [4,4] [4,5] [5,3] [5,4] [5,5]
[3,6] [3,7] [3,8] [4,6] [4,7] [4,8] [5,6] [5,7] [5,8]
[3,9] [3,10] [3,11] [4,9] [4,10] [4,11] [5,9] [5,10] [5,11]
[6,3] [6,4] [6,5] [7,3] [7,4] [7,5] [8,3] [8,4] [8,5]
[6,6] [6,7] [6,8] [7,6] [7,7] [7,8] [8,6] [8,7] [8,8]
[6,9] [6,10] [6,911] [7,9] [7,8] [7,11] [8,9] [8,10] [8,11]
[9,3] [9,4] [9,5] [10,3] [10,4] [10,5] [11,3] [11,4] [11,5]
[9,6] [9,7] [9,8] [10,6] [10,7] [10,8] [11,6] [11,7] [11,8]
[9,9] [9,10] [9,11] [10,9] [10,10] [10,11] [11,9] [11,10] [11,11]

B+[11,10] に対応する L[9,8] を求めてみましょう。行番号 9 を求めるためには、ブロック番号 11 とブロック内番号 10 の 3 による割り算

11 ÷ 3 ＝ 3 … 2　および　10 ÷ 3 ＝ 3 … 1

の商に注目し、(3-1) × 3 ＋ 3 ＝ 9 により求まります。また、列番号 8 を求めるには、3 による割り算

11 ÷ 3 ＝ 3 … 2　および　10 ÷ 3 ＝ 3 … 1

の余りに注目し、2 × 3 ＋ (1 ＋ 1) ＝ 8 により求まります。すなわち、LtoB(x, y) と BtoL(x, y) はまったく同じ計算により定義できます。

【関数 BtoL(x, y)=LtoB(x, y) 動作確認】

sudoku.mac では関数 Btol(x, y)=LtoB(x, y) は関数名 f(x, y) で定義されています。 

1
2
3
4
5
 
f(x, y) := block([dx, dy],
        dx: divide(x + 2, 3),
        dy: divide(y + 2, 3),
        [dx[1] * 3 + dy[1] - 3, dx[2] * 3 + dy[2] + 1]
);
正しく定義できているか、確認しておきます。入力済みのファイル sudoku_pre.mac を読み込んで実験してみましょう。 
(%i1) load("sudoku_pre.mac");

(%o1)                           sudoku_pre.mac


(%i2) lambda([i, j], j+9*(i-1));

(%o2)                    lambda([i, j], j + 9 (i - 1))


(%i3) A: genmatrix(%, 9, 9, 1, 1);

                    [ 1   2   3   4   5   6   7   8   9  ]
                    [                                    ]
                    [ 10  11  12  13  14  15  16  17  18 ]
                    [                                    ]
                    [ 19  20  21  22  23  24  25  26  27 ]
                    [                                    ]
                    [ 28  29  30  31  32  33  34  35  36 ]
                    [                                    ]
(%o3)               [ 37  38  39  40  41  42  43  44  45 ]
                    [                                    ]
                    [ 46  47  48  49  50  51  52  53  54 ]
                    [                                    ]
                    [ 55  56  57  58  59  60  61  62  63 ]
                    [                                    ]
                    [ 64  65  66  67  68  69  70  71  72 ]
                    [                                    ]
                    [ 73  74  75  76  77  78  79  80  81 ]


(%i4) B: zeromatrix(9, 9)$


(%i5) for i: 1 thru 9 do for j: 1 thru 9 do
B[i][j]: A[f(i, j)[1]][f(i, j)[2]];

(%o5)                                done


(%i6) display(B);

                      [ 1   2   3   10  11  12  19  20  21 ]
                      [                                    ]
                      [ 4   5   6   13  14  15  22  23  24 ]
                      [                                    ]
                      [ 7   8   9   16  17  18  25  26  27 ]
                      [                                    ]
                      [ 28  29  30  37  38  39  46  47  48 ]
                      [                                    ]
                  B = [ 31  32  33  40  41  42  49  50  51 ]
                      [                                    ]
                      [ 34  35  36  43  44  45  52  53  54 ]
                      [                                    ]
                      [ 55  56  57  64  65  66  73  74  75 ]
                      [                                    ]
                      [ 58  59  60  67  68  69  76  77  78 ]
                      [                                    ]
                      [ 61  62  63  70  71  72  79  80  81 ]

(%o6)                                done


(%i7) C: zeromatrix(9, 9)$


(%i8) for i: 1 thru 9 do for j: 1 thru 9 do
C[i][j]: B[f(i, j)[1]][f(i, j)[2]];

(%o8)                                done


(%i9) display(C);

                      [ 1   2   3   4   5   6   7   8   9  ]
                      [                                    ]
                      [ 10  11  12  13  14  15  16  17  18 ]
                      [                                    ]
                      [ 19  20  21  22  23  24  25  26  27 ]
                      [                                    ]
                      [ 28  29  30  31  32  33  34  35  36 ]
                      [                                    ]
                  C = [ 37  38  39  40  41  42  43  44  45 ]
                      [                                    ]
                      [ 46  47  48  49  50  51  52  53  54 ]
                      [                                    ]
                      [ 55  56  57  58  59  60  61  62  63 ]
                      [                                    ]
                      [ 64  65  66  67  68  69  70  71  72 ]
                      [                                    ]
                      [ 73  74  75  76  77  78  79  80  81 ]
(%o9)                                done
まず、単純に 1 から 81 までの数字を並べた行列 A を作成します。これを、先の関数 f(x, y) を利用し、ブロック型に並べ替えた行列が B です。再び関数 f(x, y) を利用し、行列 B をライン型に並べ替えたものが行列 C です。行列 A と C が一致していることから関数 f が正しく定義できていることがわかります。

【出来ることからコツコツと】

準備が整ったところで、いよいよ数独表生成関数を作成していきましょう。まずは手始めに、単純に各行に 1 を入れていくだけの関数 sudoku_pre1() を定義してみます。 

1
2
3
4
5
6
7
8
9
 
sudoku_pre1() := ([a,
        M: zeromatrix(9, 9)
        ],
        for i: 1 thru 9 do (
                a: random(9) + 1,
                M[i][a]: 1
        ),
        M
);
あまりに単純すぎて解説の余地はありませんが、まず、0 で埋め尽くした行列 M を用意しておき（2 行目）、第 1 行 M[1]、第 2 行 M[2]、..... に順に 1 を入れていきます（6 行目）。この関数の実行例は、下記の通りです。 
(%i10) sudoku_pre1();

                         [ 0  0  1  0  0  0  0  0  0 ]
                         [                           ]
                         [ 0  0  0  0  0  0  1  0  0 ]
                         [                           ]
                         [ 0  0  1  0  0  0  0  0  0 ]
                         [                           ]
                         [ 0  0  0  0  0  1  0  0  0 ]
                         [                           ]
(%o10)                   [ 0  1  0  0  0  0  0  0  0 ]
                         [                           ]
                         [ 0  1  0  0  0  0  0  0  0 ]
                         [                           ]
                         [ 0  0  0  0  0  1  0  0  0 ]
                         [                           ]
                         [ 0  0  0  0  0  0  0  0  1 ]
                         [                           ]
                         [ 0  0  0  0  0  0  1  0  0 ]
当然ながら、同じブロックや同じ列に複数の 1 が入ってしまっています。そこで、次のステップとして、同じ列に 1 が入るのを避けてみましょう。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
sudoku_pre2() := ([a, p,
    M: zeromatrix(9, 9),
    K: zeromatrix(9, 9)
    ],
    for i: 1 thru 9 do (
        p: 0,
        for j: 1 while (p = 0) do (
            a: random(9) + 1,
            if K[i][a] = 0 then (
                p: 1,
                for k: i thru 9 do K[k][a]: 1,
                M[i][a]: 1
            )
        )
    ),
    M
);
1 を「入れていい場所」と「入れてはいけない場所」を記録する変数（行列）K（3 行目）を用意するところがポイントです。7 行目の j はダミー変数で、変数 p が 0 でなくなるまでループを実行し続けます。ここで、変数 p は、「1 を入れていい列」が見つかった場合に 1 が代入される変数です。その判断をしているのが 9 行目の if 文です。「1 を入れていい列」が見つかると、変数 p に 1 を代入すると同時に、「もうこれ以上同じ列には 1 を入れてはいけない」ことを表すために、変数 K の当該列を 1 で埋め尽くします（11 行目）。最後に、1 を代入し（12 行目）、7 行目の for ループを抜け、次の i が実行されます（5 行目の for ループ）。

続いて、同じブロックに 1 が入らないようにする処理を追加ます。M[i][a] に対応するブロック番号は f(i, a)[1] で求まりますから、

for k: 1 thru 9 do (d: f(f(i, a)[1], k), K[d[1]][d[2]]: 1)
のような for ループを挿入すればよいでしょう。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
sudoku_pre3() := ([a, p, d,
    M: zeromatrix(9, 9),
    K: zeromatrix(9, 9)
    ],
    for i: 1 thru 9 do (
        p: 0,
        for j: 1 while (p = 0) do (
            a: random(9) + 1,
            if K[i][a] = 0 then (
                p: 1,
                for k: 1 thru 9 do (
                    d: f(f(i, a)[1], k),
                    K[d[1]][d[2]]: 1
                ),
                for k: i thru 9 do K[k][a]: 1,
                M[i][a]: 1
            )
        )
    ),
    M
);
11 行から 14 行に挿入してみました。この関数 sudoku_pre3() を実行すると、次のようになります。 
(%i11) sudoku_pre3();

                         [ 0  0  0  0  0  0  0  1  0 ]
                         [                           ]
                         [ 0  0  0  0  0  1  0  0  0 ]
                         [                           ]
                         [ 0  1  0  0  0  0  0  0  0 ]
                         [                           ]
                         [ 0  0  0  0  0  0  0  0  1 ]
                         [                           ]
(%o11)                   [ 0  0  0  0  1  0  0  0  0 ]
                         [                           ]
                         [ 1  0  0  0  0  0  0  0  0 ]
                         [                           ]
                         [ 0  0  0  1  0  0  0  0  0 ]
                         [                           ]
                         [ 0  0  1  0  0  0  0  0  0 ]
                         [                           ]
                         [ 0  0  0  0  0  0  1  0  0 ]
ブロックごとの色分けをしていないのでわかりにくいですが、確かに各ブロックとも 1 個づつ 1 が入っています。もちろん、同じ列にも 1 は 1 個だけです。

【失敗は成功の前触れである】

とりあえず関数 sudoku_pre3() で 1 を入れることができましたから、後はこれを 1 から 9 までループを回せば目的の関数が完成しそうです。そこで、次のような関数 sudoku_pre4() を作ってみました。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
sudoku_pre4() := ([a, p, d,
    M: zeromatrix(9, 9), 
    K: zeromatrix(9, 9)
    ],
    for l: 1 thru 9 do (
        for i: 1 while(i <= 9) do (
            p: 0,
            for j: 1 while (p = 0) do (
                a: random(9) + 1,
                if K[i][a] = 0 then (
                    p: 1,
                    for k: 1 thru 9 do (
                        d: f(f(i, a)[1], k),
                        K[d[1]][d[2]]: 1
                    ),
                    for k: i thru 9 do K[k][a]: 1,
                    M[i][a]: l
                )
            )
        ),
        K: copymatrix(M)
    ),
    M
);
これまで 1 に固定していた「入れる数 1」を変数 l に変更したこと（5 行目と 17 行目）と、変数 i に関するループ（6 行目）を抜ける度に変数 K を変数 M で置き換える処理（21 行目）を加えただけです。しかし、この関数は無限ループに入るので絶対に実行しないでください。途中で、10 行目の K[i][a]=0 を満たす a が存在しなくなり、いつまで経っても p が 1 にならないからです。関数 sudoku_pre4() が破綻する様子を見ておきましょう。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
sudoku_pre5() := ([a, p, d, q,
    M: zeromatrix(9, 9), 
    K: zeromatrix(9, 9)
    ],
    for l: 1 thru 9 do (
        q: 0,
        for i: 1 while (i <= 9 and q = 0) do (
            p: 0,
            for j: 1 while (p = 0 and q = 0) do (
                a: random(9) + 1,
                if not member(0, K[i]) then (
                    q: 1
                ) else (
                    if K[i][a] = 0 then (
                        p: 1,
                        for k: 1 thru 9 do (
                            d: f(f(i, a)[1], k),
                            K[d[1]][d[2]]: 1
                        ),
                        for k: i thru 9 do K[k][a]: 1,
                        M[i][a]: l
                    )
                )
            )
        ),
        K: copymatrix(M)
    ),
    M
);
新変数 q を用意し（6 行目）、「入れる場所」がなくなったら 1 を代入し（11 行から 13 行）、各ループを抜けるように調整しました（7 行目と 9 行目の for ループ）。早速実行してみましょう。 
(%i12) sudoku_pre5();

                         [ 4  5  6  1  9  8  7  2  3 ]
                         [                           ]
                         [ 3  1  7  2  0  4  6  8  5 ]
                         [                           ]
                         [ 0  2  8  3  5  6  0  4  1 ]
                         [                           ]
                         [ 5  0  3  4  8  0  1  6  2 ]
                         [                           ]
(%o12)                   [ 6  4  2  5  1  0  3  0  8 ]
                         [                           ]
                         [ 8  0  1  6  3  2  4  5  0 ]
                         [                           ]
                         [ 1  8  0  0  4  5  2  3  6 ]
                         [                           ]
                         [ 2  3  0  8  6  0  5  1  4 ]
                         [                           ]
                         [ 0  6  4  0  2  1  8  0  0 ]
1、2、4、6、8 については最終行（第 9 行）まで完了していますが、3 と 5 については第 8 行まで完了し、最終行で破綻しています。あと一歩でした。7 については第 3 行で早々と破綻し、9 にいたっては第 2 行で破綻というありさまです。この結果をどう捕らえるかで今後の方針が大きく異なります。
  1. 端にも棒にも着かない。
  2. 望みは薄いが、見込みがないと断言するには至らない。
  3. 脈ありと見る。
  4. 間違いなく改善できる。
端にも棒にも.....と見るなら異なるアプローチを考えなければなりませんが、6 割以上は完了しているようですので、 2 または 3 と考えるのが妥当な気がします。そこで、以下のように改良してみます。 この方針に基づいて作成したのが関数 sudoku() です。中身は概ね次のようになっています。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
sudoku() := ([a, p, d, q, n: 100,
    M: zeromatrix(9, 9), 
    K: zeromatrix(9, 9),
    T: zeromatrix(9, 9)],
    for l: 1 while (l <= 9 and n >= 0) do (
        n: n - 1,
        q: 0,
        for i: 1 while(i <= 9 and q = 0) do (
            p: 0,
            for j: 1 while (p = 0 and q = 0) do (
                a: random(9) + 1,
                if not member(0, K[i]) then (
                    q: 1,
                    l: l-1,
                    K: copymatrix(T),
                    M: copymatrix(T)
                ) else (
                    if K[i][a]=0 then (
                        p: 1,
                        for k: 1 thru 9 do (
                            d: f(f(i, a)[1], k),
                            K[d[1]][d[2]]: 1
                        ),
                        for k: i thru 9 do K[k][a]: 1,
                        M[i][a]: l
                    )
                )
            )
        ),
        K: copymatrix(M),
        T: copymatrix(M)
    ),
    if n < 0 then n else M
);
新変数 n が繰り返しの上限です。さしたる根拠もなく 100 にしてあります。入れる場所がなくなった場合に対する「やり直し処理」が 12 行から 17 行です。破綻せずにうまく完了した状態を新変数 T に保存しておき（30 行と 31 行）、for ループ変数 l を一つ戻した上で（14 行）K と M に書き戻しています（15 行と 16 行）。