「やわらか頭でアルゴリズムを10倍生かす - 第3回 8パズル：ITpro」で紹介されているJavaでの実装をRubyで書いてみました。
Rubyだと、メソッド名をnextMoveではなくて、next_moveにしたほうが慣習にあってたりするんだろうと思いましたが、そのままにしてあります。
eight_puzzle.rb
実行結果
348215067 move left move down move down move right move up move left move left move down move right move up move up move right move down move left move up move left move down move right move down move right move up move up move left move left done
