gistfile1.rb

#!/usr/bin/ruby
require 'benchmark'
require 'set'
$VERBOSE = nil

H = 'md'
N = 10
Size = 3

# H ='md'
# N = 2000
# Size = 3

class Puzzle   
  attr_reader :cells
  Solution = 0.upto(Size*Size-1).to_a         

  def initialize(cells)
    @cells = cells
  end

  def solution?
    Solution == cells
  end

  def distance_to_goal
    @distance_to_goal ||= begin
      cells.zip(Solution).inject(0) do |sum, (a,b)|
        sum += manhattan_distance(a%Size, a/Size, b%Size, b/Size)
      end
    rescue Exception => error
      puts error
    end
  end

  def zero_position
    @zero_position ||= cells.index(0)
  end

  def swap(swap_index)
    new_cells = cells.clone 
    new_cells[zero_position] = new_cells[swap_index]
    new_cells[swap_index] = 0
    Puzzle.new new_cells
  end

  def misplaced_tiles
    tmp=0
    sum=0
    @misplaced_tiles = cells.each do |n|      
      sum +=1 if n != tmp
      tmp+=1
    end
    sum
  end

  def manhattan_distance(x1, y1, x2, y2)
    (x1 - x2).abs + (y1 - y2).abs
  end
end

class PuzzleState
  Directions = [:left, :right, :up, :down]
  attr_reader :puzzle, :path

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

  def to_s
    @puzzle.cells.each_with_index do |n,i| 
      print ' ' if n < 10
      print ' ' + n.to_s
      puts if (i + 1) % Size == 0 
    end
    return
  end

  def solution?
    @puzzle.solution?
  end

  def branches
    Directions.map do |direction|
      branch_toward direction
    end.compact.shuffle
  end

  def branch_toward direction
    blank_position = puzzle.zero_position
    blankx = blank_position % Size
    blanky = (blank_position / Size).to_i
    cell = case direction
    when :left
      blank_position - 1 unless 0 == blankx
    when :right
      blank_position + 1 unless (Size-1) == blankx
    when :up
      blank_position - Size unless 0 == blanky
    when :down
      blank_position + Size unless (Size-1) == blanky
    end
    self.class.new puzzle.swap(cell), @path + [direction] if cell
  end
end

class AStarSearch
  @@steps = 0
  attr_reader :visited

  def initialize
    @visited = Set.new
  end

  Infinity = 1/0.0
  Queue = Array

  def solve puzzle
    start = self.class::State.new(puzzle)
    max_cost = start.cost
    begin
      @visited = Hash.new
      solved, max_cost = recurse start, max_cost  
    end until solved

    puts "Solved: "
    p solved
  end

  def recurse state, max_cost
    visited[state.puzzle.cells] = state.cost
    return nil, state.cost if state.cost > max_cost
    return state, max_cost if state.solution?
    next_best_cost = Infinity
    solutions = []       
    state.branches.each do |branch|
      next if (visited[branch.puzzle.cells] || Infinity) < branch.cost
      solved, deeper_cost = recurse branch, max_cost  
      solutions << [solved, branch.cost] if solved
      next_best_cost = [next_best_cost, deeper_cost].min
    end
    if solutions.any?    
      if state
        puts "Step #{@@steps+=1}"
        p state
      end
      return solutions.sort_by {|_, cost| cost }.first
    end
    return nil, next_best_cost
  end

  class State < PuzzleState
    def cost
      g + h
    end

    def g
      path.size
    end

    def h
      if H == "mt"
        puzzle.misplaced_tiles
      elsif H == "md"        
        puzzle.distance_to_goal
      end
    end
  end
end

while 1
  puts "md - manhattan_distance: "
  puts "mt - misplaced_tiles "
  puts "e - exit"
  H = gets.chomp
  exit if H == "e"

  puts "Enter random(N): "
  N = gets.to_i
  puts "Enter puzzle(Size x Size): "
  Size = gets.to_i

  puts "Start:"
  root = PuzzleState.new(Puzzle.new(0.upto(Size*Size-1).to_a))
  #root = PuzzleState.new(Puzzle.new([4, 2, 0, 1, 3, 5, 6, 7, 8]))
  N.times { root = root.branches.sample }
  p root
  x = AStarSearch.new

  solution = x.solve(root.puzzle)
  puts "Directions: #{solution.path}" if solution
  puts "Steps: #{solution.path.size}" if solution
end