Knight's tour algorithm with adjacency-lists

Question

I'm trying to solve the Knight's tour problem in Java. My goal is to calculate all possible tours of a horse on a chessboard with any dimension. What I have tried to use is an adjadency-lists data structure. The problem now, is that I know which squares are adjacent to a square, but I don't know what direction the adjacent square is in. How would I fix this?

Bifid

Do your adjacency lists store "legal jumps" or do they store "neighboring squares"?. And why do you need directions, would it not be simpler to only store "square IDs", where the 1st square is '0' and so on?. – Organotherapy

What do you mean with "legal jumps"? – Bifid

"legal jump" would be a legal knight's move in your chessboard. When talking adjacency-lists, networks come to mind. You are trying to build a hamiltonian path through all squares, and it makes sense to reformulate your network by connecting squares only when it is knight-legal to jump between them. – Organotherapy

Can you elaborate about what you mean by "what direction the adjacent square is in?" – Truncate

Answer 1

Here's just a rough outline of what you should do:

1. Make a "Square" class with fields for up, down, left, and right (plus accessor and modifier methods)
2. Make a "Chessboard" class to store all the squares and set them up.
3. Make a "Knight" class to move around the chessboard (and check if moves are valid).
4. Finally, create a driver class that searches and stores how to move the Knights around.

Sample Square class:

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;}
}

Sample Knight class:

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;
        }
    }
}

Fondea