package org.eschew.NumberGrid;
import java.util.Date;


/**
 * @author Ben Karel
 *
 */
public class NumberGrid {
     public static void main(String[] args) {
          /* Our starting positions will be (0,0) through (4,4) -- we don't
           * need to start on every single square, as the board is simply four
           * rotations of the same 5x5 grid to make one big 10x10 grid.
           */
          RealNumberGrid RNG = new RealNumberGrid();
          RNG.run();
     }
}
class RealNumberGrid implements Runnable {
	boolean printmatrices = false;
	boolean debug = true;
	
	int SIZE = 10;
     /**
       * The array of numbers representing a 10x10 grid.
       */
	int[][] board = new int[SIZE][SIZE];

     /**
       * An integer that corresponds to a direction of movement (W, SE, etc)
       */
    int direction = 0; 
     
    int lastDirection = 0;
     
     /**
      * pastMoves[iCurrent] should contain the direction used to get to
      * iCurrent.
      */
    
    int x = 0, y = 0;
    String err = "";
    /**
     * iCurrent refers to the number in the current cell, not one being written
     * to.
     */
    int iCurrent = 1;
    
    /**
     * writeNext refers to the number looking to be written to a cell that can
     * be reached from the cell containing iCurrent
     */
    int writeNext = 2;
	
	int max = SIZE * SIZE;
	int temp_x, temp_y = 0;
	int[] pastMoves = new int[max + 1];
	
	int[] pastX = new int[max + 1];
	int[] pastY = new int[max + 1];
	boolean tryAgain = true;
	boolean TRUE = true; // avoid compiler warning on while(true)
	int pass = 1;
				//    0,  1,  2  3,  4,  5, 6,  7
	int[] x_moves = { 3,  0, -3, 0, -2,  2, 2, -2 };
	int[] y_moves = { 0, -3,  0, 3, -2, -2, 2,  2 };
	
	/*
    String[] moves = {  "E",  // 0
					    "N",  // 1
						"W",  // 2
						"S",  // 3
						"NW", // 4
						"NE", // 5
						"SE", // 6
						"SW" }; // 7
	}
*/
	 RealNumberGrid() {
          this.max = SIZE * SIZE;
     }

     public void run() {
     	  Date start = new Date();
     	  System.out.println(start.getTime() + " :: "  + start.toString());
          // INITIALIZE WITH ZEROS
		  for(int i = 0; i < SIZE; ++i)
				for(int j = 0; j < SIZE; ++j) 
					board[i][j] = 0;
		  
		  for (int i = pastMoves.length - 1; i >= 0 ; --i) pastMoves[i] = 0;
          // end init
		  
          int startX = 0;
          int startY = 0;
          board[startY][startX] = 1;
		  
          /*
           * Pick from the a_moves[] arrays to get the direction to move in.
           * If it succeeds, write the **(index to moves[])** to pastMoves[]
           * 	array and increment i2m_a, then repeat.
           *  If  it fails, decrement i2m_a and repeat with picking & testing.
           */
          while (TRUE) { // this loop is for moving the startnode
              //System.out.println("(TRUE)");
              
              board[startY][startX] = iCurrent;
               outputMatrix();
               while (tryAgain) {
                   //System.out.println();
                   //System.out.println("(*TA* iCurrent = " + iCurrent + " @ (" + x + "," + y + ";  writeNext is " + writeNext);
               		pass++;
                    temp_x = x; // we know that x is valid here.
                    temp_y = y;
                    x += x_moves[direction];
                    y += y_moves[direction];
                   // err = "                          ";
           
                    if ( unoccupied(x, y) ) {
						board[y][x] = writeNext;
						
						pastMoves[iCurrent] = direction;
						
						pastY[writeNext] = y;
						pastX[writeNext] = x;
						
						if (iCurrent >= 93) {
							Date end = new Date();
							System.out.println(end.getTime() + " :: " + end.toString());
							System.out.println(end.getTime() - start.getTime() + " ms");
							System.out.println(pass + " pases");
							System.out.println("Got to limit!");
							outputMatrix();
							for (int e = 0; e <= 100; e++) {
								System.out.print(pastMoves[e]);
								if ((e % 10) == 0) {
									System.out.println();
								}
							}
							System.exit(0);
						}
								  
						iCurrent++; writeNext++;
						direction = pastMoves[iCurrent];
						
                    } else {
                         x = temp_x;
                         y = temp_y;
                         direction++;
                         validDirection();
                    }
               }
               
				board[startY][startX] = 0;
				tryAgain = true;
				startX++;
				
				if (startX == 5) {
					startX = 0;
					startY++;
				}
				
				if (startY == 5) {
					System.out.println("We're done, no solution...");
				 	System.exit(0);
				}
				
				iCurrent = 1;
				writeNext = 2;
				direction = 0;
				
				if(debug) 
				   	System.out.println("                                        New start!");
			
          }

     }
     
