flickr2006/06/18パズル「数独」をSchemeによる制約プログラミングで解くSICPは3.4節の手前で足踏み中。programingの例に釈然としないものが残る。わかんないときは自分で例を作ってみるのがいちばん。他の要素の値も定義した関係にしたがって更新されるという具合に「関係」ドリブンなプログラムを作ってみましょう、という話なんだよね。関係ドリブンで解にたどり着くといえば数理パズルなわけで、数理パズルといえばsudokuでしょう。programingでsudokuソルバとか書けないだろうか。ふつうのsudokuソルバをどのように実装するかきちんと知らないので、もしかしたら当り前すぎてバカバカしい話かもしれないし、あるいは愚かな話なのかもしれない(ちゃんと調べること→自分)。programingの練習というスタンスで。決めなければならないのは、「要素を何にするか」。ここではsudokuの各セルを要素として、そのセルが「取りうる数字」を考えることにする。最初は各セルとも、1〜9の数字をどれでも取りうる。ブロック」などをスロットと呼ぶことにすると、どのスロットも9個のセルを含み、それぞれのセルに1〜9の要素が一つずつ入らなければならない。4x4のsudokuの場合、セルは16個、スロットは12個になる。セル1〜16とスロットA〜Lの関係はこんな感じ。network図を描くのはやっかいだけど、無理に一部分を描けばこんな感じになると思う。上図の関係を見ながらプロシージャを書いていく。肝心の関係の定義は、とりあえず各スロットに、まったく同じ可能性を持つセルがあったら、ほかのセルからその可能性を取り除くこの関係だけでは解を求めるには不十分で、実際、これから示すコードで解けるsudokuの問題はほとんどない。cells)))))実際に問題を解いてみる。トップレベルでdefineを繰り返す方法がわからない......。しかたないので、各スロットのセル一覧をリストとして出力するプロシージャで我慢して、それをトップレベルに張り付けてごまかす。c99))ためしに解いてみる問題としては、「数学セミナー」の2006年5月号の西川さんの記事41ページに掲載されているものを使うことにした。みにくいけど、こんな問題。)(1)(7)(9)これらの初期値を次のように各セルに設定する。progamingのおもしろいところ。あとは出力だけしてやればいい。上記に書いたように最初に与えている関係が不十分なので、解は求まりきってない。5)(6)(9)(6)(1)(5)(3)(7)(2)(8)(4)(2)(8)(7)(4)(1)(9)(6)(3)(5)(3)(4)(5)(2)(8)(6)(1)(7)(9)doneこの結果を漫然と見る限り、スロット内での重複関係を検証するだけでは解に至らないみたいだ。(7)そういえば、Ligetiが死んだっていうニュースを最近聞いた。何枚かCDを持ってるけど、ふだん聞いて...どんな分野にも売り上げランキングというのがあって、なにかしらモノを作って販売している人間にとっては気...パズル「数独」をSchemeによる制約プログラミングで解く歯医者。磨きすぎといわれてしまった。歯茎が弱っちゃうって。自分の認識ではちゃんと磨けてる気が...誰も読む必要がない、ザ・日記が続きます。朝から実家のある柏へ。ここ数週間というもの、抜歯した奥歯の跡をどうするかという問題に頭を悩ませていた。機能を使うのが一番お手軽です。このスタイルでは、数値を指定してさまざまな囲み数字のグリフ(あれば)を呼び出すという便利な機能が提供され...職務経歴書いろいろあって職務経歴書を作成してみることにしました。編集をお手伝いしました。編集をお手伝いしました。Blogger.自己紹介k16詳細プロフィールを。