/**
 * @(#)Knight.java
 *
 *
 * @author
 * @version 1.00 2009/12/10
 */
import java.util.ArrayList;
public class Knight {

    /**
     * Creates a new instance of <code>Knight</code>.
     */
    static int g_sqSize = 5;
    static int[][] g_board;

    public static boolean InRangeAndEmpty(int y, int x){
    	return (y>=0 && x >=0 && y < g_sqSize && x < g_sqSize && g_board[y][x] == 0);
    }

    public static void PrintBoard(){
    	//int scale = ((String)(g_sqSize*g_sqSize)).length;
    	System.out.println("________________");
    	for (int[] line : g_board){
    		for (int element : line){
    			System.out.print(element + " ");
    		}
    		System.out.println();
    	}
    }

    public static void Fill(int y, int x, int counter){
    	//assume g_board[y][x] == 1;
    	g_board[y][x] = counter; //Fill initial
    	if (counter == g_sqSize*g_sqSize){ //Check if this is the last square
    		PrintBoard();
    		return;
    	}

    	ArrayList<ArrayList> emptyNeighbors = new ArrayList<ArrayList>();; //Calculate empty neighbors
    	int[][] jumps = {
    			{-2, 1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}
    		};
    	for (int[] jump : jumps){
    		int _y = y+jump[0];
    		int _x = x+jump[1];
    		int[] __xy = {_y, _x};
    		ArrayList<Integer> _xy = new ArrayList<Integer>();
    		for (int _elem : __xy){
    			_xy.add(_elem);
    		}
    		if (InRangeAndEmpty(_y, _x)){
    			emptyNeighbors.add(_xy);
    		}

    	}
    	PrintBoard();
    	// Recurse with each neightbor, heuristically weigh those with least # of free neighbors
    	// 1 for neigh
    	for (ArrayList<Integer> neighbor : emptyNeighbors){
    		Fill(neighbor.get(0), neighbor.get(1), counter+1);
    	}

    	g_board[y][x] = 0;
    }



    public static void main(String[] args) {
        // TODO code application logic here
        //Fill with 0
        g_board = new int[g_sqSize][g_sqSize];
        for (int i=0;i < g_sqSize;i++){
        	for(int r = 0; r < g_sqSize; r++){
        		g_board[i][r] = 0;
        	}
        }
        Fill(0,0,1);
    }

}