# -*- coding: utf-8 -*-
"""
Created on Sat Feb  3 20:35:18 2018

@author: ROTIMI
"""

#def divisibleSumPairs(n, k, ar):
##     Complete this function
#    ans = []
#    for char in range(n):
#        for ch in range((char+1), n):
#            if (ar[char] + ar[ch])%k == 0:
#                print((char, ch))
#                po = (char, ch)
#                if po not in ans:
#                    ans.append(po)
#    return len(ans)
#            
#
#print(divisibleSumPairs(6, 3, [1,3,2,6,1,2]))

"""alternative form of inputing from stdin"""
#f = int(input())
#for d in range(0, f):
#    g = int(input())
#    print(g+5)

#f = int(input())
#for line in range(1, f+1):
#    g = input().strip().split(' ')
#    print('max fo #:' + str(line) + ': ' + max(g))


#f = [["#", "d", "#", "i"], ["c", "i", "#"], ["#", "#", "K", 'k']]
#u = {0:'A', 1:'B', 2:'C', 3:'D', 4:'E', 5:'F', 6:'G', 7:'H'}
#def getPos(lis):
#    for i_list in lis:
#        chk = ''
#        for x in i_list:
#            chk += str(x)
#        if 'k' in chk:
#            return u[chk.index('k')] + str(lis.index(i_list)+1)
#
#print(getPos(f))


"""Josiah"""
#print('result type is total or all')
#f = True 
#inp = ''
#stor = []
#while f:
#    inp = input('enter a result type ')
#    if inp == 'a' or inp == 't':
#        f = False
#    else:
#        print('input is not valid')
#print('enter an interger to add to total or q to quit')
#g = True
#while g:
#    n = input('enter an integer o q to quit ')
#    if n.isdigit():
#        stor.append(int(n))
#    elif n == 'q':
#        g = False
#    else:
#        print(str(n) + 'is not an integer')
#        
#if inp == 'a':
#    print(all(stor))
#else:
#    print(str(sum(stor)))
#
#def fgd(m):
#    return str(sum(m))
#
#def all(n):
#    for char in n:
#        print(char)
#    d = str(sum(n))
#    e = 'total is '
#    f = e+d
#    return f

#def dfs(graph, start, goal):
#    visited = set()
#    stack = [start]
#
#    while stack:
#        node = stack.pop()
#        if node not in visited:
#            visited.add(node)
#
#            if node == goal:
#                return node
#            for neighbor in graph[node]:
#                if neighbor not in visited:
#                    stack.append(neighbor)
#                    
#small_graph = {'A': ['B', 'C'], 'B':['D'], 'C':[], 'D':[]}
#print(dfs(small_graph, 'A', 'D'))

import random
import itertools
import collections

class Node:
    """
    A class representing an Solver node
    - 'puzzle' is a Puzzle instance
    - 'parent' is the preceding node generated by the solver, if any
    - 'action' is the action taken to produce puzzle, if any
    """
    def __init__(self, puzzle, parent=None, action=None):
        self.puzzle = puzzle
        self.parent = parent
        self.action = action

    @property
    def state(self):
        """
        Return a hashable representation of self
        """
        return str(self)

    @property 
    def path(self):
        """
        Reconstruct a path from to the root 'parent'
        """
        node, p = self, []
        while node:
            p.append(node)
            node = node.parent
        yield from reversed(p)

    @property
    def solved(self):
        """ Wrapper to check if 'puzzle' is solved """
        return self.puzzle.solved

    @property
    def actions(self):
        """ Wrapper for 'actions' accessible at current state """
        return self.puzzle.actions

    def __str__(self):
        return str(self.puzzle)

class Solver:
    """
    An '8-puzzle' solver
    - 'start' is a Puzzle instance
    """
    def __init__(self, start):
        self.start = start

    def solve(self):
        """
        Perform breadth first search and return a path
        to the solution, if it exists 
        """
        queue = collections.deque([Node(self.start)])
        seen  = set()
        seen.add(queue[0].state)
        while queue:
            node = queue.pop()
            if node.solved:
                return node.path

            for move, action in node.actions:
                child = Node(move(), node, action)

                if child.state not in seen:
                    queue.appendleft(child)
                    seen.add(child.state)

class Puzzle:
    """
    A class representing an '8-puzzle'.
    - 'board' should be a square list of lists with integer entries 0...width^2 - 1
       e.g. [[1,2,3],[4,0,6],[7,5,8]]
    """
    def __init__(self, board):
        self.width = len(board[0])
        self.board = board

    @property
    def solved(self):
        """
        The puzzle is solved if the flattened board's numbers are in
        increasing order from left to right and the '0' tile is in the
        last position on the board
        """
        N = self.width * self.width
        return str(self) == ''.join(map(str, range(1,N))) + '0'

    @property 
    def actions(self):
        """
        Return a list of 'move', 'action' pairs. 'move' can be called
        to return a new puzzle that results in sliding the '0' tile in
        the direction of 'action'.
        """
        def create_move(at, to):
            return lambda: self._move(at, to)

        moves = []
        for i, j in itertools.product(range(self.width),
                                      range(self.width)):
            direcs = {'R':(i, j-1),
                      'L':(i, j+1),
                      'D':(i-1, j),
                      'U':(i+1, j)}

            for action, (r, c) in direcs.items():
                if r >= 0 and c >= 0 and r < self.width and c < self.width and \
                   self.board[r][c] == 0:
                    move = create_move((i,j), (r,c)), action
                    moves.append(move)
        return moves

    def shuffle(self):
        """
        Return a new puzzle that has been shuffled with 1000 random moves
        """
        puzzle = self
        for _ in range(1000):
            puzzle = random.choice(puzzle.actions)[0]()
        return puzzle

    def copy(self):
        """
        Return a new puzzle with the same board as 'self'
        """
        board = []
        for row in self.board:
            board.append([x for x in row])
        return Puzzle(board)

    def _move(self, at, to):
        """
        Return a new puzzle where 'at' and 'to' tiles have been swapped.
        NOTE: all moves should be 'actions' that have been executed
        """
        copy = self.copy()
        i, j = at
        r, c = to
        copy.board[i][j], copy.board[r][c] = copy.board[r][c], copy.board[i][j]
        return copy

    def pprint(self):
        for row in self.board:
            print(row)
        print()

    def __str__(self):
        return ''.join(map(str, self))

    def __iter__(self):
        for row in self.board:
            yield from row


# example of use     
board = [[1,2,3],[4,0,6],[7,5,8]]

puzzle = Puzzle(board)
puzzle = puzzle.shuffle()
s = Solver(puzzle)
p = s.solve()

for node in p:
    print(node.action)
    node.puzzle.pprint()
    
    

