C++ Linked list and back tracking

Objective:

Study data manipulation in C++ using linked lists.

Preliminary task:

(Malik, Ch. 6, programming exercise 19) (Knight’s Tour) This chapter described the backtracking algorithm and how to use recursion to implement it. Another well-known chessboard problem that can be solved using the backtracking algorithm is a knight’s tour. Given an initial board position, determine a sequence of moves by a knight that visits every square of the chessboard exactly once. For example, for a 5 x 5 and 6 x 6 square board, the sequence of moves are shown in Figure 6-18:

A knight moves by jumping two positions either vertically or horizontally and one position in the perpendicular direction. Write a recursive backtracking program that takes as input an initial board position and determines a sequence of moves by a knight that visits each square of the board exactly once.