title: Behaviour difference between HashSet and LinkedHashSet for Knights Path solution
body: <p>I'm seeing a strange behaviour in a coding puzzle I was working on 'Knights Path'. I generate the set of possible moves and store these in a HashSet (the Move class simply has an x,y co-ordinates and a standard hashcode and equals). When I use a HashSet in the generateMoves() method the program doesn't find a solution whereas when I change to the LinkedHashSet it does.</p>
  
  <pre><code>public static Collection&lt;Move&gt; generateMoves(int startX, int startY){
      Set&lt;Move&gt; moves = new HashSet&lt;Move&gt;(); &lt;-- doesn't work
  
  public static Collection&lt;Move&gt; generateMoves(int startX, int startY){
      Set&lt;Move&gt; moves = new LinkedHashSet&lt;Move&gt;(); &lt;-- works
  </code></pre>
  
  <p>I know that HashSet doesn't provide any guarantees on the ordering of the iterator elements but the ordering of the moves should not matter in terms of the eventual finding of a solution using backtracking method (some ordering of moves would be more optimal than others but with this brute force approach eventually all paths should be considered).</p>
  
  <p>Clearly there is something funky going on with the iterator of the Collection from HashSet but I have conducted multiple tests to compare the output of the generateMoves for every board position using a LinkedHashSet and a HashSet and they are the same. </p>
  
  <p>Full code below, any pointers greatly appreciated as I'm very curious to understand what may be going on here!</p>
  
  <pre><code>import java.util.ArrayList;
  import java.util.Collection;
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.LinkedHashSet;
  import java.util.Set;
  
  public class KnightTour {
  
      private static int countSteps = 0;
  
      public static void main(String[] args){
          int[][] board = new int[8][8];
          board[0][0] = 1;
          solveTour(board,0,0,1);
      }
  
      public static class Move{
          @Override
          public String toString() {
              return "["+ x + "," + y + "]";
          }
          int x;
          int y;
          @Override
          public int hashCode() {
              final int prime = 31;
              int result = 1;
              result = prime * result + x;
              result = prime * result + y;
              return result;
          }
          @Override
          public boolean equals(Object obj) {
              if (this == obj)
                  return true;
              if (obj == null)
                  return false;
              if (getClass() != obj.getClass())
                  return false;
              Move other = (Move) obj;
              if (x != other.x)
                  return false;
              if (y != other.y)
                  return false;
              return true;
          }
      }
  
      private static void printBoard(int[][] board){
          System.out.println("---------");
          for(int i=0;i &lt;8;i++){
              for(int j=0; j&lt;8; j++){
                  if(board[i][j] != 0){
                      System.out.print('x');
                  }else{
                      System.out.print('0');
                  }
  
              }
              System.out.println('\r');
          }
          System.out.println("---------");
      }
  
      public static boolean solveTour(int[][] sol, int x, int y, int movei){
          countSteps++;
          if(countSteps%100000 == 0){
              System.out.println("Count:"+countSteps);
          }
  
          Collection&lt;Move&gt; moves = generateMoves(x,y);
  
          if(movei == 64){
              printBoard(sol);
              return true;
          }
  
          for(Move tryMove : moves){
              int next_x = tryMove.x;
              int next_y = tryMove.y;
  
              if(isValidMove(sol, next_x,next_y)){
                  sol[next_x][next_y] = movei;
                  if(solveTour(sol, next_x, next_y, movei+1)){
                      return true;
                  }else{
                      sol[next_x][next_y] = 0;
                  }
              }
          }
  
          return false;
      }
  
      public static boolean isValidMove(int[][] board, int destX, int destY){
          if(destX &lt; 0 || destX &gt; 7 || destY &lt; 0 || destY &gt; 7){
              return false;//Off the board!
          }
  
          return board[destX][destY] == 0;
      }
  
      public static Collection&lt;Move&gt; generateMoves(int startX, int startY){
          Set&lt;Move&gt; moves = new HashSet&lt;Move&gt;();//Doesn't terminate
  //      Set&lt;Move&gt; moves = new LinkedHashSet&lt;Move&gt;();//Works with Linked
  
          for(int i=-2; i&lt;=2; i++){
              for(int j=-2; j&lt;=2; j++){
                  if(Math.abs(i) == Math.abs(j) || i == 0 || j==0 ){
                      //no op
                  }else{
                      Move m = new Move();
                      m.x = startX + i;
                      m.y = startY + j;
                      moves.add(m);
                  }
              }
          }
  
          return moves;
      }
  }
  </code></pre>