Task — Adventure of knight

A knight is restricted to move on an n×n chessboard. The knight is denoted by N and its way of movement is as defined in chess and as follows.

The knight may move two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an L).

Write a script to find the path such that Knight can capture all treasures. The Knight starts from the top-left square.

Examples

Example 1
      a b c d e f g h
    8 N * * * * * * * 8
    7 * * * * * * * * 7
    6 * * * * x * * * 6
    5 * * * * * * * * 5
    4 * * x * * * * * 4
    3 * x * * * * * * 3
    2 x x * * * * * * 2
    1 * x * * * * * * 1
      a b c d e f g h
* represents an empty square. x represents a square
with treasure.

Analysis

This is a form of the travelling salesman problem which has been known and investigated since the mid-1800s. Solutions have been found which can find the shortest path, but these are complex and lengthy.

My solution finds a possible path, and has an element of randomness built in such that it will find different paths on different invocations.

For the 8x8 board in the example the worst case is that all 63 cells will be visited, but in running it several times I did achieve a low of 24 steps:

Input:
o * * * * * * *
* * * * * * * *
* * * * x * * *
* * * * * * * *
* * x * * * * *
* x * * * * * *
x x * * * * * *
* x * * * * * *

Output: found all 6 treasures: (1, 6), (2, 4), (1, 5), 
   (1, 7), (4, 2), (0, 6)
steps: 24

final board:
o * * * * * * *
* * o * * * * *
* o o * + * * *
* o * o o * o *
o o + o o o * *
o + o * * * * o
+ + * o o * * *
* + * * * * o *
o = visited, * = unvisited, + = treasure found, 
    x = treasure not found

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2021-06-21
use utf8;     # Week 118 - task 2 - Adventure of knight
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

my ($treasure, $num_treasures, $found_at, $steps, $edge, @moves);

adventure_of_knight(
'o * * * * * * *
* * * * * * * *
* * * * x * * *
* * * * * * * *
* * x * * * * *
* x * * * * * *
x x * * * * * *
* x * * * * * *');

adventure_of_knight(
'o * * * * * 
* * * * * *
* x x x x *
* * * * * *
* * * * * *
* * * * * x');

sub adventure_of_knight {
    
    my (@a, @b, $max, $x, $y, $a);
    
    # initialise
    @a = split(/\s+/, $_[0]);
    $max = scalar @a;
    $edge = sqrt($max);
    if ($edge != int($edge)) {
        say qq[board is not square ($max, $edge)];
        return;
    }   
    
    $x = $y = $num_treasures = 0;
    for $a (@a) {
        if ($x >= $edge) {
            $x = 0; $y ++;
        }
        $b->[$x]->[$y] = $a;
        $x ++;
        $num_treasures ++ if $a eq 'x';
    }
    $treasure = $steps = 0;
    $found_at = '';

    # possible moves
    @moves = ([1, 2], [-2, -1], [1, -2], [-2, 1], [2, 1], 
        [2, -1], [-1, -2], [-1, 2]); 
    
    say qq[\nInput:];
    for $y (0 .. $edge - 1) {
        for $x (0 .. $edge - 1) {
            print $b->[$x]->[$y] . ' ';
        }
        say '';
    }
    $steps = 0;
    
    # make first move - and recurse for more
    make_move([0, 0], '');
    
    # show final board
    for $y (0 .. $edge - 1) {
        for $x (0 .. $edge - 1) {
            print $b->[$x]->[$y] . ' ';
        }
        say '';
    }
    say qq[o = visited, * = unvisited, + = treasure found, x = treasure not found];
}

sub make_move {
    
    my ($from, $m, $x1, $y1, $x2, $y2);
    
    $from = $_[0];
    ($x1, $y1) = @$from;
    
    # loop over possible next moves
    $steps ++;
    randomise_moves();
    for $m (0 .. 7) {
        
        # check for valid move
        ($x2, $y2) = ($x1 + $moves[$m]->[0], $y1 + $moves[$m]->[1]);
        next if $x2 < 0 or $x2 >= $edge or $y2 < 0 or $y2 >= $edge;
        next if $b->[$x2]->[$y2] =~ m|[o+]|;
                
        # treasure here
        if ($b->[$x2]->[$y2] eq 'x') {
            $b->[$x2]->[$y2] = '+';
            $treasure ++;
            $found_at .= qq[($x2, $y2), ];
            
            # found all the treasure
            if ($treasure == $num_treasures) {
                say qq[\nOutput: found all $num_treasures treasures: ] . 
                    substr($found_at, 0, -2);
                say qq[steps: $steps ]; 
                return 1;
            }
        }

        # mark cell as visited and recurse
        $b->[$x2]->[$y2] = 'o' if $b->[$x2]->[$y2] eq '*';
        return 1 if make_move([$x2, $y2]);
    }
    return 0;
}
    
sub randomise_moves {
    
    # randomises the order in which the moves are taken
    
    my ($i, $j, $h);
    
    # swap pairs 30 times
    for (1 .. 30) {
        $i = int(rand($edge - 1));
        $j = int(rand($edge - 1));
        $h = $moves[$i];
        $moves[$i] = $moves[$j];
        $moves[$j] = $h;
    }
}

last updated 2026-03-18 — 61 lines of code

Output

Input:
o * * * * * * * 
* * * * * * * * 
* * * * x * * * 
* * * * * * * * 
* * x * * * * * 
* x * * * * * * 
x x * * * * * * 
* x * * * * * * 

Output: found all 6 treasures: (1, 5), (0, 6), (1, 6), 
   (4, 2), (2, 4), (1, 7)
steps: 52 

o * o o o o * * 
o o o o * o o o 
o o o o + o o * 
o * o o o o o o 
o o + o * o o o 
* + * o o o o o 
+ + o o o o o o 
* + o * o o o o 
o = visited, * = unvisited, + = treasure found,
   x = treasure not found

Input:
o * * * * * 
* * * * * * 
* x x x x * 
* * * * * * 
* * * * * * 
* * * * * x 

Output: found all 5 treasures: (1, 2), (3, 2), (4, 2),
   (2, 2), (5, 5)
steps: 35 
o o o o o o 
o o o o o o 
o + + + + o 
o o o o o o 
o o o o o o 
o o o o o + 
o = visited, * = unvisited, + = treasure found,
   x = treasure not found