Why are there local variable conflicts in my recursive function definition?

Question

Sorry to post a long piece of code. There are two places in here where I Print[] 'path2' when the count == 984, because for some reason, that list is getting truncated in between those two points. I can only guess that there's some kind of conflict of local variables between calls to the function tryNext. But I'm at a lost to prevent it.

This codes searches for a Knight's Journey on a chessboard, a path that makes knight moves covering the entire board and returns where it started. ks is a list of legal knight-steps. The algorithm actually starts two paths at {1, 1} and extends them both out one step at a time until one can't move anymore or until they have covered all 64 squares and are one knight-step apart.

chCorners is just a time-saver that forces the search to handle the board corners correctly and not search dead ends. For example, if the knight lands on {6, 7}, he has to go to {8, 8} and {7, 6} immediately or he will never be able to hit the {8, 8} corner.

tryNext calls itself recursively adding a step to both paths with each recursion. And, for some reason, path2 gets truncated between the two places I print it, but I can't figure out why.

ClearAll["Global`*"];

ks = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};

chCorners[kp_] :=
  Switch[kp,
    {2, 6}, {{2, 6}, {1, 8}, {3, 7}},
    {3, 7}, {{3, 7}, {1, 8}, {2, 6}},
    {6, 2}, {{6, 2}, {8, 1}, {7, 3}},
    {7, 3}, {{7, 3}, {8, 1}, {6, 2}},
    {6, 7}, {{6, 7}, {8, 8}, {7, 6}},
    {7, 6}, {{7, 6}, {8, 8}, {6, 7}},
    _, {kp}];

tryNext[p1_, p2_] := 
   Module[{path1 = p1, path2 = p2, lp, ns1, ns2, np1, np2},
     count = count + 1;
     ns1 = Table[Last[path1] + ks[[i]], {i, 1, 8}]; (*All possible next steps on path1*)
     ns2 = Table[Last[path2] + ks[[j]], {j, 1, 8}]; (*All possible next steps on path2*)
     If[count == 984, Print[Length[path2], " a ", path2]]; (*Where the bug happens*)
     Do[
       (*Check that we haven't found a solution, the next step being examined is actually on the chessboard and hasn't been visited already on either path1 or path2*)
       If[
         (! done) && (0 < ns1[[i, 1]] < 9) && (0 < ns1[[i, 2]] < 9) &&
          ! (MemberQ[path1, ns1[[i]]] || MemberQ[path2, ns1[[i]]]),
         np1 = Join[path1, chCorners[ns1[[i]]]];
         lp = Length[np1] + Length[path2] - 1;
         If[(count == 984), Print[Length[path2], " b ", path2]]; (*Where the bug happens*)
         done = (lp == 64) && MemberQ[ks, Last[np1] - Last[path2]];
         If[lp < 64,
           Do[
             If[
               (! done) && (0 < ns2[[j, 1]] < 9) && (0 < ns2[[j, 2]] < 9) && 
                ! (MemberQ[np1, ns2[[j]]] || MemberQ[path2, ns2[[j]]]),
               np2 = Join[path2, chCorners[ns2[[j]]]];
               tryNext[np1, np2]] (*Both paths okay so far but not yet connected; press on*), 
             {j, 1, 8}]]], 
       {i, 1, 8}]];

(*Starting point of program*)
done = False;
count = 0;
(* Starting two paths from lower left corned, {1,1} *)
tryNext[{{1, 1}, {2, 3}}, {{1, 1}, {3, 2}}];

Answer 1

Your debug statments are misleading. You also need to track recursive call levels. That requires some extra code. Add a statement level++; right before count = count + 1; and at the last line of tryNext[] replace with {i, 1, 8}]; level--];. Next print out the level in your two Print[] statements and finally, add level = 0; in the initialization code.

The first "a" print output is at level 28 and the two "b" print outputs are at level 22. Thus, it is no wonder that path2 is not the same. In other words, the value of count only tracks the number of times you enter the function from the "top" but doesn't track when the function returns from a previous call so that count is still the same, but level has been decremented.