Perl Weekly Challenge 118: Adventure of Knight

by Abigail

Challenge

A knight is restricted to move on an 8x8 chessboard. The knight is denoted by N and its way of movement is the same as what it is defined in Chess. * represents an empty square. x represents a square with treasure.

The Knight's movement is unique. It 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).

There are 6 squares with treasures.

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

      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

BONUS: If you believe that your algorithm can output one of the shortest possible paths.

Discussion

There isn't much of a challenge here, is there? Knight's tours have been known for eons. And a Knights tour visits every square on a chess board. So, we could just pick one of the 19,591,828,170,979,904 different tours (sequence A165134 on the OEIS) and call it a day. Or, if we wanted to return to our starting square, we still have 26,534,728,821,064 closed tours to pick from.

And that's not even counting all the paths with visit a square more than once — the challenge does not prohibit visiting a square more than once.

So, perhaps we should focus at the bonus part of the challenge.

But there isn't much of a challenge there. The problem is, there is no variable input. There's just one input.

First, let us wonder the minimum length of a path capturing all the treasure. Of note is that if a chess knight is on a white square, moving it lands it on a black square, and moving a knight on a black square lands it on a white square. Now, a8, the square the knight starts on, is white, and so are five of the squares containing treasure. This means, we need to take at least 10 steps to visit all the treasure.

Can we actually visit all the treasure in 10 steps? Well, after 10 steps, the knight is on a white square. Which means, a 10 step path cannot finish on b2 (one of the squares containing treasure), as b2 is a black square. Now look at the squares one knights move away from b2: d1, d3, c4, and a4. Only one of them contains treasure (c4). Which means that we either have to visit a white square not containing treasure, or we visit a square containing treasure twice. But to that, we need more than 10 steps.

So, what about an 11 step path. Is that possible?

Yes, it's easy to see there is an 11-step path visiting all the squares:

a8 c7 e6 c5 b3 c1 a2 c3 b1 a3 c4 b2

So, an 11 step path is the shortest path possible.

But that means, there nothing left to be calculated, and the problem boils down to a glorified Hello, World! program.

Solutions

Perl

say "a8 c7 e6 c5 b3 c1 a2 c3 b1 a3 c4 b2";

Find the full program on GitHub.

Other languages

We also have solutions in AWK, Bash, Basic, bc, Befunge-93, C, Cobol, Csh, Erlang, Forth, Fortran, Go, Java, Lua, m4, MMIX, Node.js, OCaml, Pascal, PHP, PostScript, Python, R, Rexx, Ruby, Scheme, sed, SQL, and Tcl.

Upping the ante

Since the challenge as stated was not much of a challenge, we also make an alternative solution — one which actually accepts input.

As input we take a line of input, where the squares containing treasure are separated by white space. The first square is taken as the start square of the knight.

Perl

We start off with a helper function, one which maps a tuple of a rank and a file (both numbers from 1 to 8 inclusively), to the algebraic name of the square:

sub c2a ($file, $rank) {
    sprintf "%c%d", ord ('a') + $file - 1, $rank
}

Now, we precalculate all the possible knight moves. That is, for each square, we calculate which squares are reachable with a single knights move:

my $MAX_FILE = 8;
my $MAX_RANK = 8;

my %knight_moves;  # Maps square to all squares reachable from it.
for my $file (1 .. $MAX_FILE) {
    for my $rank (1 .. $MAX_RANK) {
        my $square = c2a $file, $rank;
        #
        # Consider only moves in one direction; we add reverse moves as well.
        # Knight moves 2 in one direction, and 1 orthogonally from that.
        #
        for my $move ([1, 2], [1, -2], [2, 1], [2, -1]) {
            next unless 1 <= $file + $$move [0] <= $MAX_FILE &&
                        1 <= $rank + $$move [1] <= $MAX_RANK;
            my $target = c2a $file + $$move [0], $rank + $$move [1];
            push @{$knight_moves {$square}} => $target;
            push @{$knight_moves {$target}} => $square;
        }
    }
}

We now perform a breadth first search.

Now, normally in a breadth first search, we don't recurse once we revisit a node. But in this challenge, it is possible the shortest path visiting all treasure visits a square more than once. We will recurse visiting a node we already visited, but only if we have a visited a different set of squares with treasure. (Alternatively, we could consider finding a path where the nodes are the cartesian product of the squares on the board, and the power set of the set of treasure squares).

For the breadth first search, we keep a @todo array, where each element is tuple (representing a node in the graph we're searching): the first element is the path that got us there (with the last element being the current square). The second element is a hash where the keys are the treasure squares we have visited on the path in the first element.

In the main loop, we shift an element from the @todo list, calculate which squares are reachable, and for each of those squares, we push a new element to the @todo array. If we have seen all the treasure, we return the current path:

sub find_treasure ($start_square, @treasure) {
    my %treasure = map {$_ => 1} @treasure;

    my %visited;
    my @todo = ([[$start_square], {}]);

    while (@todo) {
        my ($path, $old_seen) = @{shift @todo};
        my  $square = $$path [-1];
        my  $seen = { %$old_seen};
           $$seen {$square} = 1 if $treasure {$square};

        my $key = join " " => $square, sort keys %$seen;
        next if $visited {$key} ++;

        if (keys %$seen == keys %treasure) {
            return $path;
        }   

        push @todo => map {[[@$path => $_], $seen]} @{$knight_moves {$square}};
    }
}

All what rest is read in the input, call the method above, and print the result. We can do that in a one liner:

say "@{find_treasure split}" while <>;

Find the full program on GitHub.

Please leave any comments as a GitHub issue.