The Knight’s Tour is a challenge to move a knight from the board game of Chess around the
board landing on all squares but reaching each square only once. Knights move in an ‘L’
shape (of two squares in one direction and one square at right angles to it or vice-versa).
Your task is to implement the Knight’s Tour problem in C so that the computer will find the
solution for you.
The computer will select moves by creating a game tree. A game tree consists of all the
possible states of the game and in this assignment the computer determines any possible
solution to be the best one. Each node of the game tree has children that indicate the states of
the game that follow from the state of the parent for each possible move, i.e. each node in the
tree possesses at most 8 children of any node but as more moves are made, or if a smaller
board is used, then there will become less.
This assignment uses many data structures (trees, linked-lists, stacks, and queues) to solve the
puzzle. You should create and traverse the game tree using a stack and queue as intermediate
data structures. When a solution is found the solution should be displayed. The program will
be text only.
A Visual Studio project folder is available for download from MyLO. The project contains
many header (.h) and source (.c) files. All required files are present. You should not add
any further files or change any code which is provided (other than the settings in
assig_three121.h). You don’t have to use Visual Studio if you don’t wish to; any
editing and compiling environment is fine.
You need to complete the functions within the program files which have been declared but
for which the function bodies are missing and to update the header comments of the source
files that you complete with your names, student IDs and ratio of effort.
Please note: there is not enough memory granted by the operating system to the running
program to solve the depth-first problem on an 8×8 board or larger, or the breadth-first
problem on a 6×6 board or larger. A sample run of the game is shown below on a 4×4 board.
Please also note that there is no solution available for a tour of length 16 on a 4×4 board.