Trying to solve 15 Puzzle, OutOfMemoryError
Is there anyway I can optimize this code as to not run out of memory? Thanks.

    
    import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Stack;

public class TilePuzzle {

 private final static byte ROWS = 4;
 private final static byte COLUMNS = 4;
 private static String SOLUTION = "123456789ABCDEF0";
 private static byte RADIX = 16;

 private char[][] board = new char[ROWS][COLUMNS];
 private byte x; // row of the space ('0')
 private byte y; // column of the space ('0')
 private String representation;
 private boolean change = false;  // Has the board changed after the last call to toString?

 private TilePuzzle() {
  this(SOLUTION);
  int times = 1000;
  Random rnd = new Random();
  while(times-- > 0) {
   try {
    move((byte)rnd.nextInt(4));
   } catch(RuntimeException e) {
    
   }
  }
  this.representation = asString();
 }

 public TilePuzzle(String representation) {
  this.representation = representation;
  final byte SIZE = (byte)SOLUTION.length();
  if (representation.length() != SIZE) {
   throw new IllegalArgumentException("The board must have " + SIZE + "numbers.");
  }
  boolean[] used = new boolean[SIZE];
  byte idx = 0;
  for (byte i = 0; i < ROWS; ++i) {
   for (byte j = 0; j < COLUMNS; ++j) {
    char digit = representation.charAt(idx++);
    byte number = (byte)Character.digit(digit, RADIX);
    if (number < 0 || number >= SIZE) {
     throw new IllegalArgumentException("The character " + digit + " is not valid.");
    } else if(used[number]) {
     throw new IllegalArgumentException("The character " + digit + " is repeated.");
    }
    used[number] = true;
    board[i][j] = digit;
    if (digit == '0') {
     x = i;
     y = j;
    }
   }
  }
 }

 /**
  * Swap position of the space ('0') with the number that's up to it.
  */
 public void moveUp() {
  try {
   move((byte)(x - 1), y);
  } catch(IllegalArgumentException e) {
   throw new RuntimeException("Move prohibited " + e.getMessage());
  }
 }

 /**
  * Swap position of the space ('0') with the number that's down to it.
  */
 public void moveDown() {
  try {
   move((byte)(x + 1), y);
  } catch(IllegalArgumentException e) {
   throw new RuntimeException("Move prohibited " + e.getMessage());
  }
 }

 /**
  * Swap position of the space ('0') with the number that's left to it.
  */
 public void moveLeft() {
  try {
   move(x, (byte)(y - 1));
  } catch(IllegalArgumentException e) {
   throw new RuntimeException("Move prohibited " + e.getMessage());
  }
 }

 /**
  * Swap position of the space ('0') with the number that's right to it.
  */
 public void moveRight() {
  try {
   move(x, (byte)(y + 1));
  } catch(IllegalArgumentException e) {
   throw new RuntimeException("Move prohibited " + e.getMessage());
  }
 }

 private void move(byte movement) {
  switch(movement) {
  case 0:
   moveUp();
   break;
  case 1:
   moveRight();
   break;
  case 2:
   moveDown();
   break;
  case 3:
   moveLeft();
   break;
  }
 }
 
 private boolean areValidCoordinates(byte x, byte y) {
  return (x >= 0 && x < ROWS && y >= 0 && y < COLUMNS);
 }

 private void move(byte nx, byte ny) {
  if (!areValidCoordinates(nx, ny)) {
   throw new IllegalArgumentException("(" + nx + ", " + ny + ")");
  }
  board[x][y] = board[nx][ny];
  board[nx][ny] = '0';
  x = nx;
  y = ny;
  change = true;
 }

 public String printableString() {
  StringBuilder sb = new StringBuilder();
  for (byte i = 0; i < ROWS; ++i) {
   for (byte j = 0; j < COLUMNS; ++j) {
    sb.append(board[i][j] + " ");
   }
   sb.append("\r\n");
  }
  return sb.toString();
 }

 private String asString() {
  StringBuilder sb = new StringBuilder();
  for (byte i = 0; i < ROWS; ++i) {
   for (byte j = 0; j < COLUMNS; ++j) {
    sb.append(board[i][j]);
   }
  }
  return sb.toString(); 
 }

 public String toString() {
  if (change) {
   representation = asString();
  }
  return representation;
 }

 private static byte[] whereShouldItBe(char digit) {
  byte idx = (byte)SOLUTION.indexOf(digit);
  return new byte[] { (byte)(idx / ROWS), (byte)(idx % ROWS) };
 }

 private static byte manhattanDistance(byte x, byte y, byte x2, byte y2) {
  byte dx = (byte)Math.abs(x - x2);
  byte dy = (byte)Math.abs(y - y2);
  return (byte)(dx + dy);
 }

