続 折り紙パズル

昨日の折り紙パズル、実際に折れた方は6名（他にもできたかたは、是非ご一報ください^^）。答えは一通りでなく、何通りかあります。

20分くらいかかったというのが標準のようです。ただし実際にこのようなパズルにチャレンジしてくれるのは、よっぽど折り紙に興味がある方でしょうから、普通の人にはかなり難しい問題と思います。

与えられた展開図に対して、局所的に平坦に折りたたまれることが保証された山谷の割り当てを行うのは線形時間でできることが証明されています。しかし、紙全体が本当に平坦に折りたためるかどうかを調べるのは強NP困難な問題であることが、これもまた証明されています。仮に、正しく折れることがわかっている山谷の区別のついた展開図（問題の解答）が与えられた場合でも、妥当な紙の重なり順を決定するのは弱NP困難ですので、やはりきちんと折るのは難しい問題です（参考：Erik D. Demaine & Joseph O'Rourke, Geometric folding algorithms, p.217）。

そういう意味では、昨日のような妥当な解が存在する問題を作れたことの方が奇跡的かも。
実は調子に乗って今日は第2問目を公開、というぐあいにしたかったのですが、30分ほど試行錯誤しても作れなかった。。
このような問題を効率的に作ることも研究になるなぁ、なんて思いました。

そして、近い将来に、パズル雑誌に「折りたため」みたいな名称で、このような折り紙パズルが掲載されるようになったら楽しいなぁ、などと妄想したのでした。