Rubyで15パズルを解く

Rubyで15パズルソルバを書いてみました。アルゴリズムは乱択法なのでそんなに賢くないですが、その代わり4x4から10x10までの盤面に対応できるようにしました。

## 実行結果
![15puzzle_size4.gif](https://qiita-image-store.s3.amazonaws.com/0/54587/08494707-b9ea-47b5-cc81-bd415241dd68.gif)

白はまだ揃えてないマス、緑は揃え終わったマス、赤は空白地点です。

## ソースコード

```ruby:main.rb
class SlidingPuzzle
  def initialize(size = 4)
    raise ArgumentError unless 3 < size && size < 11
    @size = size
    @space = @size**2
    @board =(1..@space).each_slice(@size).to_a
    @ans_board =(1..@space).each_slice(@size).to_a
    @unsolved_set = []
    @fixed_list = []
    printf "\e[?25l"
  end

  # 引数の回数分ランダムに動かす
  def shuffle!(num = 200)
    num.times do
      around = space_around
      move(*around.sample)
    end
  end

  # パズルを解く
  def solve
    make_set
    @unsolved_set.each do |set|
      loop do
        print_board
        around = space_around
        around.select! { |i, j| !@fixed_list.include? [i, j] }
        move(*around.sample)
        break if set.all? { |i, j| @board[i][j] == @ans_board[i][j] }
      end
      set.each do |pos|
        @fixed_list << pos
      end
    end
  rescue Interrupt
    exit 1
  ensure
    printf "\e[?25h"
  end

  # 空白地点周りの座標の集合を返す（上下左右）
  def space_around
    i = 0; j = 0
    i = @board.index @board.find { |b| j = b.index(@space) }
    [[-1, 0], [1, 0], [0, -1], [0, 1]].map do |di, dj|
      [i + di, j + dj]
    end.select do |di, dj|
      (0 <= di && di < @size) && (0 <= dj && dj < @size)
    end
  end

  # (i, j)地点の数字を空白地点と入れ替える
  # space_around の返り値の中から選んで渡してほしい
  def move(i, j)
    si = 0; sj = 0
    si = @board.index @board.find { |h| sj = h.index(@space) }
    tmp = @board[si][sj]
    @board[si][sj] = @board[i][j]
    @board[i][j] = tmp
  end

  # パズルを解く際に使用する配列を用意する
  # @unsolved_set 同時に揃えるべき座標がセットになっている
  # @fixed_list 揃えたので動かされたくない座標のリスト
  def make_set
    @unsolved_set = []
    @fixed_list = []

    (0..@size-3).each do |i|
      (0..@size-3).each do |j|
        @unsolved_set << [[i, j]]
      end
      @unsolved_set << [[i, @size-2], [i, @size-1]]
    end
    (0..@size-3).each do |j|
      @unsolved_set << [[@size-2, j], [@size-1, j]]
    end
    @unsolved_set <<
      ((@size-2)..(@size-1)).to_a
      .product(((@size-2)..(@size-1)).to_a)
  end

  def print_board
    puts self
    printf "\e[#{@size*2 + 4}A"; STDOUT.flush;
  end

  def to_s
    "\n  \e[47m  #{"    "*@size}    \e[0m" <<
    "\n  \e[47m  \e[0m#{"    "*@size}  \e[47m  \e[0m\n" <<
    @board.map.with_index do |line, i|
      "  \e[47m  \e[0m  " << line.map.with_index do |n, j|
        case n
        when @space then "\e[41m  \e[0m"
        when ->(_){ @fixed_list.include?([i, j]) }
          "\e[1;37;42m#{n.to_s.rjust(2, "0")}\e[0m"
        else "\e[1;30;47m#{n.to_s.rjust(2, "0")}\e[0m"
        end
      end.join("  ") << "  \e[47m  \e[0m"
    end.join("\n  \e[47m  \e[0m#{"    "*@size}  \e[47m  \e[0m\n") <<
    "\n  \e[47m  \e[0m#{"    "*@size}  \e[47m  \e[0m" <<
    "\n  \e[47m  #{"    "*@size}    \e[0m\n"
  end
end


puzzle = SlidingPuzzle.new(4)

puzzle.shuffle!
puts puzzle

puzzle.solve
puts puzzle
```

## 処理の流れ
ランダムに数字を動かして、所定の位置に収まった数字は動かさないようにしつつそれを最後まで繰り返します。左上から右下に向かって順番に揃えていくのですが、この方法だと右2列の横セット、下2行の縦セット、右下4マスは同時に揃えなくてはいけないというあたりを `make_set` メソッドでやっています。これは4x4以上でも同じなので、以下のように8x8で実行してもちゃんと動作します。

![15puzzle_size8.gif](https://qiita-image-store.s3.amazonaws.com/0/54587/69e48e03-fda8-d580-5578-63e5f39bd135.gif)

newの引数nによってnxnの盤面ができます。パズルを生成したら `shuffle!` して `solve` で解き始めます。途中経過の表示を消せば（26行目くらいの `print_board` をコメントアウト）6x6ぐらいまではすぐに終わります。

## おわりに
途中経過表示するとコンピュータが解いてる感あって楽しいですね。

参考サイト
[もし幼馴染と許嫁が15パズルの解法アルゴリズムを教えてくれるとしたら](http://paiza.hatenablog.com/entry/2015/06/04/%E3%82%82%E3%81%97%E5%B9%BC%E9%A6%B4%E6%9F%93%E3%81%A8%E8%A8%B1%E5%AB%81%E3%81%8C15%E3%83%91%E3%82%BA%E3%83%AB%E3%81%AE%E8%A7%A3%E6%B3%95%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%82%92)