へろぐこの広告は、90日以上更新していないブログに表示しています。珠玉のアルゴリズムデザインの第19章の"単純な数独ソルバー"のアルゴリズムを追いました。各効率化の戦略を読み解くのが大変だったので後でまた読むときのために概要だけメモを残します。数独を解くアルゴリズムをプログラム運算により効率の良いものにしていきます。言語はHaskellです。数独は次のようなゲームです。ルール・空いているマスに1〜9のいずれかの数字を入れる。・縦・横の各列及び、太線で囲まれた3×3のブロック内に同じ数字が複数入ってはいけない。Wikipedia最初のアルゴリズム最初のアルゴリズムは次のような愚直な感じの流れです。(答えの候補が膨大なので処理が終わらないです。)空のマス目に入る候補を1〜9とする。すべての空のマス目の候補の組み合わせで答えの候補を作る。答えの候補から数独ルールに合っているものを取り出して答えとする。Haskellプログラムの実行イメージは次のような感じです。"836154972"]]-}選択肢行列の枝刈り最初のアルゴリズムで空のマス目に入る候補を1〜9としていたところから、数独ルールに合わない候補を無くします。空のマス目の数が30、そこに入る候補の数の平均が4になるとすれば探索範囲数は下記のようにしぼられます。(これでも処理時間は相当かかります。)42391158275216203514294433201(9の30乗)→1152921504606846976(4の30乗)Haskellプログラムの実行イメージは次のような感じです。空のマス目1マスずつ逐次的に"答えの候補の作成"と"無効な空のマス目候補の排除"を行う事で探索範囲数の大幅な削減を期待します。)Haskellプログラムの実行イメージは次のような感じです。珠玉のアルゴリズムデザイン面白いです。図があまり無いのでイメージが湧かない面もあり手を動かす必要があると思いますが(時間があれば...)手を動かすのも楽しいです。関数プログラミング実践入門の第6章でも数独の実装例があるので読み比べるのも勉強になります。動かすとき下記は自分で定義しました。Falseあとp133に下記の誤記があります(って細かい)。(←正誤表に反映していただきました)その他は正誤表が参考になります。CDKに置き換えてみましたEC2/Laravel環境とCode4兄弟による継続的デプロイ環境をCloudFormation/Ansibleでコード化してみましたコンピュータシステムの理論と実装の1〜5章のハードウェアを実装しました(ネタバレ注意)月別アーカイブつぶやき@nihemakさんのツイートはてなブログをはじめよう!nihmaさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。