Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
tree: 7d9c16311e
Fetching contributors…

Cannot retrieve contributors at this time

55 lines (43 sloc) 1.584 kb
use v6;
# 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).
my $n = 5;
my $size = $n * $n;
my @track;
my @directions = (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;
};
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";
}
Jump to Line
Something went wrong with that request. Please try again.