1
$\begingroup$

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}}];
$\endgroup$
  • $\begingroup$ That's a lot of code without any explanation! Please describe what your goal is, the approach you took, and how you implemented that approach. $\endgroup$ – MarcoB Feb 21 at 17:52
  • $\begingroup$ @MarcoB Thank you. Okay, I added explanation. I think my basic approach is right, I just have some local variable conflict. $\endgroup$ – Jerry Guern Feb 21 at 20:57
  • $\begingroup$ @Somos You maybe think it's a bug in MMa? $\endgroup$ – Jerry Guern Feb 21 at 23:14
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oooooooooh! Thank you so much for putting the time into this, because I was absolutely stumped. I modified the code to pass in and pass along a 'level', and it played out exactly as you said. $\endgroup$ – Jerry Guern Feb 22 at 1:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.