java - Knights Path 解决方案的 HashSet 和 LinkedHashSet 之间的行为差​​异

Question

我在编写“骑士之路”时发现一个编码谜题出现了奇怪的行为。我生成一组可能的移动并将它们存储在 HashSet 中(Move 类只有一个 x,y 坐标和一个标准的哈希码和等号)。当我在 generateMoves() 方法中使用 HashSet 时，程序找不到解决方案，而当我更改为 LinkedHashSet 时，它找到了。

public static Collection<Move> generateMoves(int startX, int startY){
    Set<Move> moves = new HashSet<Move>(); <-- doesn't work

public static Collection<Move> generateMoves(int startX, int startY){
    Set<Move> moves = new LinkedHashSet<Move>(); <-- works

我知道 HashSet 不对迭代器元素的顺序提供任何保证，但是对于最终使用回溯方法找到解决方案而言，移动的顺序应该无关紧要(某些移动顺序会更优化与其他方法不同，但使用这种蛮力方法最终应该考虑所有路径)。

很明显，HashSet 中的 Collection 的迭代器发生了一些奇怪的事情，但我进行了多次测试，以使用 LinkedHashSet 和 HashSet 比较每个棋盘位置的 generateMoves 的输出，它们是相同的。

下面是完整代码，非常感谢任何指点，因为我非常想了解这里可能发生的事情!

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 <8;i++){
            for(int j=0; j<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<Move> 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 < 0 || destX > 7 || destY < 0 || destY > 7){
            return false;//Off the board!
        }

        return board[destX][destY] == 0;
    }

    public static Collection<Move> generateMoves(int startX, int startY){
        Set<Move> moves = new HashSet<Move>();//Doesn't terminate
//      Set<Move> moves = new LinkedHashSet<Move>();//Works with Linked

        for(int i=-2; i<=2; i++){
            for(int j=-2; j<=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;
    }
}

Answer 1

在我看来，您可能看到的是 LinkedHashMap 迭代的副作用，它保证按插入顺序迭代。 HashSet 没有这种相同的保证，可以按任何顺序返回结果。

我认为移动的顺序可能对您的算法很重要，并且可能是您通过按该顺序遍历应用的意外启发式算法。移动的随机顺序可能会增加复杂性并引入许多新的和次优的路线来递归探索。

HashSet 解决方案可能会完成，尝试使用小板并查看是否能从中得到结果可能会很有趣。