Thinking Functionally with Haskell勉強メモ: 第5章1 数独ソルバー最適化以前
第5章は数独ソルバーの実装を通してHaskell/関数型プログラムの書き方(の一つ)を紹介するというもの。
まずは問題をできるだけ宣言的に解くコードを記述して、その後最適化していく。
この記事は第一段階の非常に非効率な宣言的コードの説明まで。
データ型の定義
まずは問題の入力と出力を表すデータ構造を型として定義する:
data Matrix a = [Row a] data Row a = [a] type Grid = Matrix Digit type Digit = Char digits :: [Digit] digits = ['1' .. '9'] blank :: Digit -> Bool blank = (=='0')
Matrix
型は[[a]]
のalias。一枚の数独問題(回答前・後を問わず)はGrid
型で表現する。Grid
はMatrix Digit
のaliasであり、Digit
はChar
のalias。記入されていないマスは0
で表される。
solve
関数
solve :: Grid -> [Grid] solve = filter valid . completions valid :: Grid -> Bool completions :: Grid -> [Grid]
数独を解く関数solve
の定義。
問題をGrid
として受け取り、正解回答となるGrid
すべてのリストを返す。completions
とvalid
という二つの関数を組み合わせて作る。
まずはcompletions
。問題Grid
を受け取り、、空のマスに1から9までを当てはめていくことで問題を(間違っていてもいいので)埋めきったすべての(非常に多くの)パターンのGrid
のリストを返す。
valid
は埋めきったGrid
が数独のルールに従っているかを判定する。valid
でフィルタすることで、すべてのパターンから正解例のみを取り出す。
completions
定義は:
completions = expand . choices
構成要素である二つの関数の型は:
choices :: Grid -> Matrix [Digits] expand :: Matrix [Digits] -> [Grid]
あるいはこちらのほうがわかりやすいかもしれない:
choices :: Matrix Digits -> Matrix [Digits] expand :: Matrix [Digits] -> [Matrix Digits]
choices
はDigits
のMatrix
である問題文から、確定しているマスは要素数1、空のマスは要素数9(1..9)のDigits
のリストのMatrix
に変換する。
expand
はその「各マスが取り得るDigit
値を列挙したリストのMatrix
」を引数にとり、「各マスの取り得る値の直積集合である『Digit
のMatrix
のリスト』」を返す。
choices
choices = map (map choice) choice d | blank d = digits | otherwise = [d]
個別のマスに対して、'0'以外ならその値のみ入っているリスト、'0'なら['1'..'9']を返すchoice
関数を適用する。
例えば引数が
[['1', '2', '3', '4', '5', '6', '7', '0', '0'], ..., ......]
だった場合、以下を返す:
[[['1'], ['2'], ['3'], ['4'], ['5'], ['6'], ['7'], ['1', '2', '3', '4', '5', '6', '7', '8', '9'], ['1', '2', '3', '4', '5', '6', '7', '8', '9']], ..., ......]
expand
expand
を定義するためにはまずcp
関数を定義する。cp
とは直積集合Cartesian Productの略。定義は:
cp :: [[a]] -> [[a]] cp [] = [[]] cp (xs:xss) = [x:ys | x <- xs, ys <- yss] where yss = cp xss
例えばcp
の引数が
[['1'], ['2'], ['3'], ['4'], ['5'], ['6'], ['7'], ['1', '2', '3', '4', '5', '6', '7', '8', '9'], ['1', '2', '3', '4', '5', '6', '7', '8', '9']]
だった場合、以下を返す:
[['1', '2', '3', '4', '5', '6', '7', '1', '1'], ['1', '2', '3', '4', '5', '6', '7', '1', '2'], ['1', '2', '3', '4', '5', '6', '7', '1', '3'], ['1', '2', '3', '4', '5', '6', '7', '1', '4'], ... ['1', '2', '3', '4', '5', '6', '7', '9', '8'], ['1', '2', '3', '4', '5', '6', '7', '9', '9'], ]
map cp
で一つ一つの行を「その行が取り得るすべての「9つのDigitのリスト」のリスト」に変換する。
それをさらにcp
することで、各行が取り得るすべての値の直積に変換する。それがマスを埋めたGridのパターンすべてを網羅したリストだ。
なのでexpand
の定義は:
expand = cp . map cp
なのでcompletions
を展開していくと:
completions = expand . choices = cp . map cp . choices = cp . map cp . map (map choice)
となる。
valid
数独のルールに従ってvalid
の定義は以下の通りになる:
valid g = all nodups (rows g) && all nodups (cols g) && all nodups (boxs g)
nodups
はno duplicatesの略。各行(rows)、各列(cols)、各3x3の区切り(boxs)にダブった数字がないことが正解の条件である。
all
all
関数はリストのすべてがpを満たしているかチェックする:
all :: (a -> Bool) -> [a] -> Bool all p = and . map p
nodups
あるリストに同じ要素が二回出てくるかチェックする関数。
nodups :: (Eq a) => [a] -> Bool nodups [] = True nodups (x:xs) = all (/=x) xs && nodups xs
一見O(n2)だがn=9なので気にしない。
rows
rows
はあるGrid
の行のリストを返す関数。
本には型はrows :: Matrix a -> Matrix a
とあったが、個人的には意味的にrows :: Matrix a -> [[a]]
ではないか?と思っている。
たまたまMatrix a
は[Row a]
なのでrow
の定義は:
row = id
cols
cols
はGrid
の列のリストを返す関数。
これと次のboxs
はどう考えてもMatrix a -> Matrix a
というよりMatrix a -> [[a]]
じゃないか?
cols = transpose transpose :: [[a]] -> [[a]] transpose [xs] = [ [x] | x <- xs] transpose (xs:xss) = zipWith (:) xs (transpose xss)
transpose
は私が定義した。本の中ではtranspose
関数はなく、直接cols
をこの定義にしていた。ただ、cols
という名前で書くのは(とくに次のboxs
でも使う手前)不適当な気がしたのでいったんtranspose
という名前で定義してcols
をaliasとした。
しかしこのtranspose
の定義、一番最後のリストを一要素ずつのリストのリストにする、というのを再帰の終了条件にして、そのリストにzipWithで前のリストの要素を付け加えていく。理屈はわかるのだが自前で考えろと言われて書ける気が全くしない・・・
boxs
boxs
は3マスx3マスの各区切りの中の数リストが9つ入ったリストを返す。
boxs :: Matrix a -> [[a]] boxs = map ungroup . ungroup . map transpose . group . map group group :: [a] -> [[a]] group [] = [] group xs = take 3 xs : group drop 3 xs ungroup :: [[a]] -> [a] ungroup = concat
リストを「3つの要素ごとのリスト」のリストに変換する関数がgroup
、それを元のリストに戻すのがungroup
(実際の処理はただのconcat
)。
挙動を理解するのがけっこうややこしい関数の組み合わせなので、4x4のMatrix
を2x2の区切り内の要素のリストに変換する様を書いてみる。
まず入力:
[[a1, a2, a3, a4], [b1, b2, b3, b4], [c1, c2, c3, c4], [d1, d2, d3, d4]]
map group
適用:
[[[a1, a2], [a3, a4]], [[b1, b2], [b3, b4]], [[c1, c2], [c3, c4]], [[d1, d2], [d3, d4]]]
中の4つの要素のリストが、2つの要素のリスト二つのリストに変換されている。
次はgroup
適用:
[[[[a1, a2], [a3, a4]], [[b1, b2], [b3, b4]]], [[[c1, c2], [c3, c4]], [[d1, d2], [d3, d4]]]]
4x2x2要素のリストのリストのリストだったのが、2x2x2x2のリストx4になっている。
map transpose
:
[[[[a1, a2], [b1, b2]], [[a3, a4], [b3, b4]]], [[[c1, c2], [d1, d2]], [[c3, c4], [d3, d4]]]]
[a3, a4]
と[b1, b2]
、[c3, c4]
と[d1, d2]
の位置が入れ替わった。
ungroup
適用:
[[[a1, a2], [b1, b2]], [[a3, a4], [b3, b4]], [[c1, c2], [d1, d2]], [[c3, c4], [d3, d4]]]
2x2x2x2から4x2x2に。
map ungroup
適用:
[[a1, a2, b1, b2], [a3, a4, b3, b4], [c1, c2, d1, d2], [c3, c4, d3, d4]]
4x4のリストのリストに戻っているが、最初のリストはa1, a2, b1, b2
と左上にあった数字、次のリストは右上、次は左下、最後は右下、と2x2に分割した各区切りの数字のリスト4つになっていることがわかる。
これを3x3の区切りで9x9のGrid
に適用したのが上記のboxs
。
結論
rows
もcols
もboxs
もすべてのリストがvalid
ならそのGrid
は数独のルール上正しく記入されていることになる。なのでcompletions
の戻り値をvalid
でフィルタすれば、正しい回答のリストが得られる。
が、completions
が返すリストは遅延評価とはいえ981-k (kは数字が知られているマスの数)もの結果を返し、それを一つ一つフィルタしていかなければいけない。現実的に不可能である。
なので次回はこの非常に効率の悪いコードに対しどのような等価な変換を加えていくことで最適化ができるか、というポイントを探っていく。