8-puzzle solver with flexible node selection

8-puzzle.rb

require 'priority_queue'
require 'set'

=begin
 - solve the 8 puzzle

 Basically, we have to treat each "State" as a node in the graph. 
 Add each 'move we can make' from the current state into the frontier
 but only if we haven't visited it yet.


=end

class Puzzle
  @@solution = (0..8).to_a

  attr_reader :cells
  
  def zero
    @cells.index(0)
  end

  def initialize(cells = (0..8).to_a.shuffle)
    @cells = cells
  end

  def solved?
    @cells == @@solution
  end

  def swap(new_index)
    z = zero

    new_cells = @cells.clone
    new_cells[z], new_cells[new_index] = new_cells[new_index], new_cells[z]

    Puzzle.new(new_cells)
  end
end

# Each StateNode should have a configurations of cells
# and also which steps were taken to get to this state (backtrace)
class StateNode
  attr_reader :puzzle, :moves

  def initialize(puzzle, moves = [])
    @puzzle, @moves = puzzle, moves
  end

  def solved?
    puzzle.solved?
  end

  # Return an array of states that can be arrived at from here
  def next_moves
    pos = @puzzle.zero 
    m = {} 

    # Which directions are possible ?
    # [0,1,2]
    # [3,4,5]
    # [6,7,8]
    
    # Get valid directions
    m[:up] = pos - 3 unless pos < 3
    m[:down] = pos + 3 unless pos > 5
    m[:left] = pos - 1 unless (pos % 3) == 0
    m[:right] = pos + 1 unless (pos % 3) == 2
    

    retval = [] 
    m.each do |direction, new_index|
      retval << StateNode.new(@puzzle.swap(new_index), moves + [direction])
    end

    retval
  end

  def priority
    @moves.count #TODO : THis should be @moves.count + manhattan distance
  end
end 

class FrontierQueue
  def initialize(*args)
    @nodes = args
  end

  def <<(node)
    @nodes << node
  end

  def next_node
    @nodes.delete_at(0)
  end
end

class PriorityFrontier 
  def initialize(*args)
    @queue = PriorityQueue.new
    args.each do |node|
      @queue.push node, node.priority
    end
  end

  def <<(node)
    @queue.push node, node.priority
  end

  def next_node
    @queue.delete_min_return_key
  end
end

class Solver
  def initialize(puzzle = Puzzle.new((0..8).to_a.shuffle))
    @puzzle = puzzle
  end

  def solve(frontier_class = FrontierQueue)
    frontier = frontier_class.new(StateNode.new(@puzzle))
    visited = Set.new
    visited << @puzzle.cells

    while current_state = frontier.next_node
      return current_state.moves if current_state.solved?

      # From the current state of the board, 
      # Find all of the moves we can potentially make
      current_state.next_moves.each do |next_move_state|
        unless visited.include?(next_move_state.puzzle.cells)
          frontier << next_move_state
          visited << next_move_state.puzzle.cells
        end
      end
    end
  end
end