public class Knight
{
  boolean valid_pos;
//Global variables                                                                                                                                                                    
int size = 6;//Board size
int[][] board = new int[size][size]; //create board

public boolean main(String []args)
{
  Knight check = new Knight;
  int row, col, count=0;


  for(int a=0;a<=size;a++) //clear board to 0                                                                                                                                    
    {
      for(int b=0;b<=size;b++)
        {
          board[a][b]=0;
        }
    }

  //Take input
  row = 0;
  col = 0;

  check.valid_pos(row, col, size);

  //Output results                                                                                                                                                                

  check.recursive(row, col, size, count);
  check.display_board(size);

  return false;
}

public boolean valid_pos(int row, int col, int size){
  if(row>=size || col>=size ||  row<0 || col<0){//Test for chosen location being within board dimensions                                                                          
    return true;

  }
  else{//Check to see if location was not previously visited                                                                                                                      
    if((board[row][col]) == 0){
      return false;

    }
    else{//returns 1 if location previously visited                                                                                                                              
      return true;

    }
  }
}

public void display_board(int size)
{
  for(int c=0;c<size;c++)
    {
      for(int d=0;d<size;d++)
        {
          if(d==size-1)
            {
              System.out.println("| "+board[c][d]+" |");
            }
          else
{
              System.out.println("| "+board[c][d]+" ");
            }
        }
    }
}


public int check_board(int size)
{
  int rows, cols, checker;

  for(rows=0;rows<size;rows++)
    {
      for(cols=0;cols<size;cols++)
        {
          if(valid_pos(rows,cols,size)!= true)
            {
              checker=0;
            }
        }
    }
  return(checker);
}

public void recursive(int row, int col, int size, int count)
{

  int checked;

  board[row][col]=count;

  if(valid_pos (row+2, col+1, size)!= true)
  {
    count++;
    recursive(row+2, col+1, size, count);
    checked=check_board(size);
    if(checked==0){
      board[row+2][col+1]=0;
      count--;
    }
  }
  if(valid_pos(row+2, col-1, size)!= true)
  {
    count++;
    recursive(row+2, col-1, size, count);
    checked=check_board(size);
    if(checked==0){
      board[row+2][col-1]=0;
      count--;

    }
  }
if(valid_pos (row+1, col+2, size)!= true)
{
    count++;
    recursive(row+1, col+2, size, count);
    checked=check_board(size);
    if(checked==0){
      board[row+1][col+2]=0;
      count--;
    }
  }
  if(valid_pos (row+1, col-2, size)!= true)
  {
    count++;
    recursive(row+1, col-2, size, count);
    checked=check_board(size);
    if(checked==0){
      board[row+1][col-2]=0;
      count--;
    }
  }
  if(valid_pos(row-2, col+1, size)!= true)
  {
    count++;
    recursive(row-2, col+1, size, count);
    checked=check_board(size);
    if(checked==0){
      board[row-2][col+1]=0;
      count--;
    }
  }

if(valid_pos (row-2, col-1, size)!= true)
{
    count++;
    recursive(row-2, col-1, size, count);
    checked=check_board(size);
    if(checked==0){
      board[row-2][col-1]=0;
      count--;
    }
  }
  if(valid_pos (row-1, col+2, size)!= true)
  {
    count++;
    recursive(row-1, col+2, size, count);
    checked=check_board(size);
    if(checked==0){
      board[row-1][col+2]=0;
      count--;
    }
  }
  if(valid_pos (row-1, col-2, size)!= true)
  {
    count++;
    recursive(row-1, col-2, size, count);
    checked=check_board(size);
    if(checked==0){
      board[row-1][col-2]=0;
      count--;
    }
  }

checked=check_board(size);
  if(checked==0){
    board[row][col]=0;
    count--;
  }
}
}