The Trapped Knight
February 19, 2019
Over at Numberphile, Neil Sloane discusses a knight moving on an infinite chessboard with squares numbered in a square spiral (note that, starting from 1, the squares on the southeast diagonal are successive squares of odd numbers 1² = 1, 3² = 9, 5² = 25, 7² = 49, and so on):
37 36 35 34 33 32 31 38 17 16 15 14 13 30 39 18 5 4 3 12 29 40 19 6 1 2 11 28 . 41 20 7 8 9 10 27 . 42 21 22 23 24 25 26 . 43 44 45 46 47 48 49 50
The knight starts from square 1 and always moves to the smallest-numbered square not previously visited. Thus, from 1, the knight can move to squares 10, 12, 14, 16, 18, 20, 22 or 24, of which the smallest unvisited square is 10. From 10, the knight can then move to squares 1, 3, 23, 29, 47, 49, 51 or 53; the smallest of those, 1, has already been visited, so the knight moves to square 3. And so on. The beginning of the knight’s tour visits squares 1, 10, 3, 6, 9, 4 and so on (A316667).
Your task is to write a program to determine if the knight’s tour is infinite or if the knight becomes trapped with no remaining unvisited squares; if the knight becomes trapped, determine the length of his tour and the square on which he remains. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Not as easy to Perl golf this one – need to write to functions which map from “n” to “x,y” and back again…
Then it is simply a case of a step by step hop through the points using the classic knight moves…
Use a for loop with a large max value to see if it results in a value or an infinite sequence…
use strict; use warnings; use POSIX qw(ceil); my @offsets = ( [1,2],[-1,2],[1,-2],[-1,-2],[-2,-1],[2,-1],[-2,1],[2,1] ); my ($pos,$count,%seen) = qw(1 0); while($pos) { printf "%d\t%d\t(%d,%d)\n", $seen{$pos} = ++$count, $pos, my ($x,$y) = n2xy($pos); undef $pos; foreach (@offsets) { next if exists $seen{ my $a = xy2n( $x + $_->[0] , $y + $_->[1] ) }; $pos = $a unless defined $pos && $a > $pos; } } sub n2xy { my $n = shift; return (0,0) if $n == 1; my $r = ceil( (ceil sqrt $n)/2 - 1/2 ); my $q = ceil( (my $s = $n - (2*$r-1)**2)/$r/2) - 1; $s -= $q * $r * 2; return $q==0 ? ( $r, -$r+$s ) : $q==1 ? ( $r-$s, $r ) : $q==2 ? ( -$r, $r-$s ) : ( -$r+$s, -$r ); } sub xy2n { my($x,$y) = @_; return 1 unless $x || $y; my $s = (2*(my $r = abs $x > abs $y ? abs $x : abs $y)-1)**2; return $x== $r && $y!=-$r ? $s+ $r+$y : $y==$r ? $s+3*$r-$x : $x==-$r ? $s+5*$r-$y : $s+7*$r+$x ; }Scala:
case class Field(x: Int, y: Int) {
def left = Field(x – 1, y)
def right = Field(x + 1, y)
def up = Field(x, y – 1)
def down = Field(x, y + 1)
}
def nextStep(field: Field = Field(0, 0), alreadyVisited: Set[Field] = Set()): Option[Field] = {
val possibleSteps = Set(field.left.left.up, field.left.left.down, field.right.right.up, field.right.right.down, field.up.up.right, field.up.up.left, field.down.down.right, field.down.down.left)
val notVisitedSteps = possibleSteps — alreadyVisited
val stepsAndValues = notVisitedSteps.map(field => (n(field), field)).toList
val sorted = stepsAndValues.sortWith((f1, f2) => f1.1 < f2._1)
sorted.lift(0).map(._2)
}
val map = new java.util.HashMap[Field, Int]
def n(field: Field): Int = map.computeIfAbsent(field, mappingFunction)
def mappingFunction(field: Field): Int = {
val x = field.x
val y = field.y
val r = List(x.abs, y.abs).max
}
def A316667(field: Field = Field(0, 0), alreadyVisited: Set[Field] = Set(Field(0, 0))): Stream[Field] = {
val next = nextStep(field, alreadyVisited)
if (next.isEmpty) Stream(field)
else Stream.cons(field, A316667(next.get, alreadyVisited ++ next))
}
A316667().zipWithIndex.foreach(f => println(f._2 + 1 + “: ” + n(f._1)))
A Python solution:
def knight(x,y): """ Return list of all possible knight moves from (x,y) """ moves = [(1,2),(1,-2),(-1,2),(-1,-2), (2,1),(-2,1),(2,-1),(-2,-1)] return [(x+i,y+j) for (i,j) in moves] def p2i(x,y): """ Return index in spiral of (x,y) """ m = max(abs(x),abs(y)) base = 4*m*m+1 if y == -m: return base+3*m+x elif x == -m: return base+m-y elif y == m: return base-m-x elif x == m: return base-3*m+y else: assert(false) def tour(p): """ Generate indexes of knight tour starting at p """ index = p2i(*p) seen = set() while True: yield(index) seen.add(p) s = [(p2i(*q),q) for q in knight(*p) if q not in seen] if not s: break index,p = min(s) for index in tour((0,0)): print(index)