 private byte heuristic() {
  byte total = 0;
  for (byte i = 0; i < ROWS; ++i) {
   for (byte j = 0; j < COLUMNS; ++j) {
    char digit = board[i][j];
    byte[] coordenadas = whereShouldItBe(digit);
    byte distance = manhattanDistance(i, j, coordenadas[0], coordenadas[1]);
    total += distance;
   }
  }
  return total;
 }

 private class Node implements Comparable<Node> {
  private String puzzle;
  private byte moves; // number of moves from original configuration
  private byte value; // The value of the heuristic for this configuration.
  public Node(String puzzle, byte moves, byte value) {
   this.puzzle = puzzle;
   this.moves = moves;
   this.value = value;
  }
  @Override
  public int compareTo(Node o) {
   return (value + moves) - (o.value + o.moves); 
  }
 }

 private void print(Map<String, String> antecessor) {
  Stack<String> toPrint = new Stack<String>();
  toPrint.add(SOLUTION);
  String before = antecessor.get(SOLUTION);
  while (!before.equals("")) {
   toPrint.add(before);
   before = antecessor.get(before);
  }
  while (!toPrint.isEmpty()) {
   System.out.println(new TilePuzzle(toPrint.pop()).printableString());
  }
 }

 private byte solve() {
  if(toString().equals(SOLUTION)) {
   return 0;
  }

  PriorityQueue<Node> toProcess = new PriorityQueue<Node>();
  Node initial = new Node(toString(), (byte)0, heuristic());
  toProcess.add(initial);

  Map<String, String> antecessor = new HashMap<String, String>();
  antecessor.put(toString(), "");

  while(!toProcess.isEmpty()) {
   Node actual = toProcess.poll();
   for (byte i = 0; i < 4; ++i) {
    TilePuzzle t = new TilePuzzle(actual.puzzle);
    try {
     t.move(i);
    } catch(RuntimeException e) {
     continue;
    }
    if (t.toString().equals(SOLUTION)) {
     antecessor.put(SOLUTION, actual.puzzle);
     print(antecessor);
     return (byte)(actual.moves + 1);
    } else if (!antecessor.containsKey(t.toString())) {
     byte v = t.heuristic();
     Node neighbor = new Node(t.toString(), (byte)(actual.moves + 1), v);
     toProcess.add(neighbor);
     antecessor.put(t.toString(), actual.puzzle);
    }
   }
  }
  return -1;
 }

 public static void main(String... args) {
  TilePuzzle tablero = new TilePuzzle();
  System.out.println(tablero.solve());
 }
}

Trying to solve 15 Puzzle, OutOfMemoryError
===

Is there anyway I can optimize this code as to not run out of memory? Thanks.

    
    import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Stack;

public class TilePuzzle {

 private final static byte ROWS = 4;
 private final static byte COLUMNS = 4;
 private static String SOLUTION = "123456789ABCDEF0";
 private static byte RADIX = 16;

 private char[][] board = new char[ROWS][COLUMNS];
 private byte x; // row of the space ('0')
 private byte y; // column of the space ('0')
 private String representation;
 private boolean change = false;  // Has the board changed after the last call to toString?

 private TilePuzzle() {
  this(SOLUTION);
  int times = 1000;
  Random rnd = new Random();
  while(times-- > 0) {
   try {
    move((byte)rnd.nextInt(4));
   } catch(RuntimeException e) {
    
   }
  }
  this.representation = asString();
 }

 public TilePuzzle(String representation) {
  this.representation = representation;
  final byte SIZE = (byte)SOLUTION.length();
  if (representation.length() != SIZE) {
   throw new IllegalArgumentException("The board must have " + SIZE + "numbers.");
  }
  boolean[] used = new boolean[SIZE];
  byte idx = 0;
  for (byte i = 0; i < ROWS; ++i) {
   for (byte j = 0; j < COLUMNS; ++j) {
    char digit = representation.charAt(idx++);
    byte number = (byte)Character.digit(digit, RADIX);
    if (number < 0 || number >= SIZE) {
     throw new IllegalArgumentException("The character " + digit + " is not valid.");
    } else if(used[number]) {
     throw new IllegalArgumentException("The character " + digit + " is repeated.");
    }
    used[number] = true;
    board[i][j] = digit;
    if (digit == '0') {
     x = i;
     y = j;
    }
   }
  }
 }

 /**
  * Swap position of the space ('0') with the number that's up to it.
  */
 public void moveUp() {
  try {
   move((byte)(x - 1), y);
  } catch(IllegalArgumentException e) {
   throw new RuntimeException("Move prohibited " + e.getMessage());
  }
 }

 /**
  * Swap position of the space ('0') with the number that's down to it.
  */
 public void moveDown() {
  try {
   move((byte)(x + 1), y);
  } catch(IllegalArgumentException e) {
   throw new RuntimeException("Move prohibited " + e.getMessage());
  }
 }

