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
[download]

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 ) {
   [download]

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";
   [download]

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
[download]

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";
...
[download]

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

c:\test>615969 61
43: 0,7->-2,6
*** BACK ***
43: 6,6->4,5
*** BACK ***
56: 0,6->-2,5
*** BACK ***
56: 6,5->4,4
*** BACK ***
56: 4,4->2,3
*** BACK ***
58: 1,0->-1,-1
*** BACK ***
57: 6,5->4,4
*** BACK ***
57: 4,4->2,3
*** BACK ***
57: 2,3->0,2
*** BACK ***
57: 0,2->-2,1
*** BACK ***
57: 6,1->4,0
*** BACK ***
57: 4,0->2,-1
*** BACK ***
57: 2,7->0,6
*** BACK ***
57: 0,6->-2,5
*** BACK ***
58: 7,7->5,6
*** BACK ***
58: 5,6->3,5
*** BACK ***
58: 3,5->1,4
*** BACK ***
58: 1,4->-1,3
*** BACK ***
57: 6,1->4,0
*** BACK ***
57: 4,0->2,-1
*** BACK ***
57: 2,7->0,6
*** BACK ***
56: 1,4->-1,3
*** BACK ***
55: 6,1->4,0
*** BACK ***
55: 4,0->2,-1
*** BACK ***
56: 0,6->-2,5
*** BACK ***
57: 7,3->5,2
*** BACK ***
59: 7,2->5,1
*** BACK ***
60: 3,0->1,-1
*** BACK ***
59: 0,0->-2,-1
*** BACK ***
59: 6,7->4,6
*** BACK ***
59: 4,6->2,5
*** BACK ***
60: 1,7->0,5
The Chess Board
33   16   19   08   31   14   11   08

18   27   32   15   10   07   30   13

11   34   17   06   29   12   09   06

26   07   10   35   18   05   40   37

35   12   25   08   39   36   19   04

24   09   16   13   20   03   38   41

15   14   23   02   17   42   21   04

00   01   14   15   22   05   42   43
[download]

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.