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. It is optimised to an extent but is not guaranteed to be the shortest.

My algorithm is as follows.

• Look at the possible next moves - there can be up to 8.
• If any of them ends on treasure, take that.
• If any of them ends on an unvisited square, take that.
• Or else revisit a visited square.
• And keep going until all the treasure is found.

Try it 

#!/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, @b);

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, $max, $x, $y, $x1, $y1, $x2, $y2, $a, $treasures, 
        $m, $here, $next, $else, $pass);
    
    # initialise
    @a = split(/\s+/, $_[0]);
    $max = scalar @a;
    $edge = sqrt($max);
    if ($edge != int($edge)) {
        say qq[board is not square ($max, $edge)];
        return;
    }   
    
    # initialise the board and print it
    $x = $y = $treasures = 0;
    for $a (@a) {
        if ($x >= $edge) {
            $x = 0; $y ++;
        }
        $b->[$x]->[$y] = $a;
        if ($a eq 'x') {
            $treasures ++;
        }
        $x ++;
    }
    
    # show initial board
    say qq[\nInput:];
    for $y (0 .. $edge - 1) {
        for $x (0 .. $edge - 1) {
            print $b->[$x]->[$y] . ' ';
        }
        say '';
    }   
    
    # possible moves
    @moves = ([1, 2], [-2, -1], [1, -2], [-2, 1], [2, 1], 
        [2, -1], [-1, -2], [-1, 2]); 
    
    # starting position
    $treasure = $steps = 0;
    $found_at = '';
    $here = [0, 0];

    P: while (1) {
    
        ($x1, $y1) = @$here;
        $steps ++;
        
        # treasure here?
        if ($b->[$x1]->[$y1] eq 'x') {
            $b->[$x1]->[$y1] = '+';
            $treasure ++;
            $found_at .= qq[($x1, $y1), ];
            
            # found all the treasure
            if ($treasure == $treasures) {
                say qq[\nOutput: found all $treasures treasures: ] . 
                    substr($found_at, 0, -2);
                say qq[steps: $steps ];
                
                # 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];
                return;
            }
            
        # mark as visited   
        } else {
            $b->[$x1]->[$y1] = 'o';
        }
            
        # decide on next step
        for $pass (0 .. 2) {
            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);
                
                # if there is treasure there, go there
                if ($pass == 0) {
                    if ($b->[$x2]->[$y2] eq 'x') {
                        $here = [$x2, $y2];
                        next P;
                    }
                    
                # else go to an accessible unvisited place
                } elsif ($pass == 1) {
                    if ($b->[$x2]->[$y2] eq '*') {
                        $here = [$x2, $y2];
                        next P;
                    }
                }
                $else = [$x2, $y2];
            }
        }
        
        # neither treasure nor unvisited so go to visited place
        $here = $else;
        next P;
    }           
}   

last updated 2026-03-20 — 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