title: Generating chess knight's moves for a given depth
body: <p>I am writing a function that get's the initial position of the knight on the board as an argument and a number of moves the knight will do and returns a list of all the fields the knight will be able to achieve for the given number of moves. I ran a JUnit test and for the depth 1, 2 and 3 the function works correctly, however for the depth 4, the list misses 4 fields. I've got no idea, where the mistake could be. Here's the code:</p>
  
  <pre><code>Knight.java
  
  private boolean moveIsPossible (Position pos) {     
      return (pos.x &gt;= 0 &amp;&amp; pos.x &lt;= 7) &amp;&amp; (pos.y &gt;= 0 &amp;&amp; pos.y &lt;= 7);        
  }
  
  int [] x = {1, 2, 2, 1, -1, -2, -2, -1};
  int [] y = {2, 1, -1, -2, -2, -1, 1, 2};
  
  private ArrayList&lt;Position&gt; reachableSet = new ArrayList&lt;Position&gt;(); 
  @Override
  public ArrayList&lt;Position&gt; getReachableSet(Position pos, int numberofMoves) {
      if (!reachableSet.contains(pos)) reachableSet.add(pos);
      if (numberofMoves == 0) return reachableSet;
      ArrayList&lt;Position&gt; moves = new ArrayList&lt;Position&gt;();
      for (int i = 0; i &lt; 8; i++) {           
          Position candidate = new Position (pos.x+x[i], pos.y+y[i]);
          if (!moveIsPossible(candidate)) continue;
          if (!reachableSet.contains(candidate)) {
              moves.add(candidate);
          }
      }
      for (int j = 0; j &lt; moves.size(); j++) {
          reachableSet = getReachableSet(moves.get(j), numberofMoves-1);
      }
      return reachableSet;
  }
  </code></pre>
  
  <p>Here's the Position class:</p>
  
  <pre><code>public class Position implements Comparable&lt;Position&gt; {
  /**
   * The row on the chess board
   */
  public int x;
  
  /**
   * The column on the chess board
   */
  public int y;
  
  /**
   * Create a new position object
   * @param x the row on the chess board
   * @param y the column on the chess board
   */
  public Position(int x, int y) {
      this.x = x;
      this.y = y;
  }
  }
  </code></pre>
  
  <p><strong>Here's the JUnit test I use.</strong></p>
  
  <pre><code>public class Tests {
  private IKnight knight;
  
  @Before
  public void setup() {
      knight = KnightFactory.create();
  }
  
  private String printSet(ArrayList&lt;Position&gt; positions)
  {
      StringBuffer s = new StringBuffer("\n  ");
      for (int x=0; x&lt;IKnight.boardSize; x++) {
          s.append(x);
      }
      s.append("\n  ");
      for (int x=0; x&lt;IKnight.boardSize; x++) {
          s.append("-");
      }
      s.append("\n");
  
      for (int y=0; y&lt;IKnight.boardSize; y++) {
          s.append(y).append("|");
          for (int x=0; x&lt;IKnight.boardSize; x++) {
              if (positions.contains(new Position(x, y))) {
                  s.append("X");
              } else {
                  s.append(" ");
              }
          }
          s.append("\n");
      }
      return s.toString();
  }
  
  private void compare(ArrayList&lt;Position&gt; result, int[]... expected) {
      Collections.sort(result);
  
      ArrayList&lt;Position&gt; expectedVec = new ArrayList&lt;Position&gt;(expected.length);
      for (int[] pos : expected) {
          expectedVec.add(new Position(pos[0], pos[1]));
      }
      Collections.sort(expectedVec);
  
      Assert.assertEquals(printSet(result), expectedVec.toString(), result.toString());
  }
  
  @Test
  public void noHop() {
      ArrayList&lt;Position&gt; result = knight.getReachableSet(new Position(4, 4), 0);
      int expected[][] = { { 4, 4 } };
      compare(result, expected);
  }
  
  @Test
  public void oneHop() {
      ArrayList&lt;Position&gt; result = knight.getReachableSet(new Position(4, 4), 1);
      int expected[][] = { { 4, 4 }, { 5, 6 }, { 6, 5 }, { 6, 3 }, { 5, 2 },
              { 3, 2 }, { 2, 3 }, { 2, 5 }, { 3, 6 } };
      compare(result, expected);
  }
  
  @Test
  public void oneHopCorner() {
      ArrayList&lt;Position&gt; result = knight.getReachableSet(new Position(0, 0), 1);
      int expected[][] = { { 0, 0 }, { 1, 2 }, { 2, 1 } };
      compare(result, expected);
  }
  
  @Test
  public void twoHopsCorner() {
      ArrayList&lt;Position&gt; result = knight.getReachableSet(new Position(0, 0), 2);
      int expected[][] = { { 0, 0 }, { 0, 2 }, { 0, 4 }, { 1, 2 }, { 1, 3 },
              { 2, 0 }, { 2, 1 }, { 2, 4 }, { 3, 1 }, { 3, 3 }, { 4, 0 },
              { 4, 2 } };
      compare(result, expected);
  }
  
  @Test
  public void threeHops() {
      ArrayList&lt;Position&gt; result = knight.getReachableSet(new Position(4, 4), 3);
      int expected[][] = {{ 0, 1 }, { 0, 2 }, { 0, 3 }, { 0, 4 },
              { 0, 5 }, { 0, 6 }, { 0, 7 }, { 1, 0 }, { 1, 1 }, { 1, 2 },
              { 1, 3 }, { 1, 4 }, { 1, 5 }, { 1, 6 }, { 1, 7 }, { 2, 0 },
              { 2, 1 }, { 2, 3 }, { 2, 4 }, { 2, 5 }, 
              { 2, 7 }, { 3, 0 }, { 3, 1 }, { 3, 2 }, { 3, 3 }, { 3, 4 },
              { 3, 5 }, { 3, 6 }, { 3, 7 }, { 4, 0 }, { 4, 1 }, { 4, 2 },
              { 4, 3 }, { 4, 4 }, { 4, 5 }, { 4, 6 }, { 4, 7 }, { 5, 0 },
              { 5, 1 }, { 5, 2 }, { 5, 3 }, { 5, 4 }, { 5, 5 }, { 5, 6 },
              { 5, 7 }, { 6, 0 }, { 6, 1 }, { 6, 3 }, { 6, 4 },
              { 6, 5 }, { 6, 7 }, { 7, 0 }, { 7, 1 }, { 7, 2 },
              { 7, 3 }, { 7, 4 }, { 7, 5 }, { 7, 6 }, { 7, 7 }, };
      compare(result, expected);
  }
  
  @Test
  public void fourHops() {
      ArrayList&lt;Position&gt; result = knight.getReachableSet(new Position(4, 4), 4);
      int expected[][] = { { 0, 0 }, { 0, 1 }, { 0, 2 }, { 0, 3 }, { 0, 4 },
              { 0, 5 }, { 0, 6 }, { 0, 7 }, { 1, 0 }, { 1, 1 }, { 1, 2 },
              { 1, 3 }, { 1, 4 }, { 1, 5 }, { 1, 6 }, { 1, 7 }, { 2, 0 },
              { 2, 1 }, { 2, 2 }, { 2, 3 }, { 2, 4 }, { 2, 5 }, { 2, 6 },
              { 2, 7 }, { 3, 0 }, { 3, 1 }, { 3, 2 }, { 3, 3 }, { 3, 4 },
              { 3, 5 }, { 3, 6 }, { 3, 7 }, { 4, 0 }, { 4, 1 }, { 4, 2 },
              { 4, 3 }, { 4, 4 }, { 4, 5 }, { 4, 6 }, { 4, 7 }, { 5, 0 },
              { 5, 1 }, { 5, 2 }, { 5, 3 }, { 5, 4 }, { 5, 5 }, { 5, 6 },
              { 5, 7 }, { 6, 0 }, { 6, 1 }, { 6, 2 }, { 6, 3 }, { 6, 4 },
              { 6, 5 }, { 6, 6 }, { 6, 7 }, { 7, 0 }, { 7, 1 }, { 7, 2 },
              { 7, 3 }, { 7, 4 }, { 7, 5 }, { 7, 6 }, { 7, 7 }, };
      compare(result, expected);
  }
  </code></pre>