Twitterのタイムラインで、8パズルを見かけたのでRubyで作ってみました。作ろうと思って、さっと作れるところがRubyのいいところだと思います。
8puzzle.rb
- パズルは、3x3ですが、1次元配列で扱っています。
init_puzzle
メソッドで、最初のパズル画面のデータを作成します。- 幅優先探索を使ってゴールを目指します。
array_to_int
メソッドは、パズルのデータである1次元配列のデータを整数に変換します。各数字を4ビットで表現しています。int_to_array
メソッドは、整数から1次元配列データを復元します。
実行
何回か実行してみると、おおよそ、20〜30手で解けるようですが、以下は14手で解けた例です。
$ ruby 8puzzle.rb 0: 1 3 5 4 8 2 7 6 ------ 1: 1 3 5 4 8 2 7 6 ------ 2: 1 3 4 8 5 2 7 6 ------ 3: 1 3 4 8 5 2 7 6 ------ 4: 1 3 4 8 5 2 7 6 ------ 5: 4 1 3 8 5 2 7 6 ------ 6: 4 1 3 2 8 5 7 6 ------ 7: 4 1 3 2 8 5 7 6 ------ 8: 4 1 3 2 5 7 8 6 ------ 9: 4 1 3 2 5 7 8 6 ------ 10: 1 3 4 2 5 7 8 6 ------ 11: 1 3 4 2 5 7 8 6 ------ 12: 1 2 3 4 5 7 8 6 ------ 13: 1 2 3 4 5 7 8 6 ------ 14: 1 2 3 4 5 6 7 8 ------