Knights tour problem without recursion in C++

8x8 board output that looks like:

 63, 20, 3, 24, 59, 36, 5, 26 2, 23, 64, 37, 4, 25, 58, 35 19, 62, 21, 50, 55, 60, 27, 6 22, 1, 54, 61, 38, 45, 34, 57 53, 18, 49, 44, 51, 56, 7, 28 12, 15, 52, 39, 46, 31, 42, 33 17, 48, 13, 10, 43, 40, 29, 8 14, 11, 16, 47, 30, 9, 32, 41 

The board state at each instant is an 88 array of integers all of whose elements are initially set at 1. As you move to a square, you replace the corresponding array element by the sequence number of the move made (such as 1 for the square visited after the first move, 2 for the second move etc.). At each instant the board state with any other necessary information is pushed on to the stack. This is to recover from the case when the knight is trapped somewhere, with no unvisited square to move to, without finding the complete solution. In such a case, you back-track along the traversed path by popping the states from the stack, until you find a square from which you can make a valid move. While back-tracking you should also unmark the the squares (i.e., put 1 at the corresponding elements of the current board state) so that you can visit those squares again.

If, at a particular instant, the knights position on the board is given by (i,j), there may be at most eight possible moves for the knight which will move it to one of the squares (i 2,j + 1),(i1,j +2),(i+1,j +2),(i+2,j +1),(i+2,j 1),(i+1,j 2),(i1,j 2),(i2,j 1).

The summary of the project:

I) Implementation of a singly linked list (with associated operations) to store the user inputs concerning the initial positions of the knight.

(ii) Solving the knights tour problem for each initial position using a stack, backtracking, and using Warnsdoffs heuristic for the first 32 moves. (Then backtracking for the rest)

The two components should work together. All the messages, and/or the transcript of a session demonstrating the successful operation of the complete program, should be saved in the output file.

The program should start with:

The project also requires the use of a singly linked list to store a number of choices of initial conditions for the knight. Before solving the problem for any initial condition, the program should prompt the user incrementally to enter the initial conditions, but should not ask for the number of initial positions that the user wishes to enter. At the end of this data entry mode, the program should display all the positions entered. It should then further prompt to see if the user wants to add, delete, or modify the list of initial positions. For each initial position, the program would then solve the knights tour problem. The result in each case would be an 8 8 matrix holding the order of the visits. Store all the results in an array of these matrices.