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;
}
Update: Spoiler tag removed.
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.