Research:

Our thesis is that it will be possible for depthfirst, but will also probably take a long time to solve. We don't think that it's possible with breadthfirst because of memory limitations.

To answer our research question we plan to make some calculations about the search trees in advance. And if thought possible try to write a programme in java which will solve knight's tour using the search technique(s).

Some calculations:

To predict the behaviour of our search-tree we are going to investigate the branching factor and search complexity. As can be seen in the picture on the right from a green square 8 knight moves can be made. The colours stand for the number of possible moves from that spot. Using the numbers below the picture we come at an average of 5.25 (336/64) as the branching factor.

Green: 8 moves ( 16 squares), Yellow: 6 moves (16 squares) Orange: 4 moves (20 squares), Red: 3 moves (8 squares) Blue: 2 moves (4 squares)

This means that breadth-first will have an average of 5.25^64=1.23*10^46 paths at the end of it's search-tree. This ofcourse does not take into account the fact that a board-space can't be occupied twice. This will ofcourse lower the average branching-factor, but even at a branching factor of 2, this will lead to 2^64=18446744073709551616 paths. Because of this enormous number a breadth-first implementation in java for this problem will be impossible, because of memory limitations.

This enormous number of possible paths ofcourse will also be a problem for depth-first search, because it can take a very long time to find a solution. (This is indeed the case as later on can be seen). But because it is possible we have tried to implement a depth-first search for this problem. Because of the expected length of the calculation time we thought we could give the depth first search a certain (correct) beginpath, and let it search from there on. On the internet we found the following heuristic to find a path:

• Check all available fields from the current position. For each one, find the number of open fields that could move to that field.
• Move to the field that had the least open fields that could jump to it.

We have implemented this heuristic as well to generate a beginpath. (The description is also the pseudocode)

The pseudocode we have implemented for the depth-first-search is:

1) Take the last node in the path and call it N,
2) Try to find a possible follow-up node from N,
-if found, call it M, mark M as visited, add M to the path and go back to step 1
-if not found, delete node N from the path, and go back to step 1

A node is a possible follow-up node when:
-it is not already in the path
-it hasn't already been visited (by depth-first search from node N)?
-it's a legal knight move