     /**
     * Returns true if the points exist or are
     * unoccupied.
     * 
     * @param x The x-coord to be checked.
     * @param y The y-coord to be checked.
     * @return true if the point is not out of bound and is not
     * already occupied.
     */
     private boolean unoccupied(int x, int y) {
          if (x < 0 || x >= SIZE || y < 0 || y >= SIZE) {
         //      err += " : OFF_BOARD";
               return false;
          }

          //System.out.println(x + " " + y);
          return (board[y][x] == 0);
     }

 /* This goes back through the pastMoves[] array
  * until it finds a viable move. Then the iCurrent
  * index is written to that of the latest valid node.
  */
  
     private boolean validDirection() {
          if(direction < 8) { return true; }
          else {	// would generate an IndexOutOfBoundsException
          			// tried all the fnodes for current node.
             
                   if(iCurrent == 0) {
						// this would mean that we've tried every possible path
						// from the current starting position, and should start from a new position.
						tryAgain = false;
						return false;
                   } else {/*
						if (debug && (pass % 1000 == 0)) {
							System.out.println(pass);
							//outputMatrix();
						}*/
													 
						board[y][x] = 0;			// return current position to default state
						pastMoves[iCurrent] = 0;	// reset current place on the pastMoves array
						writeNext = iCurrent;		// looking to write the number that was in the current cell into another cell
						iCurrent--;					// going to go back one space.
						pastY[writeNext] = y;		// record our current position...
						pastX[writeNext] = x;		
						y = pastY[iCurrent]; 		// and then go back to where we were before.
						x = pastX[iCurrent];
					
						direction = pastMoves[iCurrent];
						direction++;				// try the next direction.
						
							/*
						if(false && debug) {
							System.out.println("Going back to "+
												pastX[iCurrent] + "," +
												pastY[iCurrent]);
							System.out.println("After going back, new " +
									  "direction is " + direction);
						}
						  */
				   }
                return validDirection(); // recursively make sure the newly-picked state is valid.
     }
}
	
     /*
      * If the current index into the array is (5,5), then the available
      * moves are as follows:
      *             ( X , Y )
      * N ~~>  ( 5 , 2 )   +0 , -3
      * S -->  ( 5 , 8 )   +0 , +3
      * 
      * E -->  ( 8 , 5 )   +3 , +0 
      * W -->  ( 2 , 5 )   -3 , +0
      * 
      * NE --> ( 7 , 3 )   +2 , -2
      * NW --> ( 3 , 3 )   -2 , -2 
      * SW --> ( 3 , 7 )   -2 , +2 
      * SE --> ( 7 , 7 )   +2 , +2    
      */

     
     public void outputMatrix(){
         for (int i = 0; i < SIZE; ++i) {
			for (int j = 0; j < SIZE; ++j) {
				if(board[i][j] < 9) {
					System.out.print("0" + board[i][j] + " ");
				} else {
					System.out.print(board[i][j] + " ");
				}
			}
			System.out.println();
	  }
     }
}