Robson » Little Red Book » Knight's Tour

Chapter 9 - Question 6

Another chess board problem is:

Given an initial square on the board, find a sequence of knight's moves that, starting from the given square, will visit each square on the board once and once only.

Solution 1

Working out the solution would require a lot of processing on the server, so I'm only allowing a cut down version to be run here.

This version moves around the board until it can't move. The full solution can be seen below.

<?
   // knights moves
   
   // . 0 . 1 .
   // 7 . . . 2
   // . . X . .
   // 6 . . . 3
   // . 5 . 4 .
   
   // define all possible moves
   // horizontal, vertical    
   $directions = array(
                   array(-1, -2), // 0
                   array(+1, -2), // 1
                   array(+2, -1), // 2
                   array(+2, +1), // 3
                   array(+1, +2), // 4
                   array(-1, +2), // 5
                   array(-2, +1), // 6
                   array(-2, -1)  // 7
                       );
                   
   // the size of the board
   $size = 8;
   
   // create a three-dimensional array of squares
   // each contains 0 to begin
   for ($n = 0; $n < $size; $n++)
       $squares[$n] = array_fill(0, $size, '-');
       
   // create a simple array of values from 1 to the number of directions
   // the directions are always the same, so no need for anything more complex
   $moves = array(0, 1, 2, 3, 4, 5, 6, 7);
   
   // start at a random square
   $current_x = mt_rand(0, $size-1);
   $current_y = mt_rand(0, $size-1);
   
   // start at 1
   $counter = 1;
   // all squares must be used, so the starting square is reasonably irrelevant
   $squares[$current_x][$current_y] = $counter;
   
   // only loop while a possible move can be done
   while (!$no_more_moves)
   {
       // shuffle the possible directions so that they are checked in a random order
       shuffle($moves);
       // reset the moves variable from the last loop
       $moved = FALSE;
       // increment the counter
       $counter++;
       // loop through each of the possible moves
       foreach ($moves as $move)
       {
           // work out where that move would be
           $possible_x = $current_x - $directions[$move][0];
           $possible_y = $current_y - $directions[$move][1];
           // check if this is inside the board
           if ($possible_x >= 0 && $possible_x < $size &&
               $possible_y >= 0 && $possible_y < $size)
           {
               // check if that square wasn't used already
               if (!is_numeric($squares[$possible_x][$possible_y]))
               {
                   // if we've got here it's a valid move
                   // set that square to the current counter
                   $squares[$possible_x][$possible_y] = $counter;
                   // a valid move was completed, so save that
                   $moved = TRUE;
                   // set the current position to the new position
                   $current_x = $possible_x;
                   $current_y = $possible_y;
                   // no need to check anymore numbers, so break out of this foreach loop
                   break;
               }
           }
       }    
       // all possible moves have been attempted by this point
       // so check if no move was possible
       if (!$moved)
           // if so, set this variable to true which will stop the loop
           $no_more_moves = TRUE;
   }
   
   // output in monospace
   echo '<pre>';
   // this could be done in two lines with imploding, but i want to output aligned
   // loop through each vertical square along the left side
   foreach ($squares as $vert_square)
   {
       // loop through each square on that row
       foreach ($vert_square as $horz_square)
       {
           // output the value contained within it
           echo $horz_square . ' ';
           // if this is a short number
           if (strlen($horz_square) == 1)
               // add a space so it mathes up
               echo ' ';
       }
       // add a new line for the next row
       echo '<br/>';
   }
   // return output to variable width
   echo '</pre>';
   
?>

Which produces:

-  -  -  22 7  26 31 24 
- - - 27 20 23 8 -
- 18 21 6 9 28 25 30
- 5 10 19 16 - - -
- - 17 4 11 - 29 -
- - 12 15 - - - -
- 14 3 - - - 1 -
- - - 13 2 - - -

Solution 2

This is the full solution. However, due to the amount of time it would take to generate a valid sequence, I haven't fully tested it and it would be irresponsible of me to allow this script to be run on the server. Check my comments at the top of the script for more information. I could possibly optimize my code in the future to decrease the amount of time it would take.

