How to debug a long while loop

[nbezzala]

Dear Monks,

I am trying to write a program to solve a puzzle I came across.

There is one horse on a chessboard, and it can move according to the rules of chess. It needs to cover all the 64 squares of the board in 63 moves. So, it can not go back to a square which it has already been in.

I am attaching what I have so far, and it works for the first 42 moves, but it fails for the 43rd move.

Can someone please tell me what is the best way to debug such a program?

Also, is this the kind of solution you would have thought of or is there a better solution?
Should I rather have created objects and used them?

Thanks,
Nitish

 #! /usr/bin/perl

 use strict;
 use warnings;

 use Data::Dumper;


 my $puzzle_board = create_board();
 solve ($puzzle_board);
 print_board ($puzzle_board);


 sub solve {
     my $board = shift @_;

     my $move = 1;
     my ($x, $y) = (0, 1);

# Change this number to solve more or less of the puzzle
     while ( $move < 44 ) {

         my ($newx, $newy) = calculate_move($board, $x, $y);
         print "$move: $x,$y->$newx,$newy\t";

         if ( verify_move($board, $newx, $newy) == 1 ) {
             forward($board, $x, $y, $newx, $newy);
         } elsif ( $board->[$x][$y]{trial} < 7 ) {
             $board->[$x][$y]{trial}++;
             next;
         } else {
             back($board, $x, $y, $newx, $newy);
             $x = $board->[$newx][$newy]{oldx};
             $y = $board->[$newx][$newy]{oldy};
             $move--;
             next;
         }
         ($x, $y) = ($newx, $newy);
         $move++;
     }
 }


 sub forward {

     my ($board, $x, $y, $newx, $newy) = @_;

     $board->[$newx][$newy]->{visited} = $board->[$x][$y]->{visited} +
+ 1;
     $board->[$newx][$newy]->{oldx} = $x;
     $board->[$newx][$newy]->{oldy} = $y;
 }

 sub back {

     my ($board, $x, $y, $newx, $newy) = @_;

     $board->[$newx][$newy]{trial} = 0;
     $board->[$newx][$newy]{visited} = 0;
 }

 # Assumes that it is passed valid x and y values in the board.
 sub calculate_move {

     my ($board, $x, $y) = @_;
     my ($newx, $newy) = 0;

     if ($board->[$x][$y]{trial} == 0) {
         $newx = $x + 1;
         $newy = $y + 2;
     }
     if ($board->[$x][$y]{trial} == 1) {
         $newx = $x - 1;
         $newy = $y + 2;
     }
     if ($board->[$x][$y]{trial} == 2) {
         $newx = $x + 1;
         $newy = $y - 2;
     }
     if ($board->[$x][$y]{trial} == 3) {
         $newx = $x - 1;
         $newy = $y - 2;
     }
     if ($board->[$x][$y]{trial} == 4) {
         $newx = $x + 2;
         $newy = $y + 1;
     }
     if ($board->[$x][$y]{trial} == 5) {
         $newx = $x - 2;
         $newy = $y + 1;
     }
     if ($board->[$x][$y]{trial} == 6) {
         $newx = $x + 2;
         $newy = $y - 1;
     }
     if ($board->[$x][$y]{trial} == 7) {
         $newx = $x - 2;
         $newy = $y - 1;
     }

     return ($newx, $newy);
 }

 sub verify_move {

     my ($board, $x, $y) = @_;

     if ($x > 7 || $x < 0 || $y > 7 || $y < 0) {
         return 0;
     }

     if ($board->[$x][$y]{visited} > 0) {
         return 0;
     }

     return 1;
 }

 sub create_board {
     my @board;
     my ($i, $j);


     for ( $i = 0; $i < 8; $i++ ) {
         for ( $j = 0; $j < 8; $j++ ) {
                 $board[$i][$j] = {
                 x => $i,
                 y => $j,
                 visited => 0,
                 trial => 0,
                 oldx => 0,
                 oldy => 0
             }
         }
     }


     $board[0][1] = {
         x => 0,
         y => 1,
         visited => 1,
         trial => 0
     };

     return \@board;
 }

 sub print_board {
     my $board_ref = shift @_;
     my ($i, $j);

     print Dumper  $board_ref;
     print "\nThe Chess Board\n";
     for ($i = 7; $i >= 0; $i--) {
         for ($j = 0; $j < 8; $j++) {
             printf ("%02d   ", $board_ref->[$i][$j]{visited}  );
         }
         print "\n\n";
     }
 }

[BrowserUk]

On my system, your (unmodified) code happily completes up to step 61--which is intriguing. It fails attempting to complete step 62. When it fails, it produces a bunch of "Uninitialised value errors":

