title: Trying to solve 15 Puzzle, OutOfMemoryError
body: <p>Is there any way that I can optimize this code as to not run out of memory?</p>
  
  <pre><code>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-- &gt; 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 &lt; ROWS; ++i) {
              for (byte j = 0; j &lt; COLUMNS; ++j) {
                  char digit = representation.charAt(idx++);
                  byte number = (byte)Character.digit(digit, RADIX);
                  if (number &lt; 0 || number &gt;= 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 &gt;= 0 &amp;&amp; x &lt; ROWS &amp;&amp; y &gt;= 0 &amp;&amp; y &lt; 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 &lt; ROWS; ++i) {
              for (byte j = 0; j &lt; 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 &lt; ROWS; ++i) {
              for (byte j = 0; j &lt; 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 &lt; ROWS; ++i) {
              for (byte j = 0; j &lt; COLUMNS; ++j) {
                  char digit = board[i][j];
                  byte[] coordenates = whereShouldItBe(digit);
                  byte distance = manhattanDistance(i, j, coordenates[0], coordenates[1]);
                  total += distance;
              }
          }
          return total;
      }
  
      private class Node implements Comparable&lt;Node&gt; {
          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&lt;String,String&gt; antecessor) {
          Stack toPrint = new Stack();
          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&lt;Node&gt; toProcess = new PriorityQueue();
          Node initial = new Node(toString(), (byte)0, heuristic());
          toProcess.add(initial);
  
          Map&lt;String,String&gt; antecessor = new HashMap&lt;String,String&gt;();
          antecessor.put(toString(), "");
  
          while(!toProcess.isEmpty()) {
              Node actual = toProcess.poll();
              for (byte i = 0; i &lt; 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 puzzle = new TilePuzzle();
          System.out.println(puzzle.solve());
      }
  }
  </code></pre>