a solver for 8 number prob

main.rb

#!/usr/bin/env ruby

require 'algorithms'

class TrueClass
  def to_i
    1
  end
end

class FalseClass
  def to_i
    0
  end
end

class Array
  def merge value
    [self, value].transpose.map {|x| x.reduce(:+)}
  end
end

def getIndex array, number
  row = array.index {|l| l.include? number}
  col = array[row].index number
  [row, col]
end

def getInverseNumber array
  ans = 0
  array.each_index do |i|
    (i+1..array.length-1).to_a.each do |j|
      ans = ans + 1 if array[j] < array[i]
    end
  end
  ans
end

class Puzzle < Object
  @@dirs = [[0, 1], [0, -1], [-1, 0], [1, 0]]
  @@standard = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
  @@blank = 0

  attr_accessor :data, :backTrace, :step

  def initialize
    @data = []
    @backTrace = []
    @step = 0
  end

  def to_s
    @data.map{|x| x.join ' '}.join "\n"
  end

  def check
    @data == @@standard
  end

  def evalue
    value = @step
    (1..8).to_a.each do |i|
      value = value + [getIndex(@@standard, i), getIndex(@data, i)].transpose.map{|x| (x.first - x.last).abs}.reduce(:+)
    end
    #[@@standard, @data].transpose.each do |line|
    #  value = value + line.transpose.map{|x| (x.first == x.last).to_i}.reduce(:+)
    #end
    value
  end

  def inRange cross
    (0..2).to_a.include? cross.first and (0..2).to_a.include? cross.last
  end

  def generate
    sons = []
    @@dirs.each do |dir|
      oldBlank = getIndex @data, @@blank
      newBlank = oldBlank.merge dir
      if self.inRange newBlank
        newPuzzle = Puzzle.new
        newPuzzle.data = Marshal::load Marshal.dump self.data
        newPuzzle.backTrace = Array.new self.backTrace
        newPuzzle.backTrace << self
        newPuzzle.data[oldBlank.first][oldBlank.last] = @data[newBlank.first][newBlank.last]
        newPuzzle.data[newBlank.first][newBlank.last] = @@blank
        sons << newPuzzle
      end
    end
    sons
  end
end

visited = {}
puzzle = Puzzle.new
File.open ARGV[0], "r" do |infile|
  while line = infile.gets
    puzzle.data << line.split(' ').map{|s| s.to_i}
  end
end

if getInverseNumber(puzzle.data.reduce(:+)) % 2 == 0
  print "no solution\n"
else
  pq = Containers::PriorityQueue.new
  pq.push puzzle, -puzzle.evalue
  i = 0

  while not pq.empty?
    nowStatus = pq.pop
    i = i + 1
    if i % 100 == 0
      $stderr.print "Searched Nodes: ",i,"\n"
    end
    if not nowStatus.check
      nowStatus.generate.reject{|a| visited[a.data] == true}.each do |son|
        visited[son.data] = true
        son.step = nowStatus.step + 1
        pq.push son, -son.evalue
      end
    else
      answer = nowStatus
      break
    end
  end

  $stderr.puts "Finished Nodes: ",i

  File.open ARGV[1], "wb" do |outfile|
    answer.backTrace.shift
    answer.backTrace << answer
    outfile.puts answer.backTrace.length, "\n"
    answer.backTrace.each do |step|
      outfile.write step.to_s+"\n\n"
    end
  end
end