// PuzzleAsArrayString
// adapting code from Kiri Wagstaff

/* locating tiles:
   123_
   12345678_
   etc
*/

import java.io.*;

public class PuzzleAsString
{

    private char BLANK=' ';     // representation of blank tile (0)
    private int SIZE;           // size of puzzle
    private int END;            // size*size-1 (lastIndex)
    private String puzzle;      // string of "tiles"
    private int blankPos;       // location of blank tile
    private int RANDOMNESS;     // Randomness of scambling puzzle  

    // Constructor: create a tile size SIZE and set params accordingly:
    public PuzzleAsString(int size,String level)
    {
		setDifficulty(level);
		setPuzzleDims(size);
		createPuzzle();
    }

    // Set difficulty (how much puzzle is scrambled):
    private void setDifficulty(String level)
    {
		if (level.equals("easy"))
		    RANDOMNESS=(int) (Math.random()*(5)+1);
		else
		    RANDOMNESS=(int) (Math.random()*(100)+1);
    }

    // Set border index values for puzzle:
    private void setPuzzleDims(int size)
    {
		SIZE = size;
		END=size*size-1;
    }
	
    // Create initial puzzle with an array and reset it:
    private void createPuzzle()
    {
		resetPuzzle();
    }
    
    // Restore puzzle to initial state:
    public void resetPuzzle()
    {
		// Fill current puzzle:
		puzzle = createTileString();

		// Set location of blank tile:
		blankPos = END;
    }

    // Create a string of numbers:
    private String createTileString()
    {
		// "Fill" puzzle with ascending numbers starting from 1.
		// Work from left-to-right, then top-down:
		String tiles="";
		for (int c=1; c <= END; c++)
		    tiles += c;
		tiles +=(""+BLANK);
		return tiles;
    }

    // Return true if puzzle is solved:
    public boolean isSolved()
    {
		return puzzle.equals(createTileString());
    }

    // Move a tile in the specified direction (dir: N/S/E/W), if possible.
    // Return true if the move was successful; otherwise, false:
    public boolean moveBlank(char dir)
    {
		char[] tiles = puzzle.toCharArray();

		switch (dir)
	    {
		    case 'N':
	                if ( (blankPos > END-SIZE) && (blankPos <= END)) return false; // no tile to move north
	                // Swap the blank and what's right below it
		        	tiles[blankPos]=puzzle.charAt(blankPos+SIZE);
		       		tiles[blankPos+SIZE]=BLANK;
	                blankPos=blankPos+SIZE;
	                break;
	        case 'S':
	                if (blankPos < SIZE) return false; // no tile to move south
	                // Swap the blank and what's right above it
			        tiles[blankPos]=puzzle.charAt(blankPos-SIZE);
		    	    tiles[blankPos-SIZE]=BLANK;
	                blankPos=blankPos-SIZE;
	                break;
	        case 'E':
		        if ((blankPos - SIZE) % SIZE==0) return false; // no tile to move east
	                // Swap the blank and what's to the left of it
		   	    	tiles[blankPos]=puzzle.charAt(blankPos-1);
		        	tiles[blankPos-1]=BLANK;
	                blankPos--;
	                break;
	        case 'W':
		        if ( (blankPos+1) % SIZE==0 ) return false; // no tile to move west
		        // Swap the blank and what's to the right of it
		        tiles[blankPos]=puzzle.charAt(blankPos+1);
		        tiles[blankPos+1]=BLANK;
	            blankPos++;
	            break;
		}
	
		puzzle = new String(tiles); // reforge the String
		return true;
    }

    // Scrambles the puzzle by making a series of random moves:
    public void scramble()
    {
		resetPuzzle();
		for (int r=0; r < RANDOMNESS; r++)
	    {
		    int m = (int)(Math.random()*SIZE);
		    switch (m)
	        {
		        case 0: moveBlank('N'); break;
		        case 1: moveBlank('S'); break;
		        case 2: moveBlank('E'); break;
		        case 3: moveBlank('W'); break;
			}
		}

    }

    // Display puzzle:
    public void display()
    {
		System.out.println(this);
    }

    // String representation of tiles:
    public String toString()
    {
		char[] tiles=puzzle.toCharArray();

		// Standard row: +-...+-...
		// assuming only size 2 or 3 to get single digits!
		String rowBorder = "+";
		for (int row=0;row<SIZE;row++)
		    rowBorder += "---+";         
		rowBorder += "\n";               
		
		// Build string that stores puzzle:
		String p=""; // string rep of puzzle
		int pos = 0;
		for (int row=0;row<SIZE;row++)
	    {
		    // Start new row:
		    p+=rowBorder+"|";

		    // Fill in tiles:
		    for (int col=0;col<SIZE;col++)
	        {
				// first padding:
				p+=" "; 

				// store tile number:
				p+=tiles[pos];

				// last padding and column:
				p+=" |";

				// update
				pos++;
			}
		    
		    // End current row:
			p+="\n";
		}
		
		// End puzzle:
		p += rowBorder;
		
		// Done!
		return p;
    }

    // Number of digits in an integer:
    private int digitCount(int num)
    {
		return (""+num).length();
    }
    
    public static void main(String[] args)
    {
    	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    	char move;
    	PuzzleAsString puzzle = new PuzzleAsString(3, "easy");
    	puzzle.scramble();
    	puzzle.display();
    	while (! puzzle.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);
			    }
			    puzzle.moveBlank(move);
			}
			catch(Exception e)
			{ 
			    System.out.println("Quitting!");
			    System.exit(0);
			}
	 
			System.out.println();
			puzzle.display();
    	}
    }
    
} // Class PuzzleAsString