Calculate possible knight moves on a 5x5 field in Java, using DFS

I'm trying to calculate all possible knight moves on a 5x5 field.

To do this, I'm trying to use DFS (Depth First Search) and a Graph class.

The field would look something like this (using an id for each field):

0  1  2  3  4
5  6  7  8  9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24

The possible steps are defined like this (using edges of a Graph, G):

G.addEdge(0, 1); G.addEdge(0, 5);

G.addEdge(1, 2); G.addEdge(1, 6);

G.addEdge(2, 3); G.addEdge(2, 7);

G.addEdge(3, 4); G.addEdge(3, 8);

G.addEdge(4, 9);

G.addEdge(5, 6); G.addEdge(5, 10);

G.addEdge(6, 7); G.addEdge(6, 11);

G.addEdge(7, 8); G.addEdge(7, 12);

G.addEdge(8, 9); G.addEdge(8, 13);

G.addEdge(9, 14);

G.addEdge(10, 11); G.addEdge(10, 15);

G.addEdge(11, 12); G.addEdge(11, 16);

G.addEdge(12, 13); G.addEdge(12, 17);

G.addEdge(13, 14); G.addEdge(13, 18);

G.addEdge(14, 19);

G.addEdge(15, 16); G.addEdge(15, 20);

G.addEdge(16, 17); G.addEdge(16, 21);

G.addEdge(17, 18); G.addEdge(17, 22);

G.addEdge(18, 19); G.addEdge(18, 23);

G.addEdge(19, 24);

G.addEdge(20, 21);

G.addEdge(21, 22);

G.addEdge(22, 23);

G.addEdge(23, 24);

Here's what I tried to find the possible destinations:

private static void calculatePath(int currentSquare) {
        short tours = 0;

        for (int point : G.adj(currentSquare)) {
            System.out.print(currentSquare + " ");
            if (dfs.marked(currentSquare)){
                tours++;
                dfs.unmark(currentSquare);
                calculatePath(point);
            }
        }
        System.out.println(currentSquare + " - tours: " + tours);
        System.out.println("\n");
    }

For example, if I try to call this recursive function by calculatePath(20), it should return 11 and 17, since these are the only possible destinations a knight could jump to from this field (with id 20). Unmarked squares are squares that have already been reached.

The variable tours would be the amount of possible tours (2 in the case of calculatePath(20)).

Your primary issue is that you are unmarking the square before recursing.

This code:

        if (dfs.marked(currentSquare)){
            tours++;
            dfs.unmark(currentSquare);
            calculatePath(point);
        }

is saying:

1. If this square is not marked:
   1. Mark the square
   2. Increment tours
   3. Unmark the square. << This is clearly wrong.
   4. Calculate a new path from this new square.

You need to unmark only after you have tried a new path from the now marked square.

This does not solve your problem and generate knights moves but it certainly should help.

The next problem you have is that the edges you are adding to the graph are the direct neighbors to each square. If you want to check knights moves you will ned to grow the graph marking squares that are a knights move apart to be adjacent. Here's the first five for you - I'll let you finish the list.

    g.addEdge(0, 7);
    g.addEdge(0, 11);

    g.addEdge(1, 10);
    g.addEdge(1, 12);
    g.addEdge(1, 8);

    g.addEdge(2, 5);
    g.addEdge(2, 11);
    g.addEdge(2, 13);
    g.addEdge(2, 9);

    g.addEdge(3, 6);
    g.addEdge(3, 12);
    g.addEdge(3, 14);

    g.addEdge(4, 7);
    g.addEdge(4, 13);

    g.addEdge(5, 2);
    g.addEdge(5, 12);
    g.addEdge(5, 14);

Again - this may not be the solution to your problem but it is clearly one of your problems.