 /**
  * Swap position of the space ('0') with the number that's left to it.
  */
 public void moveLeft() {
  try {
   move(x, (byte)(y - 1));
  } catch(IllegalArgumentException e) {
   throw new RuntimeException("Move prohibited " + e.getMessage());
  }
 }

 /**
  * Swap position of the space ('0') with the number that's right to it.
  */
 public void moveRight() {
  try {
   move(x, (byte)(y + 1));
  } catch(IllegalArgumentException e) {
   throw new RuntimeException("Move prohibited " + e.getMessage());
  }
 }

 private void move(byte movement) {
  switch(movement) {
  case 0:
   moveUp();
   break;
  case 1:
   moveRight();
   break;
  case 2:
   moveDown();
   break;
  case 3:
   moveLeft();
   break;
  }
 }
 
 private boolean areValidCoordinates(byte x, byte y) {
  return (x >= 0 && x < ROWS && y >= 0 && y < COLUMNS);
 }

 private void move(byte nx, byte ny) {
  if (!areValidCoordinates(nx, ny)) {
   throw new IllegalArgumentException("(" + nx + ", " + ny + ")");
  }
  board[x][y] = board[nx][ny];
  board[nx][ny] = '0';
  x = nx;
  y = ny;
  change = true;
 }

 public String printableString() {
  StringBuilder sb = new StringBuilder();
  for (byte i = 0; i < ROWS; ++i) {
   for (byte j = 0; j < COLUMNS; ++j) {
    sb.append(board[i][j] + " ");
   }
   sb.append("\r\n");
  }
  return sb.toString();
 }

 private String asString() {
  StringBuilder sb = new StringBuilder();
  for (byte i = 0; i < ROWS; ++i) {
   for (byte j = 0; j < COLUMNS; ++j) {
    sb.append(board[i][j]);
   }
  }
  return sb.toString(); 
 }

 public String toString() {
  if (change) {
   representation = asString();
  }
  return representation;
 }

 private static byte[] whereShouldItBe(char digit) {
  byte idx = (byte)SOLUTION.indexOf(digit);
  return new byte[] { (byte)(idx / ROWS), (byte)(idx % ROWS) };
 }

 private static byte manhattanDistance(byte x, byte y, byte x2, byte y2) {
  byte dx = (byte)Math.abs(x - x2);
  byte dy = (byte)Math.abs(y - y2);
  return (byte)(dx + dy);
 }

 private byte heuristic() {
  byte total = 0;
  for (byte i = 0; i < ROWS; ++i) {
   for (byte j = 0; j < COLUMNS; ++j) {
    char digit = board[i][j];
    byte[] coordenadas = whereShouldItBe(digit);
    byte distance = manhattanDistance(i, j, coordenadas[0], coordenadas[1]);
    total += distance;
   }
  }
  return total;
 }

 private class Node implements Comparable<Node> {
  private String puzzle;
  private byte moves; // number of moves from original configuration
  private byte value; // The value of the heuristic for this configuration.
  public Node(String puzzle, byte moves, byte value) {
   this.puzzle = puzzle;
   this.moves = moves;
   this.value = value;
  }
  @Override
  public int compareTo(Node o) {
   return (value + moves) - (o.value + o.moves); 
  }
 }

 private void print(Map<String, String> antecessor) {
  Stack<String> toPrint = new Stack<String>();
  toPrint.add(SOLUTION);
  String before = antecessor.get(SOLUTION);
  while (!before.equals("")) {
   toPrint.add(before);
   before = antecessor.get(before);
  }
  while (!toPrint.isEmpty()) {
   System.out.println(new TilePuzzle(toPrint.pop()).printableString());
  }
 }

 private byte solve() {
  if(toString().equals(SOLUTION)) {
   return 0;
  }

  PriorityQueue<Node> toProcess = new PriorityQueue<Node>();
  Node initial = new Node(toString(), (byte)0, heuristic());
  toProcess.add(initial);

  Map<String, String> antecessor = new HashMap<String, String>();
  antecessor.put(toString(), "");

  while(!toProcess.isEmpty()) {
   Node actual = toProcess.poll();
   for (byte i = 0; i < 4; ++i) {
    TilePuzzle t = new TilePuzzle(actual.puzzle);
    try {
     t.move(i);
    } catch(RuntimeException e) {
     continue;
    }
    if (t.toString().equals(SOLUTION)) {
     antecessor.put(SOLUTION, actual.puzzle);
     print(antecessor);
     return (byte)(actual.moves + 1);
    } else if (!antecessor.containsKey(t.toString())) {
     byte v = t.heuristic();
     Node neighbor = new Node(t.toString(), (byte)(actual.moves + 1), v);
     toProcess.add(neighbor);
     antecessor.put(t.toString(), actual.puzzle);
    }
   }
  }
  return -1;
 }

 public static void main(String... args) {
  TilePuzzle tablero = new TilePuzzle();
  System.out.println(tablero.solve());
 }
}
