### Knight's tour using recursion and backtracking

Hey guys!
I am writing a program to trace a knight's tour on a chess board using recursion and backtracking. The task is to make the knight travel through all the cells of the chess board, with each cell visited at most once. I have written pretty much all of the code for the program and have tested it. The results are encouraging but I am having a few problems. Shown below is the class definition and the definition of the recursive function.

Here are my questions, they mostly address what happens after backtracking:

Qn 1. Why are the contents of the queue in `lines 36` and `45` different? In other words, why are the contents of the queue in `line 45`, when control is returning from a recursive call, different from those in `line 36`, even though both queues occur within the same recursive call? (no data was popped from the queue between the instances of the two statements!!)

Qn 2. Similarly, why is it that the value of `noOfCellsFilled` in `line 38` not the same as that on `line 52`, after the recursive call?

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960`` ``````class knightTour { public: knightTour(int = 0); bool canPlaceKnight(int&, int&, int); //function to determine if knight can be placed in a particular cell on chess board bool moveWithinBounds(int, int, int); //function to determine if knight move is within the bounds of the chess board bool traceKnightTour(int, int); //function to trace the path of the knight; all cells must be visited, each at most once void printKnightTour(); pair indexToKnightMoveConverter(int); private: int noOfCellsFilled; int boardSize; int** chessBoard; }; bool knightTour::traceKnightTour(int row, int col) { if (noOfCellsFilled < boardSize*boardSize) { if (noOfCellsFilled == 0) { chessBoard[row][col] = 1; ++noOfCellsFilled; } for (int i = 0; i < 8; i++) { if (canPlaceKnight(row, col, i)) //determines the row-column coordinates of knight's cell { static queue > q; //queue to hold row-column coordinates of the current and last cell entries q.push(make_pair(row, col)); if (q.size() > 2) //ensuring the queue size is 2 q.pop(); showQueueContents(q); //function to display the contents of the queue chessBoard[row][col] = ++noOfCellsFilled; //fill cell with corresponding number if (traceKnightTour(row, col)) //recursive call return true; chessBoard[row][col] = 0; //backtracking showQueueContents(q); //displaying queue contents after recursive call pair temp; if (!q.empty()) temp = q.front(); //since we are backtracking, retrieve row-column pair of last cell filled from the queue row = temp.first; //grab the row-column coordinates of the last cell filled col = temp.second; cout<<"noOfCellsFilled = "<
Last edited on
Does anyone have any insight into the questions I raised?
You made q static. It gets initialized once, when traceKnightTour is called for the first time, and each subsequent call to traceKnightTour modifies the original copy. Its kind of like a global variable internal to the function.

So since you call traceKnightTour between 36 and 45, as well as between 38 and 52, you end up modifying the single `queue<pair<int,int> >` that gets shared between all calls to the funtion.
You wrote:
 So since you call traceKnightTour between 36 and 45, as well as between 38 and 52, you end up modifying the single queue > that gets shared between all calls to the funtion.

I see what you are saying but my reasoning is this:

Function `traceKnightTour(int,int)` spans `lines 19` to `60`; at `line 40`, when the recursive call is encountered, a fresh function is invoked and a new set of local variables is created. The scope and duration of these variables are somewhere between `lines 19` to `60`, should the next recursive call return false. In order words, the unfinished execution of the statements following the `IF` block(recursive call) of `line 40` just resumes. That is why I expected `lines 45` and `52` to retain respectively what `lines 36` and `38` had when `line 40` returns false.

I only made `q` static in order to be able to access the row-col pair of the current recursive call during the next recursive call: the new position of the knight depends on its current position. Observe that the queue is constrained to size 2. The alternative would have been to pass the pair as a parameter to the function; but I am restricted from doing that!

Do you see my argument?
 The scope and duration of these variables are somewhere between lines 19 to 60, should the next recursive call return false.

By default, the storage duration of a local variable is automatic, and the scope of the associated name is exactly from the point of declaration to the end of the lexically innermost block containing that declaration.

Your queue has static storage duration - it is persistent global state, with block scope; the same variable is shared between every call to that function. In C++, neither scope nor storage duration (not to be confused with lifetime) can depend on the state of the program. The behavior you're describing might appear in certain dynamic languages -- Common Lisp or Perl, for example -- but not C++.

A common pattern for solving this problem is to add a private steady-state recursive function with all the parameters you need, using the publicly visible function as a thunk:
 ``12345`` ``````public: bool traceKnightTour(int row, int col) { traceKnightTour(row, col, std::queue>{}); } private: bool traceKnightTour(int, int, std::queue>) { ... } ``````
Last edited on
Topic archived. No new replies allowed.