import console.*;


public class Board {


  private static final int HOLE = 0;
  
  
  private final int size, squares;
  
  private int[][] board;
  private int[] x, y;
  
  
  public Board(int n) {
  
    size = n;
    squares = n * n;
    
    board = new int[n][n];
    x = new int[squares];
    y = new int[squares];
    
    int piece = 1;
    for (int i=0; i<size; i=i+1) {
      for (int j=0; j<size; j=j+1) {
        
        board[i][j] = piece;
        x[piece] = i;
        y[piece] = j;
        piece = piece + 1;
        if (piece == squares) {
          piece = HOLE;
        }
      }
    }
  }
  
  
  public boolean success() {
  
    int piece = 0;
    
   check:
    for (int i=0; i<size; i=i+1) {
      for (int j=0; j<size; j=j+1) {
      
        piece = piece + 1;
        if ( board[i][j] != piece ) {
          break check;
        }
      }
    }
    return ( piece == squares );
  }
  
  
  public boolean free(int piece) {
  
    if ( (piece > 0) && (piece < squares) ) {
    
      int dx = Math.abs(x[piece] - x[HOLE]);
      int dy = Math.abs(y[piece] - y[HOLE]);
    
      return ( ((dx == 1) && (dy == 0)) || ((dx == 0) && (dy == 1)) );
    
    } else {
    
      return false;
    }
  }
  
  
  public void slide(int piece) {
  
    if ( free(piece) ) {
    
      board[ x[HOLE] ][ y[HOLE] ] = piece;
      board[ x[piece] ][ y[piece] ] = HOLE;
      
      int z = x[HOLE];
      x[HOLE] = x[piece];
      x[piece] = z;
      z = y[HOLE];
      y[HOLE] = y[piece];
      y[piece] = z;
    }
  }
  
  
  public void show(Console console) {
  
    console.putln();
    
    for (int i=0; i<size; i=i+1) {
      for (int j=0; j<size; j=j+1) {
      
        if ((size > 3) && (board[i][j] < 10)) {
          console.put(" ");
        }
        if (board[i][j] == HOLE) {
          console.put("   ");
        } else {
          console.put(" " + board[i][j] + " ");
        }
      }
      console.putln();
    }
    console.putln();
  }
  
  
  public void shuffle() {
  
    int moves = 50 * squares;
    
    for (int k=0; k<moves; k=k+1) {
    
      int piece = ((int) (squares * Math.random()));
      if ( free(piece) ) {
        slide(piece);
      }
    }
  }

}