<?
   // the first attempts at creating sequences:
   
   // 54:       5 attempts /   0.0066 seconds
   // 55:      38 attempts /   0.0388 seconds
   // 56:      62 attempts /   0.0641 seconds
   // 57:     178 attempts /   0.1772 seconds
   // 58:   1,586 attempts /   1.6147 seconds
   // 59:   4,195 attempts /   4.2062 seconds
   // 60:  11,941 attempts /  11.9921 seconds
   // 61:  18,530 attempts /  18.3615 seconds
   // 62: 140,680 attempts / 140.7349 seconds
   // 63: gave up after half an hour
   // 64: not attempted
 
   // as you can see, each attempt takes about 0.001 seconds
   // so one thousand combinations can be checked per second
 
   // knights moves
   
   // . 0 . 1 .
   // 7 . . . 2
   // . . X . .
   // 6 . . . 3
   // . 5 . 4 .
   
   // this is going to take a long time, so disable time limits
   set_time_limit(0);
   
   // start logging the time
   $time_before = explode(' ', microtime());
   
   // define all possible moves
   // horizontal, vertical    
   $directions = array(
                   array(-1, -2), // 0
                   array(+1, -2), // 1
                   array(+2, -1), // 2
                   array(+2, +1), // 3
                   array(+1, +2), // 4
                   array(-1, +2), // 5
                   array(-2, +1), // 6
                   array(-2, -1)  // 7
                       );
                   
   // the size of the board
   $size = 8;
 
   // create a simple array of values from 1 to the number of directions
   // the directions are always the same, so no need for anything more complex
   $moves = array(0, 1, 2, 3, 4, 5, 6, 7);
   
   // set the number of attempts to 0 so php knows it's a number
   $attempts = 0;
 
   while (!$large_board)
   {
       // kill these variables so they don't conflict later
       unset($squares);
       unset($no_more_moves);
       
       // create a three-dimensional array of squares
       // each contains 0 to begin
       for ($n = 0; $n < $size; $n++)
           $squares[$n] = array_fill(0, $size, 0);
       
       // start at a random square
       $current_x = mt_rand(0, $size-1);
       $current_y = mt_rand(0, $size-1);
       
       // start at 1
       $counter = 1;
       // all squares must be used, so the starting square is reasonably irrelevant
       $squares[$current_x][$current_y] = $counter;
       
       // only loop while a possible move can be done
       while (!$no_more_moves)
       {
           // shuffle the possible directions so that they are checked in a random order
           shuffle($moves);
           // reset the moves variable from the last loop
           $moved = FALSE;
           // increment the counter
           $counter++;
           // loop through each of the possible moves
           foreach ($moves as $move)
           {
               // work out where that move would be
               $possible_x = $current_x - $directions[$move][0];
               $possible_y = $current_y - $directions[$move][1];
               // check if this is inside the board
               if ($possible_x >= 0 && $possible_x < $size &&
                   $possible_y >= 0 && $possible_y < $size)
               {
                   // check if that square wasn't used already
                   if (!$squares[$possible_x][$possible_y])
                   {
                       // if we've got here it's a valid move
                       // set that square to the current counter
                       $squares[$possible_x][$possible_y] = $counter;
                       // a valid move was completed, so save that
                       $moved = TRUE;
                       // set the current position to the new position
                       $current_x = $possible_x;
                       $current_y = $possible_y;
                       // no need to check anymore numbers, so break out of this foreach loop
                       break;
                   }
               }
           }    
           // all possible moves have been attempted by this point
           // so check if no move was possible
           if (!$moved)
               // if so, set this variable to true which will stop the loop
               $no_more_moves = TRUE;
       }
       // check if it's the required size
       // this is where you can specify to make less than the required amount
       // it's set on 58 so it'll generate a solution quickly, but you can increase that
       // up to the number of squares on the board
       $large_board = $counter > 58;
       // increment the number of attempts so far
       $attempts++;
   }
   
   // output in monospace
   echo '<pre>';
   // this could be done in two lines with imploding, but i want to output aligned
   // loop through each vertical square along the left side
   foreach ($squares as $vert_square)
   {
       // loop through each square on that row
       foreach ($vert_square as $horz_square)
       {
           // output the value contained within it
           echo $horz_square . ' ';
           // if this is a short number
           if (strlen($horz_square) == 1)
               // add a space so it mathes up
               echo ' ';
       }
       // add a new line for the next row
       echo '<br/>';
   }
   // return output to variable width
   echo '</pre>';
   
   // get the current time
   $time_after = explode(' ', microtime());
   // work out how long it took to run everything
   $difference = ($time_after[1] - $time_before[1]) + ($time_after[0] - $time_before[0]);
 
   
   echo 'Attempts: ' . number_format($attempts) . '<br/>';
   echo 'Duration: ' . round($difference, 4) . ' seconds';
   
?>

Log

© 2004-17 robson | cc unless stated