# P91 - Knight's tour.

*Author: Edwin Pratomo*

# Specification

P91 (**) Knight's tour Another famous problem is this one: How can a knight jump on an NxN chessboard in such a way that it visits every square exactly once? Hints: Represent the squares by pairs of their coordinates of the form X/Y, where both X and Y are integers between 1 and N. (Note that '/' is just a convenient functor, not division!) Define the relation jump(N,X/Y,U/V) to express the fact that a knight can jump from X/Y to U/V on a NxN chessboard. And finally, represent the solution of our problem as a list of N*N knight positions (the knight's tour).

Source code: P91-edpratomo.pl

use v6; my $n = 5; my $size = $n * $n; my @track; my @directions = flat ((1, -1 X 2, -2), (2, -2 X 1, -1)); sub valid_moves($curr, @temp_track=@track) { my @valid_squares = @directions.map(->$a,$b { ($curr.key + $a) => ($curr.value + $b) }).grep({0 <= all(.key, .value) < $n}); # exclude occupied squares. !eqv doesn't work yet. @valid_squares.grep({ not $_ eqv any(|@temp_track, $curr) }); } sub knight($square) { @track.push($square); return 1 if @track.elems == $size; # simple heuristic, for move ordering my @possible_moves = valid_moves($square).sort: ->$a,$b { valid_moves($a, [|@track,$a]).elems <=> valid_moves($b, [|@track, $b]).elems or $a.key <=> $b.key or $a.value <=> $b.value; }; return unless @possible_moves.elems; for @possible_moves -> $try { my $result = knight($try); if $result { return 1; } else { @track.pop; } } } if knight(0 => 0) { say "FOUND: " ~ @track.perl; } else { say "NOT FOUND"; }