「鉛筆パズルゲームプログラミング ナンバープレース・お絵かきパズル・ナンバークロスワードのアルゴリズム」感想
タイトルどおり,ナンバープレース,お絵かきパズル(お絵かきロジック),ナンバークロスワード(ナンクロ)について,コンピュータで解いたり,作ったりしようという内容である。
プログラミング環境は,Java6.0ないしJava5.0。GenericsとかAutoBoxingとかJava5.0で追加された機能が使用されているので,1.4以前では動かない。
まずはナンバープレース編。
はじめにGUI関係の説明が少しあって,その後解答プログラムの話に移る。
当然ながら,まずは以下の2つの手法で解くことになる。
- あるマスに注目してそのマスに入りうる数字が1つしかないときに,その数字を確定する。
- ある数字に注目したとき,各3x3ボックス,ヨコ列,タテ列,の中で配置可能な場所が1か所しかなければその場所に確定する。
この本では1を消去法,2を消去法の拡張と呼んでいる。
人にとって見つけやすいのは1より2の方だから,2の方を先に持ってきてもらいたい気もするが,まあどちらでもいいだろう。
著者によると,1の手法を実装することで,
多くの問題はこれで解くことができます。しかし、稀に解くことのできない問題にあたることがあります。
1と2の両方を実装することで,
いまのところ筆者は解けない問題を発見していませんが、もしかしたらまだ解けない問題が残っているかもしれません。
だそうだ。
試しにニコリのペンパ本の数独第18巻99問がどれだけ解けるかを調べたところ,1を実装したプログラムで解けるのは,99問中たったの17問のみ,1と2を実装したプログラムで解けるのは99問中74問である。これで解けない問題を発見していないとは,いくらなんでも調査が足りないと言わざるをえない。
その次にバックトラックを用いた解法を提示している。当然この段階では全て解ける。
その次に問題の自動作成を行っている。
問題作成は,初めに完成盤面を作成して,解の一意性を確保される範囲で数字を間引いて行くという手法である。
多くのナンバープレースの問題は、上下左右対称で、中心から45度の直線に対しても対称になるように空きマスが配置されています。
ということで,縦横斜めに線対称配置になるように数字を抜いていっている。
表出数字を何個以下にするかと1,2の手筋の要否と最低適用回数など,簡単な難易度調整というかフィルタリングができるようになっている。
実際に試してみると,配置の対称性の要求が厳しいためかどうか分からないが,表出28個以下ではなかなか作ってくれない。
表出29個なら少し待つと作ってくれて,その例が今日の上の記事の問題である。それほど悪くないかも。なおこの例は中央の3がなくても成立してるから,そうすると表出28個となる。
全体の感想として,著者のナンバープレースに対する理解が十分ではないと思われ,その点が気に入らない。
第2章のお絵かきロジック編は,わたしが解答プログラムを書いたことがなくよく分からないのでパス。
問題の自動生成までは行わない。このパズルは絵が決まれば問題が決まるから,さすがに問題を作れないのは仕方がない。絵が出ない問題ではつまらないだろうし。
第3章のナンクロ編は,解くのと,あらかじめ決められた黒マス配置に対して言葉を組むのをやっているようである。
まだちゃんと読んでいないが,参考になる部分もありそうと思っている。
もし気が向いたら後日また書くかもしれないが,人のプログラムにけちをつけている暇があったら,自分のを何とかする方に時間を使った方がよさそうだから,多分これで終わりにするかも。
鉛筆パズルゲームプログラミング ナンバープレース・お絵かきパズル・ナンバークロスワードのアルゴリズム
- 作者: 棚床弘樹
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2007/06/27
- メディア: 大型本
- 購入: 2人 クリック: 23回
- この商品を含むブログ (28件) を見る