プログラマの道具箱(深さ優先探索と幅優先探索) Mathematica編


参考:数独の平凡な解法(C言語Mathematica

「数独で見るRuby(とMathematica)のパワーと表現力」という記事で、『プログラミング言語Ruby』に載っている数独のコードには、Rubyのイメージをダウンさせる危険があるという話をしました。

ああいうことになってしまった原因は、与えられた問題に特化したコードを書こうとする姿勢にあると思われます。

問題を解くときには、その問題専用の道具をいきなり作ろうとするのではなく、まずは手持ちの道具の中から使えそうなものを探してみるといいでしょう。

今回の題材である数独には、簡単な探索ツールで十分です(これは、試してみてからわかることではありますが)。たいていのプログラマの道具箱には、深さ優先探索や幅優先探索のためのコードが入っているはずなので、それを使います。単純な探索ツールが道具箱に無い人は、Peter Norvigさん(Googleの研究本部長)の名著『実用 Common Lisp』の第6章(原著ではBuilding Software Tools)あたりから始めるといいかもしれません。

単純な探索というのは図のような探索木の探索です。木構造に並べた候補の中から解を探します。

探索木

木構造を探索する方法には、深さ優先探索と幅優先探索があります。これらの名前と図に示した候補を調べる順番を照らし合わせれば、探索がどのように行われるかは簡単にわかるでしょう。

探索木

実装には木構造は使いません。ノードの管理にスタックを使えば深さ優先探索に、キューを使えば幅優先探索になります。ちょっと横着して、(1)候補は前から取り出す、(2)新たな候補を、深さ優先なら前に、幅優先なら後ろに追加する、ということに決めてしまえば、いつもリストを使えばよくなります。

Mathematicaで実装すると次のようになります(UMMでも動きます)。

search[fringe_, combiner_, findAll_] :=
 If[fringe != {},
  With[{x = First@fringe},
   search[
    If[goal@x, report@x; If[findAll, Rest@fringe, {}],
     combiner[Rest@fringe, expand@x]],
    combiner, findAll]]]

goal[x_]:=解かどうかを判定する述語

report[x_]:=解を報告する手続き

expand[x_]:=探索木の子ノードのリスト(上図のAに対する{B,C}やBに対する{D,E,F}を返す関数)

ここで、fringeは解の候補を入れるリスト、combinerはリストに候補を追加するための関数、findAllは解をすべて見つけるかどうかを指示するboolean値です。

今、このような探索木のための道具が道具箱にあったとして、数独のためには次のような関数を用意しなければなりません。

goal[x_] := Not@MemberQ[x, 0, 2]

report[x_] := Sow[TableForm@x]

expand[x_] := With[{pos = First@Position[x, 0]}, 
  ReplacePart[x, pos -> #] & /@ candidates[x, pos]]

ここでcandidates[board_, {i_, j_}]は、boardのi行j列に入りうる数字のリストを作る関数です。

candidates[board_, {i_, j_}] := Complement[Range[1, 9],
  board[[i]],
  board[[Range[1, 9], j]],
  Flatten[Take[board, 3 Ceiling[i/3] - {2, 0}, 3 Ceiling[j/3] - {2, 0}]]]

準備が出来たら繰り返しの制限を緩和してから実行します(combinerをJoin[#2, #1] &にすれば深さ優先、Join[#1, #2] &にすれば幅優先探索になります)。

$IterationLimit = Infinity;

Reap@search[{ {
    {1, 0, 0, 0, 0, 7, 0, 9, 0},
    {0, 3, 0, 0, 2, 0, 0, 0, 8},
    {0, 0, 9, 6, 0, 0, 5, 0, 0},
    {0, 0, 5, 3, 0, 0, 9, 0, 0},
    {0, 1, 0, 0, 8, 0, 0, 0, 2},
    {6, 0, 0, 0, 0, 4, 0, 0, 0},
    {3, 0, 0, 0, 0, 0, 0, 1, 0},
    {0, 4, 0, 0, 0, 0, 0, 0, 7},
    {0, 0, 7, 0, 0, 0, 3, 0, 0}
   } }, Join[#2, #1] &, False]

{Null, {{1 6 2 8 5 7 4 9 3}}}
         5 3 4 1 2 9 6 7 8
         7 8 9 6 4 3 5 2 1
         4 7 5 3 1 2 9 8 6
         9 1 3 5 8 6 7 4 2
         6 2 8 7 9 4 1 3 5
         3 5 6 4 7 8 2 1 9
         2 4 1 9 3 5 8 6 7
         8 9 7 2 6 1 3 5 4

他の例:油売り算(Mathematica)

ここで紹介したのは一般的な方法ですが、深さ優先探索だけでいいなら、論理演算をつかってきれいに書けます。その方法は、「数独で見るRuby(とMathematica)のパワーと表現力」で紹介しました(HaskellPythonに移植されています)。木構造の一段下にある候補の論理和がそのノードの評価になるようにするのですが、Haskellは遅延評価なので、一つでも解が見つかればそこで評価が終了します。すべての解を求めたい場合には、そのための工夫をしなければなりません。Mathematicaは遅延評価ではないので、解が一つ見つかればいいという場合に工夫が必要です。

他の例:

参考:プログラマの道具箱(深さ優先探索と幅優先探索) C++編

数独で見るRuby(とMathematica)のパワーと表現力


参考:数独の平凡な解法(C言語Mathematica

プログラミング言語 Ruby (大型本)Rubyのバイブル『プログラミング言語 Ruby』の第1.4節では、「Rubyプログラムが実際にはどのようなものかというイメージをもっとよくつかめるように(p.18)」数独を解くRubyプログラムが紹介されています(ソースコードは原著のサポートサイトにあります)。曰く、

コメントと空行を取り除くと、ちょうど129行のコードが残る。これは、単純な力任せのアルゴリズムに頼るわけではないオブジェクト指向の数独ソルバとしてはまずまずの長さだ。このサンプルは、Rubyのパワーと表現力をよく示していると思うがどうだろうか。(p.25)

どうだろうかって、このサンプルは、Rubyのパワーと表現力を示すものとしてはふさわしくないんじゃないでしょうか。100行以上書かないと数独が解けないなんて、Rubyのイメージダウンにならなければいいのですが。

Rubyが手続き型プログラミングのためのすばらしい言語であることは否定しませんが、所詮は手続き型なので、「欲しい結果を得るための処理」を書かなければならない場合には便利でも、「欲しい結果の性質」を書けばよい言語に比べれば、プログラマの負担は大きいはずです。

Ruby本のコードには入力からゴミを取り除くような本質的ではない処理も含まれているので、行数で比較することが最善の評価法というわけではありませんが、数独はSQLなら1行ですし、その1行を生成させるJavaのコードでも70行程度です。行数というのはそんなにいい指標ではないわけですが(Pythonでは1行という話もありますし)、一つの目安ということで。

適材適所という観点から言って、数独はProlog(やSQL)のような言語で解くのがいいと思うのですが、どうしても手続き型の言語を使いたいという向きのために、Ruby本よりはシンプルな方法(10行)を紹介しましょう。実装にはMathematicaを使いますが、関数型の記述ができる言語になら簡単に翻訳できるでしょう。引用箇所の「オブジェクト指向の」は無視します。(UMMでも動きます。)

単純探索のテンプレートを使います。まず、数独に限らず、一般的な探索に使える述語を定義します。

search[x_] := Or[goal@x, deepen@x]
scanOr[f_, x_] := Catch[Scan[If[f@#, Throw@True] &, x]; False] (* 深さ優先探索 *)

数独の解を定義します。空白(0)の部分が無い(Not@MemberQ)ものが解です。

goal[x_] := And[Not@MemberQ[x, 0, 2], report@x]
report[x_] := (Sow@TableForm@x; True) (* 解の表示 *)

力任せの方法

引用箇所には「単純な力任せのアルゴリズムに頼るわけではない」とあります。Ruby本のコードは、未定のマス目に入りうる数字を数独のルール通りに決めているだけなので、「力任せ」だと言っていいと思うのですが、ここで言う「力任せ」の方法とは次のようなものでしょう。

力任せの方法:「空白部分に1から9までの数字を入れてルールをチェック」の繰り返し

述語deepenは、空白部分を調べ(Position)、1から9までの数字(Range[1,9])を入れてみて、ルール(test)に違反していなければ(Select)探索(search)を進めます。

deepen[x_] := scanOr[search, Select[ReplacePart[x, First@Position[x, 0] -> #] & /@ Range[1, 9], test]]

ルール(test)は、各行(x)と各列(Transpose@x)、各ブロック(Flatten…)を集計(Tally)し、1以上の部分({_, a_ /; a > 1})がないことを確認します。

test[x_] :=
 And @@ Map[Not[MemberQ[Tally[Select[#, (# != 0) &]], {_, a_ /; a > 1}]] &,
   Flatten[{
     x,
     Transpose@x,
     Flatten[Table[Flatten[Take[x, 3 i - {2, 0}, 3 j - {2, 0}]], {i, 1, 2}, {j, 1, 2}], 1]
     }, 1]]

再帰の深さ制限をなくしてから探索すれば、どんな問題でも解けますが、さすがに時間がかかりすぎます(「scanOr」を「Or @@ Map」に置き換えればすべての解を見つけますが、やめたほうがいいでしょう)。

$RecursionLimit = Infinity;

Reap@search@{
  {1,0,0,0,0,7,0,9,0},
  {0,3,0,0,2,0,0,0,8},
  {0,0,9,6,0,0,5,0,0},
  {0,0,5,3,0,0,9,0,0},
  {0,1,0,0,8,0,0,0,2},
  {6,0,0,0,0,4,0,0,0},
  {3,0,0,0,0,0,0,1,0},
  {0,4,0,0,0,0,0,0,7},
  {0,0,7,0,0,0,3,0,0}}

方法2(これも力任せ)

Ruby本のように、入りうる数字(candidates)をルール通りに決めて、それだけを調べるようにしてみましょう。

述語deepenは、空白の場所(pos)を、そこに入りうる数字(candidates)で置き換え(ReplacePart)、探索を進めます(入りうる数字が無いと、Or @@ Mapの結果はFalseになります)。入りうる数字だけを使うので、ルールのチェック(test)は不要です。

deepen[x_] := With[{pos = First@Position[x, 0]}, 
  Or @@ Map[search, (ReplacePart[x, pos -> #] & /@ candidates[x, pos])]]

i行j列に入りうる数字(candidates)は、1から9の数字(Range[1,9])から、i行目(board[[i]])とj列目(board[[Range[1, 9], j]])、そのマス目が属するブロック(Flatten…)に属する数字を除いたもの(Complement)です。

candidates[board_, {i_, j_}] := Complement[Range[1, 9],
  board[[i]],
  board[[Range[1, 9], j]],
  Flatten[Take[board, 3 Ceiling[i/3] - {2, 0}, 3 Ceiling[j/3] - {2, 0}]]]

今度はすぐに解が求まります(「Or @@ Map」なので、すべての解を求めます)。

Reap@search@{
  {1,0,0,0,0,7,0,9,0},
  {0,3,0,0,2,0,0,0,8},
  {0,0,9,6,0,0,5,0,0},
  {0,0,5,3,0,0,9,0,0},
  {0,1,0,0,8,0,0,0,2},
  {6,0,0,0,0,4,0,0,0},
  {3,0,0,0,0,0,0,1,0},
  {0,4,0,0,0,0,0,0,7},
  {0,0,7,0,0,0,3,0,0}}

{True, {{1 6 2 8 5 7 4 9 3}}}
         5 3 4 1 2 9 6 7 8
         7 8 9 6 4 3 5 2 1
         4 7 5 3 1 2 9 8 6
         9 1 3 5 8 6 7 4 2
         6 2 8 7 9 4 1 3 5
         3 5 6 4 7 8 2 1 9
         2 4 1 9 3 5 8 6 7
         8 9 7 2 6 1 3 5 4

結論

空行を取り除くと、ちょうど10行のコードが残ります。これは、単純な力任せのアルゴリズムに頼る関数型言語の数独ソルバとしてはまずまずの長さです。このサンプルは、Mathematicaのパワーと表現力をよく示していると思いますがどうでしょう。

search[x_] := Or[goal@x, deepen@x]
goal[x_] := And[Not@MemberQ[x, 0, 2], report@x]
report[x_] := (Sow@TableForm@x; True)
deepen[x_] := With[{pos = First@Position[x, 0]}, 
  Or @@ Map[search, (ReplacePart[x, pos -> #] & /@ candidates[x, pos])]]
candidates[board_, {i_, j_}] := Complement[Range[1, 9],
  board[[i]],
  board[[Range[1, 9], j]],
  Flatten[Take[board, 3 Ceiling[i/3] - {2, 0}, 3 Ceiling[j/3] - {2, 0}]]]
$RecursionLimit = Infinity;

補足:Mathematica 5で試す場合には、述語deepenの中のReplacePart[x, pos -> #]をReplacePart[x, #, pos]に置き換えてください。

動的SQLによる数独の超高速解法


途絶えることを知らない「どのプログラミング言語を使うべきか」論争は、あまり生産的ではないように思う。少なくとも現時点では「至高の言語」なんてものはなくて、問題によって言語を使い分けるのが最良の戦略なのではないだろうか。(チームワークにおいて言語を統一しなければならないような状況では、「そういう状況」のための最適な言語を探せばいい。その際の決定が、普遍的なものであるとは限らない。)

Doukaku?なんかを見ても、「生産性が高い」というふれこみで人気のある言語でも、問題によってはかなり悲惨な状況になることがわかる。

さて、ここに「数独」という問題がある。数独を解くルーチンsuudoku(int **p)を標準ライブラリに持っているような高級言語を残念ながら私は知らない。だから、コンピュータで数独を解きたいときは、ちょっとしたプログラムを書かなければならない。

Ai Escargot

取り得る戦略を次のように分類してみる。

  1. 数独を解くルーチン(知らない)
  2. 制約条件を記述
  3. 制約条件と解決のための具体的な手続きを記述

よくある言語論争は、「C, C++, Java, C#, Perl, Python, Rubyのどれがいい?」みたいな感じだけれど、これらの言語だと、ここに挙げた戦略の3番目しか採れない。

もうちょっと別の方法があるということを見せたいと思って、「SQLで解く」という方法を実装した。これは上に挙げた戦略では2番目に近い。

じゃあ、「数独のような問題にはSQLが最適なのか」といえば、そう単純でもなくて、ここで実装した方法は、JavaとSQLの組み合わせ。ネタとしてSQLのみでも書いたが、明らかに「組み合わせ」のほうが易しい(Javaの部分はほかの言語で置き換え可能)。

あたりまえの結論:言語は問題にあわせて選択するといいかもしれない。一つにこだわるよりも複数を組み合わせた方がいいと思われる場合もある。

「使うべき言語」ではなく「学ぶべき言語」については、少し違った議論もできると思う。何度も書いているように、私は「サピア=ウォーフの仮説」が好き。でも、人生は(今のところ)有限(しかもかなり短い)から、誰かが「学ぶべき」と言ったものを全部学べるとはとても思えない。

補足:「どのプログラミング言語を使うべきか」論争の最近の例

論文:矢吹太朗, 佐久田博司. SQLによる数独の解法とクエリオプティマイザの有効性. 日本データベース学会論文誌. Vol.9, No.2, pp.13–18, 2010.

上記論文ではDB2ではうまく行かないと報告していますが、「DB2 for IBM i でも数独が解ける!?」によれば、論文で使ったのとは別のバージョンのDB2ではうまく行くそうです。

参考:数独の平凡な解法(C言語Mathematica

SQLによる数独の解法


SQLを使って数独を解く方法の解説記事を書きました。3部構成のうちの第1部がCodeZineで公開されています

  1. SQLによる数独の解法
  2. SQLによる数独の高速解法(9/11に公開)
  3. 動的SQL数独の超高速解法(9/18に公開)

ナンプレ VOW

この記事を書くきっかけになったのは、Nintendo DSのゲーム「ナンプレ VOW」です。巷で売られている数独の問題はかなり簡単で、あまり頭を使わずに解けるのですが、解くときの爽快感と、VOWのおもしろさのために、つい何時間かはまってしまいました

ちなみに、少し頭を使わないと解けない問題は商品にならないそうです。難問を集めたはずの『激辛数独1』にさえ、次のような記述があります(試行錯誤が推理に含まれないのか、などということは別にしても私には納得できないのですが)

本書のすべての問題は、試行錯誤(このマスがもし○ならば、こうなってこうなってダメなので△我はいる。というような解き方)をすることなく、推理力を駆使して解けるようになっています

はまってしまったパズルゲームから抜け出す手段として、「パズルを解くプログラムを書く」というものがあります。「コンピュータで簡単に解けるようなパズルで時間を浪費するな」と自分を説得するのです(私にも「機械を差別する心」があるようです)

プログラムは簡単に書けるのでそれで終わりだったはずなのですが(せいぜい「数独ウォッチ」につっこみを入れるくらい)、ふと読んだこんな文章にひっかかりました

ここで示した解法プログラムは、まずまず高速です。図1の「Ai Escargot」パズルを2.4GHzのCPUと1GBのRAMを搭載したマシンで解いたところ、5分20秒で解答が導かれました。(高パフォーマンスなストアドプロシージャの設計

これはSQLのストアド・プロシジャの書き方を解説した記事なのですが、例題として取り上げた数独の問題を解くのに、5分20秒もかかったというのです

一度プログラムを書いているので、今のコンピュータなら数独を解くのにそんな時間はかからないということはすぐにわかります。読んだ人が「SQLダメじゃん」と思ってしまわないかも心配でした(はい、SQL好きです)。そこで、「こうやって書けば速いんじゃないかな」という方法を紹介することにしたのです

どのくらい速くなるかは第3部でのお楽しみということで

(CodeZineがMS系フォントをスタイル指定するのをやめますように)

論文:矢吹太朗, 佐久田博司. SQLによる数独の解法とクエリオプティマイザの有効性. 日本データベース学会論文誌. Vol.9, No.2, pp.13–18, 2010.

上記論文ではDB2では実行できないと報告していますが、「DB2 for IBM i でも数独が解ける!?」によれば、より新しいバージョンでは大丈夫だそうです。

参考:数独の平凡な解法(C言語Mathematica

オイラーを貶めるオイラー記念“数独”ウォッチ


オイラーを記念して、数独をデザインした腕時計が発売されているらしい

数学者レオンハルト・オイラー生誕300周年記念――オリス、“数独”ウォッチを発表(+D Style)

その文字盤はこんな感じ

 6  57 1
8 5     2
2
1 46
63 7   21
7
5      4
3    4 5
7  2   

解いてみようか、と誰もが思うでしょ。で、実際解いてみると、なんと、解が922個もありますぜ

Solution No.1
463257819
815439672
279861345
721346598
638795421
594128736
152673984
386914257
947582163
...
...
Solution No.922
469257813
875163942
213489576
721846395
638795421
594321768
952678134
386914257
147532689

解が複数ある悪問をオイラーと結びつけるのは、ちょっと失礼なんじゃないでしょうか。そもそも、「オイラー方陣」は数独とはずいぶん違うものなので、そういう意味でも失礼なんじゃないでしょうか(参考:岩波 数学入門辞典

こんなことで貶められるようなものでもないか、オイラーは

参考:数独の平凡な解法(C言語Mathematica