Knight's Tour in Java (recursive), using Graph and DFS

Question

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

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

I thought it might be too much code (and maybe not relevant enough) to paste these entire classes in this post, so I display them here:

Graph.java

DepthFirstSearch.java

Graph.java uses Bag.java:

Bag.java

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 following attributes are used in the CalculatePath method, which should calculate the amount of possible tours a knight could take from a specific square to visit each square exactly once (should take a minute or two to solve it).

The possible Knight's steps are defined (in the main class) like this (using edges of a Graph, G):

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

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

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

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, 16);

G.addEdge(6, 15);
G.addEdge(6, 17);
G.addEdge(6, 3);
G.addEdge(6, 13);

G.addEdge(7, 0);
G.addEdge(7, 4);
G.addEdge(7, 10);
G.addEdge(7, 14);
G.addEdge(7, 16);
G.addEdge(7, 18);

G.addEdge(8, 1);
G.addEdge(8, 17);
G.addEdge(8, 19);
G.addEdge(8, 11);

G.addEdge(9, 2);
G.addEdge(9, 12);
G.addEdge(9, 18);

G.addEdge(10, 1);
G.addEdge(10, 21);
G.addEdge(10, 7);
G.addEdge(10, 17);

G.addEdge(11, 0);
G.addEdge(11, 2);
G.addEdge(11, 20);
G.addEdge(11, 22);
G.addEdge(11, 8);
G.addEdge(11, 18);

G.addEdge(12, 1);
G.addEdge(12, 3);
G.addEdge(12, 21);
G.addEdge(12, 23);
G.addEdge(12, 5);
G.addEdge(12, 9);
G.addEdge(12, 15);
G.addEdge(12, 19);

G.addEdge(13, 2);
G.addEdge(13, 4);
G.addEdge(13, 22);
G.addEdge(13, 24);
G.addEdge(13, 6);
G.addEdge(13, 16);

G.addEdge(14, 3);
G.addEdge(14, 23);
G.addEdge(14, 7);
G.addEdge(14, 17);

G.addEdge(15, 6);
G.addEdge(15, 12);
G.addEdge(15, 22);

G.addEdge(16, 5);
G.addEdge(16, 7);
G.addEdge(16, 13);
G.addEdge(16, 23);

G.addEdge(17, 6);
G.addEdge(17, 8);
G.addEdge(17, 10);
G.addEdge(17, 14);
G.addEdge(17, 20);
G.addEdge(17, 24);

G.addEdge(18, 7);
G.addEdge(18, 9);
G.addEdge(18, 11);
G.addEdge(18, 21);

G.addEdge(19, 8);
G.addEdge(19, 12);
G.addEdge(19, 22);

G.addEdge(20, 11);
G.addEdge(20, 17);

G.addEdge(21, 10);
G.addEdge(21, 12);
G.addEdge(21, 18);

G.addEdge(22, 11);
G.addEdge(22, 13);
G.addEdge(22, 15);
G.addEdge(22, 19);

G.addEdge(23, 12);
G.addEdge(23, 14);
G.addEdge(23, 16);

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

int currentSquare = 20;
calculatePath(currentSquare);
System.out.println("From square " + currentSquare + " there are " + tours + " possible tours.");

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

  private static void calculatePath(int currentSquare) {
        boolean foundChoice = false;
        for (int point : G.adj(currentSquare)) {

            if (dfs.marked(currentSquare)) {
                foundChoice = true;
//              dfs.unmark(currentSquare);
                calculatePath(point);
            }
        }
        if (!foundChoice) {
            tours++;
            dfs.unmark(currentSquare);
        }
        System.out.println(currentSquare + " - tours: " + tours);
    }

For example, if I try to call this recursive function by calculatePath(20), it should return all possible tours (tours) from that square, using every square on the field.

Unmarked squares are squares that have already been reached and shouldn't be visitable anymore in the same tour.

Now, the problem is that I'm not able to let CalculatePath skip the already visited squares (the output shows it goes from 20 to 17 and from 20 to 11, and then stops the recursive method).

Also, the method doesn't calculate multiple tours, yet. I want to calculate one path correctly first and eventually calculate all possible tours.

All code I'm using is privided in this post - included the classes in the links above.

OldCurmudgeon OldCurmudgeon · Accepted Answer · 2016-01-13T13:51:12

There are still :) a number of issues with this code but it looks like you are making progress.

Your method DepthFirstSearch.marked seems wrong to me. I would have thought it should return true if it successfully changed the mark from false to true. Here you are only returning the value of marked[w].

Your DepthFirstSearch constructor seems to be attempting to mark all of the adjacent (and all of their adjacent points). This seems strange - how do you expect this to work? The normal DFS mechanism for avoiding loops is to leave a mark at each location you have touched as you recurse and remoive the mark as the recursion completes. Here you seem to be marking all squares at the start and then unmarking them when you've completed one round of all adjacents without finding a marked one.

Knight's Tour in Java (recursive), using Graph and DFS

1 Answers