#!/usr/bin/env ruby
 
=begin
$desired_pattern = [1, 2, 3,
                    8, 0, 4,
                    7, 6, 5]
=end
$desired_pattern = [1, 2, 3,
                    4, 5, 6,
                    7, 8, 0]
 
if [0,9].include?(ARGV.size) then
else
	print "Bad usage. Examples:\n	<app>\n	<app> 1 2 3 4 5 6 7 8 0\n"
	exit
end
 
class Array
	def where(number)
		0.upto(self.size-1) do|i|
			return i if self[i] == number
		end
		return nil
	end
end
 
class VariantList
 
	@@list = []
 
	def self.add(t)
		@@list[t.fnc()] = [] if @@list[t.fnc()] == nil
		@@list[t.fnc()] << t
	end
 
	def self.include?(t)
		@@list.each do|i|
			next if i == nil
			i.each do|j|
				return true if j == t
			end
		end
		return false
	end
 
	def self.list
		@@list
	end
 
	def self.info
		print "[\n"
		@@list.each do|i|
			if i == nil then
				print "\tnil,"
			else
				i.each do|j|
					print "\t"
					j.info_line
					print j.checked?, ','
				end
			end
			print "\n"
		end
		print "]\n"
	end
 
end
 
class Tile
 
	attr_accessor :set
	attr_accessor :checked
	@@count = 0
 
	def initialize(*args)
		@set = []
		@checked = false
		if args.size == 1 && args[0].kind_of?(Array) && args[0].size == 9 then
			0.upto(8)do|i|
				if not (args[0].include?(i.to_s) || args[0].include?(i)) then
					puts "Invalid argument content."
					exit
				end
			end
			args[0].each do|a| begin
				@set[@set.size] = Integer(a)
			rescue ArgumentError
				puts "Invalid argument type."
				exit
			end end
		else
			@set = [0, 1, 2, 3, 4, 5, 6, 7, 8].sort_by { rand }
		end
 
		return nil if VariantList.include?(@set)
 
		if is_finished() then
			puts 'Finished!'
			info()
			exit
		end
 
		VariantList.add(self)
		@@count += 1
#		print '[', @@count, '] New variant (value ', hamming(), '):', "\n"
#		self.info
	end
 
	def set()
		return @set
	end
 
	def info()
		0.upto(8){|i|
			print @set[i] != 0 ? @set[i] : ' '
			if [2,5,8].include?(i) then print "\n" else print ' ' end
		}
		puts
	end
 
	def info_line()
		print '[ '
		0.upto(8){|i|
			print @set[i]
		}
		print ' ]'
	end
 
	def checked?()
		@checked
	end
 
	def check!()
		@checked = true
	end
 
	def is_finished()
		#   1 2 3
		#   8   4
		#   7 6 5
		@set == $desired_pattern
	end
 
	def ==(state)
		return matches(state)
	end
 
	def [](at)
		@set[at]
	end
 
	def []=(at, value)
		@set[at] = value
	end
 
	def matches(state)
		0.upto(8) do|i|
			return false if @set[i] != state[i]
		end
		true
	end
 
	def steps_between(i,j)
		return 0 if i == j
		return ((i/3)-(j/3)).abs + ((i%3)-(j%3)).abs
	end
 
	def where(number)
		0.upto(8) do|i|
			if @set[i] == number then return i end
		end
		print 'Invalid number search: ', number, "\n"
		exit
	end
 
	def swapped(i,j)
		ret = @set.dup
		ret[i] += ret[j]
		ret[j] = ret[i] - ret[j]
		ret[i] -= ret[j]
		return ret
	end
 
	def hamming() # returns number of wrong placed elements
		count = 0
		0.upto(8) do|i|
			count +=1 if $desired_pattern[i] != @set[i]
		end
		return count
	end
 
	def manhattan()
		sum = 0
		0.upto(8) do|i|
			sum += steps_between(where(i), $desired_pattern.where(i))
		end
		return sum
	end
 
	def fnc
		return hamming
	end
 
	def negotiate_next()
		i = where(0)
		Tile.new(swapped(i, i-1)) if not [0, 3, 6].include?(i)
		Tile.new(swapped(i, i+1)) if not [2, 5, 8].include?(i)
		Tile.new(swapped(i, i-3)) if not [0, 1, 2].include?(i)
		Tile.new(swapped(i, i+3)) if not [6, 7, 8].include?(i)
	end
 
end
 
Tile.new(ARGV)
i = 1
catch(:bigloop) do while true do
#	VariantList::info
	catch(:loop) do VariantList::list.each do|i|
		next if i == nil || i.size == 0
		i.each do|j|
			if not j.checked? then
				j.check!
				j.negotiate_next()
#				puts 'Press Enter to continue.'
#				STDIN.gets
				throw :loop
			end
		end
		throw :bigloop if i.object_id == VariantList::list[VariantList::list.size].object_id
	end end
end end