c:\test>615969 62
57: Use of uninitialized value in array element at c:\test\615969.pl l
+ine 66.
Use of uninitialized value in array element at c:\test\615969.pl line 
+66.
Use of uninitialized value in array element at c:\test\615969.pl line 
+70.
Use of uninitialized value in array element at c:\test\615969.pl line 
+70.
Use of uninitialized value in array element at c:\test\615969.pl line 
+74.
Use of uninitialized value in array element at c:\test\615969.pl line 
+74.
Use of uninitialized value in array element at c:\test\615969.pl line 
+78.
Use of uninitialized value in array element at c:\test\615969.pl line 
+78.
Use of uninitialized value in array element at c:\test\615969.pl line 
+82.
Use of uninitialized value in array element at c:\test\615969.pl line 
+82.
Use of uninitialized value in array element at c:\test\615969.pl line 
+86.
Use of uninitialized value in array element at c:\test\615969.pl line 
+86.
Use of uninitialized value in array element at c:\test\615969.pl line 
+90.
Use of uninitialized value in array element at c:\test\615969.pl line 
+90.
Use of uninitialized value in array element at c:\test\615969.pl line 
+94.
Use of uninitialized value in array element at c:\test\615969.pl line 
+94.
Use of uninitialized value in subtraction (-) at c:\test\615969.pl lin
+e 95.
Use of uninitialized value in subtraction (-) at c:\test\615969.pl lin
+e 96.
Use of uninitialized value in concatenation (.) or string at c:\test\6
+15969.pl line 23.
Use of uninitialized value in concatenation (.) or string at c:\test\6
+15969.pl line 23.
Use of uninitialized value in array element at c:\test\615969.pl line 
+25.
Use of uninitialized value in array element at c:\test\615969.pl line 
+25.
60: 0,0->2,1

Note: For the above run I made two changes.

1. I made the step counter a command line argument:

   my $steps = shift( @ARGV ) || 64;
   
   my $puzzle_board = create_board();
   solve ($puzzle_board);
   print_board ($puzzle_board);
   ...
   # Change this number to solve more or less of the puzzle
       while ( $move < $steps ) {
   

2. I changed the trace statement so that it overwrites on the same line:

           my ($newx, $newy) = calculate_move($board, $x, $y);
           printf "\r$move: $x,$y->$newx,$newy\t";
   

The errors seem to indicate that something goes wrong during backtracking? Sorry I don't have any better explanation than that so far.

The really mysterious things is why would it get further on my machine than yours? It consumes very little memory so that isn't the problem. Maybe Perl version differences?

I'm using

c:\test>perl -v

This is perl, v5.8.6 built for MSWin32-x86-multi-thread
(with 3 registered patches, see perl -V for more detail)

Copyright 1987-2004, Larry Wall

Binary build 811 provided by ActiveState Corp. http://www.ActiveState.
+com
ActiveState is a division of Sophos.
Built Dec 13 2004 09:52:01

Maybe if you get a few other reports they might correlate to a clue as to what is happening to make the boundary of error move.

HTH

---

Update:

Added the following trace into your back() sub:

sub back {
    print "\n*** BACK ***\n";
...

(I also disabled the Dumper output for conciseness) and when I run 61 steps I get the following output:

Read more... (1482 Bytes)

The interesting thing is that the first time it backtracks is at step 43, the very place where it is failing for you. I'd suggest you take a close look at the logic there and see if you can spot anything amiss.

[liverpole]

Hi nbezzala,

It sounded like a fun challenge, so I tried my hand at a recursive version of it, which follows:

Read more... (7 kB)

Update:  Although I was unaware of this problem before, I did know of the "Eight Queens" problem which roboticus referred to.  I wrote Solving the Eight Queens problem a while ago to solve it, specifically, and "Attack" -- Find Solutions for N Non-Attacking Chess Pieces to solve a more general case of N pieces which are not allowed to attack one another.

[roboticus]

nbezalla:

I don't want to solve a homework problem for you, especially as you've made such a great start at it. Here's a hint that may help you out:

Unless you're specifically avoiding it, recursion would be your best bet here. You're doing a lot of work in your code that recursion would "automatically" take care of for you. You're making a complex data structure (board) to track a handful of state variables that you would get "free" using recursion.

For example, your board array is rather complicated. You could use local variables to store most of your state information for each move. Something like:

sub solve {
   my $move = shift;
   ... other code ...
   solve($move+1,...);
}

Here, rather than putting the $move variable into your board structure, you're letting perl keep track of them for you on the stack. As you call solve, you get a new copy of $move, and when you return, you get the previous value back.

Using local variables and recursion, you should be able to use an 8x8 array of integers to track which squares have been used, the rest being local variables.

If you need another hint or two, let me know.!

(Note: Just as an example of how using recursion can simplify things a bit, I cobbled together a quickie solution that's a little less than half the size of yours.)

...roboticus

[roboticus]

nbezalla:

I recalled another amusing chess puzzle--specifically the "queens problem". It's another one that's easily solved with recursion. It might be too much of a hint, so I've put spoiler tags on it (below) so you don't see the solution to it if you don't want to. Anyway, the queens problem (on the offhand chance that you're unfamiliar with it) is basically to place eight queens on a chessboard such that none can attack another.

My solution is:

<Reveal this spoiler or all in this thread>

...roboticus

[roboticus]

nbezalla:

Okay ... now that I've answered your second question, I guess I should address the first one.

Generally, when I debug a long-running while loop, I'll use one (or more) of the following techniques:

• If each iteration is relatively quick and simple, I'll first use the perl debugger to step through the first few iterations to get a feel for things.
• If there are plenty of alternate execution paths, I'll set a breakpoint in *all* of them, then start the program. As I reach each new breakpoint, I'll step through to the end of the loop, looking for something odd. When I hit the end of the loop, if I found nothing interesting in that path, I'll remove the breakpoint that I tripped and continue execution. After a while, you'll usually reach the point where the fault occurs relatively quickly.
• Sometimes, I'll just pepper the loop with print statements showing the values of variables I'm concerned about, to see what's happening.
• If the fault seems to occur with the same data each time, then I'll use the debugger and set the variables up to cause the fault immediately, then step through the code and see where my bug is.

I hope this is useful...

...roboticus