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:

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

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-20 robson | cc unless stated