# 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];`
`            \$possible_y = \$current_y - \$directions[\$move];`
`            // 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:

`-  -  44 -  32 47 42 3  -  30 23 46 43 2  33 48 22 45 -  31 -  11 4  41 29 -  21 24 5  40 1  34 20 7  18 -  10 25 12 -  17 28 9  6  39 14 35 -  8  19 -  15 26 37 -  13 -  16 27 38 -  -  -  36 `

### 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];`
`                \$possible_y = \$current_y - \$directions[\$move];`
`                // 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 - \$time_before) + (\$time_after - \$time_before);`
` `
`    `
`    echo 'Attempts: ' . number_format(\$attempts) . '<br/>';`
`    echo 'Duration: ' . round(\$difference, 4) . ' seconds';`
`    `
`?>`

## Log

• March 28, 2005 - Added solution 1 and 2.
© 2004-19 robson | cc unless stated