I wrote this on the ride home. I makes Knight's Tour Puzzles. This is a puzzle with a grid of letters, encoding a message that you discover by moving from square to square as a knight would in chess, never hitting the same square twice.
knightstour.pl:
#!/usr/local/bin/perl -w
use strict;
my $usage = "knightstour.pl ROWS COLS MESSAGE\n";
die $usage unless @ARGV == 3;
#main
{
my( $numrows, $numcols, $message ) = @ARGV;
my @letters = split //, $message;
die "length of $message = ",scalar(@letters)," must be ",
$numrows*$numcols,"\n"
if @letters != $numrows * $numcols;
# store grid in hash; $grid->{"0,0"} = "x";
my $grid = {};
# starting position. use upper left corner. could randomize
my $row = 0;
my $col = 0;
# recursively look for solutions
trypath( $grid, \@letters, $numrows, $numcols, $row, $col );
}
# look for a path
sub trypath {
my( $gridref, $lettersref, $numrows, $numcols, $row, $col ) = @_;
# make local copy of grid, letters-to-do list
my $grid = { %$gridref };
my $letters = [ @$lettersref ];
# remove 1st letter from letter list. store in a square
$grid->{"$row,$col"} = shift @$letters;
# if no more letters, print solution
if( !@$letters ) {
printgrid( $grid, $numrows, $numcols );
# otherwise try possible next moves
} else {
# find possible next moves
foreach (
grep {
# square under consideration actually on the grid
$_->[0] >= 0
&& $_->[0] < $numrows
&& $_->[1] >= 0
&& $_->[1] < $numcols
# no letter on it yet
&& !defined $grid->{"$_->[0],$_->[1]"}
}
# possible knight's moves
[ $row-1, $col-2 ],
[ $row-1, $col+2 ],
[ $row+1, $col-2 ],
[ $row+1, $col+2 ],
[ $row-2, $col-1 ],
[ $row-2, $col+1 ],
[ $row+2, $col-1 ],
[ $row+2, $col+1 ] ) {
# try it
trypath( $grid, $letters, $numrows, $numcols, $_->[0], $_->[1] );
}
}
}
sub printgrid {
my( $grid, $numrows, $numcols ) = @_;
for( my $row = 0; $row < $numrows; ++$row ) {
for( my $col = 0; $col < $numcols; ++$col ) {
print $grid->{"$row,$col"} || "_", " ";
}
print "\n";
}
print "\n";
}
Some sample results:
i i u k i
b e l a n
n s d k i
s e e a r
s s t b s
y e o e c m h
o i a m c s o
t u c k l o y
CS people have worked out interesting and more efficient solutions to this problem, but this script is fine for generating puzzles small enough for a human to actually solve.