[F#] 数独をF#で解く

投稿日: 2014/01/12 作成者: masuda

ふと、数独（sudoku）をF#で解く…で検索すると、

Sudoku solver in F#
http://www.ffconsultancy.com/dotnet/fsharp/sudoku/

があって、コードがええとよくわからないので、自作しました。
最初は素朴な方法を使っていて、左上から順番に数を入れて計算して、数を入れて計算してという方法をやっていたのですがいっこうに終わらないで、ちょっと考え直し。元ソースをよく見ると、左上からチェックして入れた後は、右に進むという方法をとっているので、ああ、これで十分かということで。

アルゴリズムとして、

  1. 左上（0,0）から始める。
  2. 0以外だったら、右へ進む。
  3. 1 右端に達したら次の行のはじめへ
  4. 0だったら、
  5. 横一列を調べる
  6. 縦一列を調べる
  7. 3×3のボックスを調べる
  8. 数が埋まれば、埋めて右に進んで再帰

な感じで進めればOK。そういえば、行列計算をちまちま自作していたときに思ったのですが、このあたり「アルゴリズム」≒計算機が得意とする手順は、がぜん生きていますね。普段、リスト構造とかツリー構造とかオブジェクトの構造とか、既存の.NETライブラリで賄えるものが多かったのですが、行列計算、線形代数の分野になると、高速化とか誤差も含めて数学的な解法とは違った古式ゆかしき「アルゴリズム」が生きている分野なのだな、と再確認しています。

さて、このアルゴリズムを直に実装したのが以下です。

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
let rec solve (m:int[,]) x y =
    printfn "%d %d" x y
    if x = 9 && y = 8 then
        // 完成
        printfn "%A" m
        exit 0
    elif x = 9 then
        solve m 0 (y+1)
    elif m.[x,y] <> 0 then
        solve m (x+1) y
    else
        // 縦/横/boxをチェック
        let mutable v = [|0..9|]
        for i in 0..8 do v.[m.[i,y]] <- 0
        for i in 0..8 do v.[m.[x,i]] <- 0
        let x0 = x/3*3
        let y0 = y/3*3
        for i in 0..2 do
            for j in 0..2 do
                v.[m.[x0+i,y0+j]] <- 0
 
        let m' = Array2D.copy m
        for i in 0..9 do
            if v.[i] <> 0 then
                m'.[x,y] <- v.[i]
                solve m' (x+1) y

for ループの部分が「えー」とか、match を使ったほうがいいよとか、fold の使い方を知らないとか色々あるわけですが、素直に書いたのでこんな感じ。
ただし、この再帰関数 solve は元に帰ってこなくて、完成したとき（9,8 のとき）には、無理矢理 exit してプログラムを止めています。これが再帰関数を戻すと再び別の解を探し出すので無駄なんですよね。元ネタをみると、例外を発生させているので、それでもいいのですが。末尾再帰をしているわけではないので、スタックを食うのは仕方がなく（バックトラック法だし）、ただし、ツリー構造を探索していく中で各ノードはパラレルに動かせるので探索自体は深くなりそうなときは適当にスレッド化することも可能なのかなと。このあたりは、巨大な行列計算と似た感じになると思っています。

まあ、9×9の数独ならば1秒も経たないで解けてしまうのでスレッド化する意味はありません。が、10倍ぐらいの、100×100（数字は1から100まで）の数独ならばどうなんだろうというのがあります。ウィキペディアを見ると、

Mathematics of Sudoku – Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Mathematics_of_Sudoku

ボックス（bands）が5×5の場合の計算はあるのですが、それ以上はどうなるかわからんという状態みたいです。まあ、パズルとして人間が解ける限界を超えているし、パズルとしての面白味もないので解く意味はないのですが、コンピュータに解かせるときの最適化具合を見るのにはいいかも、と。

数独を解かせるためには、配列の配列を渡してやって、Array2D に直します。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Input puzzle
let example = [|[|0;0;0;0;6;0;4;0;0|];
                [|0;5;0;0;0;3;6;0;0|];
                [|1;0;0;0;0;5;0;0;0|];
                [|0;4;1;0;0;0;0;0;0|];
                [|0;9;0;0;0;0;0;2;0|];
                [|5;0;2;0;0;0;3;4;0|];
                [|3;0;0;7;0;0;0;0;0|];
                [|0;0;6;5;0;0;0;9;0|];
                [|0;0;4;0;1;0;0;0;0|]|]
 
let pazzle = Array2D.init 9 9 (fun i j -> example.[i].[j])
 
solve pazzle 0 0

答えはこんな感じ

1
2
3
4
5
6
7
8
9
[[2; 3; 7; 1; 6; 8; 4; 5; 9]
 [4; 5; 8; 9; 7; 3; 6; 1; 2]
 [1; 6; 9; 2; 4; 5; 7; 8; 3]
 [6; 4; 1; 3; 5; 2; 9; 7; 8]
 [7; 9; 3; 4; 8; 1; 5; 2; 6]
 [5; 8; 2; 6; 9; 7; 3; 4; 1]
 [3; 1; 5; 7; 2; 9; 8; 6; 4]
 [8; 2; 6; 5; 3; 4; 1; 9; 7]
 [9; 7; 4; 8; 1; 6; 2; 3; 5]]

実は、元ネタの数独は複数回答あって、問題としてよろしくないんですよね。
それはさておき、検算をするコードが以下

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
37
38
39
let ans =
    [[2; 3; 7; 1; 6; 8; 4; 5; 9]
     [4; 5; 8; 9; 7; 3; 6; 1; 2]
     [1; 6; 9; 2; 4; 5; 7; 8; 3]
     [6; 4; 1; 3; 5; 2; 9; 7; 8]
     [7; 9; 3; 4; 8; 1; 5; 2; 6]
     [5; 8; 2; 6; 9; 7; 3; 4; 1]
     [3; 1; 5; 7; 2; 9; 8; 6; 4]
     [8; 2; 6; 5; 3; 4; 1; 9; 7]
     [9; 7; 4; 8; 1; 6; 2; 3; 5]]
 
let A = Array2D.init 9 9 (fun i j -> ans.[i].[j])
 
let check (m:int[,]) =
     
    for y in 0..8 do
        let mutable v = [|0..9|]
        for i in 0..8 do
            v.[m.[i,y]] <- 0
        if Array.sum v <> 0 then
            printfn "error y=%d" y
 
    for x in 0..8 do
        let mutable v = [|0..9|]
        for i in 0..8 do
            v.[m.[x,i]] <- 0
        if Array.sum v <> 0 then
            printfn "error x=%d" x
 
    for x in 0..3..8 do
        for y in 0..3..8 do
            let mutable v = [|0..9|]
            for i in 0..2 do
                for j in 0..2 do
                    v.[m.[x+i,y+j]] <- 0
            if Array.sum v <> 0 then
                printfn "error x=%d y=%d" x y
             
    printfn "OK"

# ああ、そうか。MSTest を使ってもいいんだっけ。どっかにサンプルページがあったはずなので後ほど。

で、bounds が 10×10の数独（全体が100×100）は、どうなるのかなと考えてみたものの…そんな数独の問題はどこにもないわけで、ということは自分で問題を作らないとダメなのですよ。どうせならば、解がひとつしかないパターンの自動作成をしたいわけで、ここは思案のしどころ。ざっと、問題作成の手順を書き下すと、

  1. 矛盾なくNxNを敷き詰める。
  2. ランダムに1個空白にする。
  3. 解が1つしかないことを確認する。再び2へ

な感じかな。3の部分を最適化したいところですが、基本は先の解法コードを拡張するだけなので、後は計算時間の問題かな。

カテゴリー: F# パーマリンク