箱入り娘のプログラムを書いて思う
実家に帰った際に箱入り娘のパズルがあったのでやっていた。
全然解けなかったが、プログラムで力技で解きたいと思い、やってみた
結論として、解けずに終わった。
Pythonで再帰関数で解こうとして、再帰呼び出しの上限に引っかかって30sほどでエラーとなった。
将棋などと比較すると取ることができる手ににかなりきつい制限があるので、全探索余裕と思ってしまったのだが、完全に間違っていた。
一応、盤面を都度記録し、同じ盤面になったらそれ以上は探索しないようにしたのだが、それでも解空間は大きかった。
まず、再帰による解法の選択について。現代のプログラムにおいては、上限の大きさは違えど再帰呼出の階数には制限がある。ので、対象としている問題で想定される階数に比較してプログラミング言語の制約が十分かどうか判断しなければいけなかった。あるいは、階数をパラメータとして保持しておき、起動時に何階層まで探索するか指定するような形にすればよかった。
再帰ではなく、盤面をメモリかファイルに記録し、都度記録から次の盤面を探してスタックを使用しない形にしても良かった。
そもそも論で行くと、パズルは頭の体操として娯楽としてあるもので、力技で解くことに意味あるのか? というのもある。
今回は、初めてPythonを使って割としっかりとしたプログラムが書けたので、練習として良かったということにした。
