"""
this is an exercise in exhaustive search AI. The puzzle8 game is where the zero ( representing an empty square)
can be moved around either north, east, west, or south and the corresponding tile moved into its place.
It uses a map of board codes seen as a history of boards visited already to avoid cycling, 
and a list as a stack for depth first searching. If the list is a queue , it becomes breadth first searching.

"""
	
import random
import time
class Board:
	__already_seen = {}
	
	def __init__(self, l = None):
	
		self._prev_board = None
			
		if l :
			self.__l= []
			self.__l.extend( l )
		else:
			random.seed(time.time())
			self.__l = random.sample( [0,1,2,3,4,5,6,7,8], 9)
		
	
	def get_code(self):
		l = ''.join( [ str(x) for x in self.__l ] )
		return l
	
	def get_vals(self):
		return self.__l
	
	def show(self):
		for i in range (0, 3):
			print self.get_val_at(0, i), self.get_val_at(  1, i) , self.get_val_at( 2, i)
	
	def set_prev(self, board):
		self._prev_board = board

	def get_prev(self):
		return self._prev_board
		
	def next( self):
		x,y = self.find_zero()
		next_boards = []
		
		for dir in ['n','s', 'e', 'w']:
			if y == 0 and dir == 'n':
				continue
			if y == 2 and dir == 's':
				continue
			if x == 0 and dir == 'w':
				continue
			if x == 2 and dir == 'e':
				continue
			next_x , next_y = x, y
			if dir == 'n':
				next_y = y -1
			if dir == 's':
				next_y = y + 1
			if dir == 'w':
				next_x = x -1
			if dir == 'e':
				next_x = x + 1
			
			#print "swap", dir, x,y, "->", next_x, next_y
			next_board = self.swap( x,y, next_x, next_y)
			if Board.__already_seen.has_key( next_board.get_code() ):
				continue
			
			next_board.set_prev(self)
			
			next_boards.append(next_board)
			Board.__already_seen[next_board.get_code()] = 1

		return next_boards
			
	def find_zero(self):
		for i in range(0,9):
			print self.__l[i]
			if self.__l[i] == 0:
				#print "found zero"
				return ( i % 3, i / 3 )
		
		raise Exception, "zero not found"
			
	def swap( self, x,y, next_x, next_y):
		new_board = Board(self.get_vals() )
		new_board.set_val_at(x,y, self.get_val_at(next_x, next_y) )
		new_board.set_val_at( next_x, next_y, self.get_val_at( x, y) )
		return new_board
			
		
	
	def _check_xy(self,x , y):
		if y < 0 or y > 2:
			raise Exception, "y = %d is out of range" %y
		if x < 0 or x > 2 :
			raise Exception, "x = %d is out of range" % x
		
			
	def get_val_at(self, x,y):
		self._check_xy(x,y)
		return self.__l[y * 3  + x] 
	
	def set_val_at(self, x,y, val):
		self._check_xy(x,y)
		self.__l[y * 3 + x] = val	
				
	def depth_search(self, target_board):
		already_seen = {}
		target_value = target_board.get_code()
		search = [self]

		while search <> []:
			candidate = search.pop()
			print "checking candidate"
			candidate.show()
			next_boards = candidate.next()
			if next_boards == [] :
				continue
			else:
				
				board_values = [ x.get_code() for x in next_boards]
				if target_value in board_values:
					for x in next_boards:
						if x.get_code() == target_board.get_code():
								print "END BOARD FOUND!"
								solution = []
								
								
								while x:
									solution.append(x)
									x = x.get_prev()
								solution.reverse()
								
								return solution
								
								
				else:
					search.extend(next_boards)

		raise Exception, "No solution found !!"
			
if __name__ == '__main__':
	print "ready to start: "
	def get_board( which = 'start'):
		s = raw_input("enter the "+which+" board as a sequence of numerals 0-8 or enter for random")
		if len(s.strip().split(' ')) < 9:
			print "less than 9 tiles specified , using random board"
			return None
		else:
			try:
				return [ int(x) for x in s.strip().split(' ')]
			except:
				print "Error in parsing numerical tokens"
				print "using random end board"
				return None
	b = Board( get_board() )
	print "start board is :"
	b.show()
	t = Board( get_board('end'))
	print
	print "target board is:"
	t.show()
	print
	raw_input("press enter to start")
	print
	print "searching"
	solution = b.depth_search(t)

	print "solution is:"

	for x in solution:
		x.show()
		print