The Trapped Knight
February 19, 2019
We need a way to quickly determine the numbers of the squares to which a knight can move. The OEIS page on the trapped knight points to two pages that map the square number to lattice points on a cartesian grid, where we find these remarkable formulas (who thinks up these things?):
X(1) = 0, X(n) = X(n-1) + sin(mod(floor(sqrt(4*(n-2)+1)),4)*π/2)
Y(1) = 0, Y(n) = Y(n-1) – cos(mod(floor(sqrt(4*(n-2)+1)),4)*π/2)
Now it’s easy to write a function to convert a spiral square number to a grid number:
(define-memoized (n->point n)
(if (= n 1) (cons 0 0)
(let* ((k (modulo (isqrt (+ (* (- n 2) 4) 1)) 4))
(half-pi (* (atan 1) 2))
(k-half-pi (* k half-pi))
(prev (n->point (- n 1)))
(prev-x (car prev))
(prev-y (cdr prev)))
(cons (+ prev-x (inexact->exact (round (sin k-half-pi))))
(- prev-y (inexact->exact (round (cos k-half-pi))))))))
> (n->point 10) (2 . -1)
Going the other direction is a little bit harder, as there is no function that directly inverts the formulas given above. We make a hash table containing previously-computed grid points, and calculate unknown grid points as needed:
(define max-n 0) (define (hash p) (+ (* (car p) 10000) (cdr p))) (define points (make-hashtable hash equal?))
(define (point->n point)
(cond ((hashtable-ref points point #f)
=> (lambda (n) n))
(else (let loop ((n (+ max-n 1)))
(set! max-n n)
(let ((p (n->point n)))
(hashtable-set! points p n)
(if (equal? point p) n
(loop (+ n 1))))))))
> (point->n '(2 . -1) 10
Now we can compute the eight points to which a knight can travel:
(define (k-moves n)
(let* ((p (n->point n)) (x (car p)) (y (cdr p)))
(sort < (list (point->n (cons (+ x 2) (+ y 1)))
(point->n (cons (+ x 2) (- y 1)))
(point->n (cons (- x 2) (+ y 1)))
(point->n (cons (- x 2) (- y 1)))
(point->n (cons (+ x 1) (+ y 2)))
(point->n (cons (+ x 1) (- y 2)))
(point->n (cons (- x 1) (+ y 2)))
(point->n (cons (- x 1) (- y 2)))))))
> (k-moves 10) (1 3 23 29 47 49 51 53)
And now we can solve the problem:
(define (knight)
(let loop ((tour (list 1)))
(let ((moves (filter (lambda (n) (not (member n tour)))
(k-moves (car tour)))))
(if (null? moves) (reverse tour)
(loop (cons (car moves) tour))))))
And that’s it:
> (define tour (knight)) > (length tour) 2016 > (car (reverse tour)) 2084 > tour (1 10 3 6 9 4 ... 3101 2880 2467 2084)
The knight is trapped at square 2084 after visiting 2016 squares; the highest-numbered square that the knight visits is 3199. The code is collected at https://ideone.com/Ekdbxn, but it times out before completing the tour.
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)