## 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.

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…

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)._2)sorted.lift(0).map(

}

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: