java - 具有邻接列表的骑士巡回算法

Question

我正在尝试用 Java 解决骑士的旅行问题。我的目标是计算一匹马在任何维度的棋盘上所有可能的旅行。我尝试使用的是邻接列表数据结构。现在的问题是，我知道哪些方格与一个方格相邻，但我不知道相邻方格的方向。我该如何解决这个问题？

Answer 1

这只是您应该做什么的粗略概述：

1. 制作一个“方形”类，其中包含向上、向下、向左和向右的字段（加上访问器和修饰符方法）
2. 制作一个“棋盘”类来存储所有方格并设置它们。
3. 创建一个“骑士”类在棋盘上移动（并检查移动是否有效）。
4. 最后，创建一个驱动程序类来搜索和存储如何移动骑士。

示例 Square 类：

public class Square
{
    public final Square up;
    public final Square down;
    public final Square left;
    public final Square right;
    public Square(Square up, Square down, Square left, Square right)
    {
        this.up=up;
        this.down=down;
        this.left=left;
        this.right=right;
    }
    public Square getUp(){return up;}
    public Square getDown(){return down;}
    public Square getLeft(){return left;}
    public Square getRight(){return right;}
}

示例骑士类：

public class Knight
{
    private Square mySquare;

    public Knight(Square start)
    {
        mySquare = start;
    }

    /*  7 0
     * 6    1
     * 
     * 5    2
     *  4 3   
     */
    public boolean move(int dir)
    {
        switch(dir)
        {
        case 0: try{
           mySquare=mySquare.getUp().getUp().getRight(); return true;
        } catch (NullPointerException e) {return false}
        case 1: try{
           mySquare=mySquare.getUp().getRight().getRight(); return true;
        } catch (NullPointerException e) {return false}
        case 2: try{
           mySquare=mySquare.getDown().getRight().getRight(); return true;
        } catch (NullPointerException e) {return false}
        case 3: try{
           mySquare=mySquare.getDown().getDown().getRight(); return true;
        } catch (NullPointerException e) {return false}
        case 7: try{
           mySquare=mySquare.getUp().getUp().getLeft(); return true;
        } catch (NullPointerException e) {return false}
        case 6: try{
           mySquare=mySquare.getUp().getLeft().getLeft(); return true;
        } catch (NullPointerException e) {return false}
        case 5: try{
           mySquare=mySquare.getDown().getLeft().getLeft(); return true;
        } catch (NullPointerException e) {return false}
        case 4: try{
           mySquare=mySquare.getDown().getDown().getLeft(); return true;
        } catch (NullPointerException e) {return false}
        default: return false;
        }
    }
}