/* Designed for 3x3 puzzle only
 *
 * puzzle represented as ints
 * 0 is for blank
 * others are 1-8
 */

import java.io.*;

public class PuzzleAsUrJava
{
    private static int topL;
    private static int topM;
    private static int topR;
    private static int midL;
    private static int midM;
    private static int midR;
    private static int botL;
    private static int botM;
    private static int botR;

    // stores location of the blank tile
    private static String blank;

    // initializes the puzzle to the solved state
    public static void init()
    {
        topL = 1;
        topM = 2;
        topR = 3;
        midL = 4;
        midM = 5;
        midR = 6;
        botL = 7;
        botM = 8;
        botR = 0;

        blank = "botR";
    }
    
    // tests if puzzle is solved
    public static boolean isSolved()
    {
    	if( topL == 1 && topM == 2 && topR == 3 &&
    		midL == 4 && midM == 5 && midR == 6 &&
    		botL == 7 && botM == 8 && botR == 0 )
    		return true;
    	else
    		return false;
    }
    
    // move the blank tile in the specified direction if possible
    public static void moveBlank(char dir)
    {
    	switch(dir)
    	{
    		case 'S':
    			if( blank.equals("midL") )
    			{
    				int temp = topL;
    				topL = 0;
    				midL = temp;
    				blank = "topL";
    			}
    			else if( blank.equals("midM") )
    			{
    				int temp = topM;
    				topM = 0;
    				midM = temp;
    				blank = "topM";
    			}
    			else if( blank.equals("midR") )
    			{
    				int temp = topR;
    				topR = 0;
    				midR = temp;
    				blank = "topR";
    			}
    			else if( blank.equals("botL") )
    			{
    				int temp = midL;
    				midL = 0;
    				botL = temp;
    				blank = "midL";
    			}
    			else if( blank.equals("botM") )
    			{
    				int temp = midM;
    				midM = 0;
    				botM = temp;
    				blank = "midM";
    			}
    			else if( blank.equals("botR") )
    			{
    				int temp = midR;
    				midR = 0;
    				botR = temp;
    				blank = "midR";
    			}
    			break;
    		case 'N':
    			if( blank.equals("topL") )
    			{
    				int temp = midL;
    				midL = 0;
    				topL = temp;
    				blank = "midL";
    			}
    			else if( blank.equals("topM") )
    			{
    				int temp = midM;
    				midM = 0;
    				topM = temp;
    				blank = "midM";
    			}
    			else if( blank.equals("topR") )
    			{
    				int temp = midR;
    				midR = 0;
    				topR = temp;
    				blank = "midR";
    			}
    			else if( blank.equals("midL") )
    			{
    				int temp = botL;
    				botL = 0;
    				midL = temp;
    				blank = "botL";
    			}
    			else if( blank.equals("midM") )
    			{
    				int temp = botM;
    				botM = 0;
    				midM = temp;
    				blank = "botM";
    			}
    			else if( blank.equals("midR") )
    			{
    				int temp = botR;
    				botR = 0;
    				midR = temp;
    				blank = "botR";
    			}
    			break;
    		case 'W':
    			if( blank.equals("topL") )
    			{
    				int temp = topM;
    				topM = 0;
    				topL = temp;
    				blank = "topM";
    			}
    			else if( blank.equals("midL") )
    			{
    				int temp = midM;
    				midM = 0;
    				midL = temp;
    				blank = "midM";
    			}
    			else if( blank.equals("botL") )
    			{
    				int temp = botM;
    				botM = 0;
    				botL = temp;
    				blank = "botM";
    			}
    			else if( blank.equals("topM") )
    			{
    				int temp = topR;
    				topR = 0;
    				topM = temp;
    				blank = "topR";
    			}
    			else if( blank.equals("midM") )
    			{
    				int temp = midR;
    				midR = 0;
    				midM = temp;
    				blank = "midR";
    			}
    			else if( blank.equals("botM") )
    			{
    				int temp = botR;
    				botR = 0;
    				botM = temp;
    				blank = "botR";
    			}
    			break;
    		case 'E':
    			if( blank.equals("topM") )
    			{
    				int temp = topL;
    				topL = 0;
    				topM = temp;
    				blank = "topL";
    			}
    			else if( blank.equals("midM") )
    			{
    				int temp = midL;
    				midL = 0;
    				midM = temp;
    				blank = "midL";
    			}
    			else if( blank.equals("botM") )
    			{
    				int temp = botL;
    				botL = 0;
    				botM = temp;
    				blank = "botL";
    			}
    			else if( blank.equals("topR") )
    			{
    				int temp = topM;
    				topM = 0;
    				topR = temp;
    				blank = "topM";
    			}
    			else if( blank.equals("midR") )
    			{
    				int temp = midM;
    				midM = 0;
    				midR = temp;
    				blank = "midM";
    			}
    			else if( blank.equals("botR") )
    			{
    				int temp = botM;
    				botM = 0;
    				botR = temp;
    				blank = "botM";
    			}
    			break;
    		default: break;
    	}
    }

    // scrambles the puzzle with 50 random moves
    public static void scramble()
    {
        for(int i = 0; i < 50; i++)
        {
        	int ran = (int)(Math.random()*3);
        	switch(ran)
        	{
        		case 1: moveBlank('N'); break;
        		case 2: moveBlank('S'); break;
        		case 3: moveBlank('E'); break;
        		case 4: moveBlank('W'); break;
        	}
        }
    }
    
    // display the puzzle
    public static void display()
    {
    	System.out.println( topL + " " + topM + " " + topR);
    	System.out.println( midL + " " + midM + " " + midR);
    	System.out.println( botL + " " + botM + " " + botR + '\n');
    }
    
    
    public static void main(String[] args)
    {
    	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    	char move;
    	PuzzleAsUrJava.init();
    	PuzzleAsUrJava.scramble();
    	PuzzleAsUrJava.display();
    	while (! PuzzleAsUrJava.isSolved() )
    	{
    		try
    		{ 
			    System.out.print("Enter a move [NSEW]: ");
			    move=((in.readLine()).toUpperCase()).charAt(0);
			    while  ( !(move=='N' || move=='S' || move=='E' || move=='W') )
			    {
					System.out.print("I do not recognize that move. ");
					System.out.print("Enter a real move [NSEW]: ");
					move = ((in.readLine()).toUpperCase()).charAt(0);
			    }
			    PuzzleAsUrJava.moveBlank(move);
			}
			catch(Exception e)
			{ 
			    System.out.println("Quitting!");
			    System.exit(0);
			}
	 
			System.out.println();
			PuzzleAsUrJava.display();
    	}
    }

}