パズルプログラミング勉強会

初心者課題：橋をかけろ

見てはいけないソース： HashioKakero.h, HashioKakero.C
by パソコン初心者

橋をかけろのルール説明 byニコリ

先日、xDSLが使えないということになった。 悲しいもので、こうなると、仕事も遊びも何もできない。掃除すらできない状態であった。

それで、ちょっと骨休め、暇潰しに、何をしようかと考えた。 私が生まれ育ったのは瀬戸内海沿岸、それも瀬戸大橋のすぐ近くであった。 そういう訳で、橋をかけろのプログラム(ソルバー)を作ることについしてしまったのである。

しかし、プログラムの完成を前に、xDSLが何とか繋がるようになり、 また未完成プログラムになるかと思ったが、何とか動作するようになったので、 とりあえず公開して恥をさらそうと思う。 複数解があるときは全部を表示し、解が無い場合は大抵どこかに矛盾があって、そのために プログラムは停止する。停止の詳しい理由は後で述べる。

実際、むちゃくちゃいい加減なプログラムである。知識らしい知識も入れていないし、 さりとて恰好良く組んだ訳でもない。奇抜なアイデアが入れられている訳でもない。 だから見るだけ無駄みたいなプログラムだが、それでも動作するようだ。

言語はC++というか、g++での動作だけ確認している。GUIなど何もないが、問題データを ファイルで用意しておけば、かなりホイホイ解いてくれる。ペンパ本１冊98問全部解かしても 5秒程度ではないかと勝手に思っている。なお、まだチューンアップなど一切していないし、 あまりそういうことをする気が無いので、そのあたりは訪問者の方に任せたい。

注意してくべきことがある。 本プログラムでは、「例外」を使ってプログラムの制御をしている。 適当にやって、矛盾したら例外を発生させるようになっている。 このため、問題が変だったときにも例外が発生してしまい、 そのためにプログラムが止まってしまうであろうが、そういう風になっている。 気に入らない人は、一番外側にも例外でも受けるようにすればトラブルを避けられるであろう。

	usage:	HashioKakero  [-g] filename

	問題ファイル
		; Vol.1 Sample
		begin
		size 9 9
		4 . 3 . 2 . 2 . 1
		. 3 . 4 . 1 . . .
		3 . 1 . 2 . 7 . 4
		. 2 . 3 . 3 . . .
		2 . 4 . 1 . 2 . .
		. 1 . 1 . 5 . . 4
		3 . 8 . 2 . . . .
		. . . 2 . 6 . 2 .
		1 . 5 . 4 . 3 . 3
		end

	実行結果
		Answer 1
		４＝３−２−２・１
		‖３＝４−１｜・｜
		３｜１｜２＝７＝４
		｜２｜３＝３‖・｜
		２｜４−１｜２・｜
		｜１‖１−５−−４
		３＝８＝２‖・・‖
		・・‖２＝６＝２‖
		１−５＝４＝３−３

	これは、ニコリのペンパ本「橋をかけろ１」の例題から取っていま〜す。

探索方法はだいたい以下の手順にそってやっている

1. (1)‥‥(1) の間には線を引けない
2. (2)‥‥(2) の間には線は高々１本しか引けない
3. 橋について、両端の島に与えられた数(未使用数)より引く線数を決める
4. 島に与えられた数(未使用数)より線を引ける方向を決める
5. 線を引くと孤島群ができるかいなか(１本、２本の場合あり)

6. 以上でダメな場合は、１手仮定、２手仮定を行って、背理法を使っている。

7. それでもダメな場合、適当な場所に、線を引かない、１本引いてみるの ２つの場合を試すことを続けることで、調べ尽くそうとしている。

※なお、仮定のレベルは現在100レベルまでになっているが、多分大丈夫。
※仮定したり、要するに探索するのに以前の状態を覚えておく必要があるが、 それには、ちょっと変なスタックを用意している。

このプログラムは、以上のようなはなはだ怠慢な作りなので、効率は極めて悪いが 意外にも高速に動いてしまった。何かの間違いであろう。 ペンパの「橋をかけろ１」の全問を今時のパソコンなら数秒くらいで解き終える能力があるようだ。 まじめに組めば、ペンパ１冊９８問を、１秒以下で解くのは間違いないだろう。

本当は、第２課題の数独の解説でもと思ったのだが、それはこの日曜日(１９日)に 行われる勉強会の楽しみにとっておこうと思う。

２００１年８月１７日