Before I went to bed, I only had a guess. I started with a pen and paper, and some maths:
w * h = (w - 2) * h + 10
w * h - (w - 2) - h = 10
h * (w - w + 2) = 10
2h = 10
h = 5
Now, we need to find the width. To be able to step on every tile, it must be coprime with the height, and moreover, width - 2 must be coprime with the height as well. I drew the simplest cases and extrapolated the observation to the following sequence: 3, 9, 11, 13, 19, 21, 23...
And when I got up, I verifyied the results with a Perl program. Specify a true command line argument to see the paths:
#!/usr/bin/perl
use strict;
use warnings;
my $DEBUG = shift;
sub steps {
my ($w, $h) = @_;
print "$w x $h\n" if $DEBUG;
my $steps = 1;
my @dir = ( 1, 1 );
my ($x, $y) = (1, 1);
my @visited = ([], [ undef, '\\' ]);
while () {
$x += $dir[0];
$y += $dir[1];
$dir[0] = -1, $x -= 1 if $x > $w;
$dir[1] = -1, $y -= 1 if $y > $h;
$dir[0] = 1, $x = 1 if $x < 1;
$dir[1] = 1, $y = 1 if $y < 1;
++$steps;
return -1 if $steps > $w * $h or $visited[$x][$y];
$visited[$x][$y] = $dir[0] != $dir[1] ? '/' : '\\';
if ($DEBUG) {
for my $x (1 .. $w) {
for my $y (1 .. $h) {
print $visited[$x][$y] // ' ';
}
print "\n";
}
sleep 1;
print "\n";
}
if ($x == $w and $y == $h) {
last if $steps == $w * $h
and '\\' eq $visited[$x][$y];
return -1
}
}
return $steps
}
my @steps;
my $width = 1;
until (0) {
for my $height (1 .. $width) {
$steps[$width][$height] = steps($width, $height);
print "$width x $height = $steps[$width][$height]\n"
if ($height > 2 and $steps[$width][$height - 2] =
+= $steps[$width][$height] - 10)
or ($height < $width - 1 and $steps[$width - 2][$height] =
+= $steps[$width][$height] - 10)
}
++$width;
}
Spoiler tag removed.
