class SliderPuzzle
  
  def initialize(solved_state = [[0,1,2],[3,4,5]])
    @solved = solved_state
    @current = @solved.map{ |r| r.map{ |c| c } }
    @y_max = @current.size - 1
    @x_max = @current[0].size - 1
    @move_count = 0
    puts 'Initial, solved.'
    dump(@solved)
  end
  
  def possible_moves
    moves = []
    y0, x0 = blank_position
    # Check North, East, South, West.    
    moves << [y0-1, x0] if y0 > 0
    moves << [y0, x0+1] if x0 < @x_max
    moves << [y0+1, x0] if y0 < @y_max
    moves << [y0, x0-1] if x0 > 0
    moves
  end
  
  def random_move
    moves = possible_moves
    moves[rand(moves.size)]
  end
  
  def move_to_blank(point)    
    y, x = point
    y0, x0 = blank_position
    blank = @current[y0][x0]
    @current[y0][x0] = @current[y][x]
    @current[y][x] = blank
  end
  
  def blank_position
    (0...@current.length).each do |i|
      (0...@current[i].length).each do |k|
        return [i,k] if @current[i][k] == 0
      end
    end
  end
  
  def dump(board = @current)
    puts board.inspect
    puts ''
  end 
  
  def shake(n = 100)
    @move_count = 0 # In case we re-solve the same puzzle.
    n.times { move_to_blank(random_move) }
    puts 'Shaken.'
    dump(@current)
  end
   
  def solve
    while @current != @solved
      move_to_blank(random_move)
      @move_count += 1
    end
    puts "Solved in #{@move_count} moves."
    dump(@current)
  end
end

sixteen = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,0]]
nine = [[0,1,2],[3,4,5],[6,7,8]]
four = [[0,1],[2,3]]

f = SliderPuzzle.new(four)
f.shake
f.solve

n = SliderPuzzle.new(nine)
n.shake
n.solve