はじめに
夏休みの旅行中に、うちの子がペグソリティアをやっているのを見て、 「これ解けたらドヤ顔できるな」と思ってチャレンジしたものの、意外に大変でした、というお話です。
解いてみる
チャレンジしたのは33ペグのやつです。
https://ja.wikipedia.org/wiki/%E3%83%9A%E3%82%B0%E3%83%BB%E3%82%BD%E3%83%AA%E3%83%86%E3%83%BC%E3%83%AB
いろんなパターンがあるようですが、一番スタンダードっぽいやつということで。
最初は、何回かチャレンジしてれば解けるやろ、と思っていたが全然できないです。 マジですか？？ヤバイという気持ちになり、PCに解いてもらおうと考えたわけです。
プログラミングする
しかし、これも意外に難しい。というか全然意外ではなく、難しいことが知られていたらしいです。 私が知らないだけでした。
こういうのとか（英語なので半分も読めてないですけど）、こういうのとか見ると、現実的な時間で解の全部を解くことはかなり困難そうだ、という印象を受けました。
がんばりました
とはいえ、仕事のあとでちょびちょびやるだけだとそこまでのエネルギーは ないというわけで、とりあえず、簡単な感じで書いてみました。
https://github.com/HideoYukutake/puzzle
なんと！時間はものすごーくかかったものの、一応、解の一つが得られました。 夜寝る前に走らせて、翌朝には解けていたので、とりあえず良しとします。
（時間を計測するのを仕込むのを忘れてしまったのが残念。）
このあとは、性能を改善するのみ！現実的な時間でちゃんと解けるようになりたいなぁ。
2019/9/22追記
あのあとも少し工夫を続けた結果、解の一つであれば、数分で得られるようになりました。7時間くらい雨後し続けると50,000超の解を得ることができましたが、まだまだ探索空間が広すぎて全体を把握できていないようです。
対称性や回転で同一となるペグの配置ができたら解決済みとする、とかの工夫が必要だなぁと思いつつ、まだ解決できていません。
