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

Pages: 1 2

### 3 Responses to “The Trapped Knight”

1. James Curtis-Smith said

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 + \$_-> , \$y + \$_-> ) };
\$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 ;
}
```
2. Andras said

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

``````val next =
if (x == y && x > -1) (2 * x + 1) * (2 * y + 1) + 1
else if (y == r) n(field.right)
else if (x == -r) n(field.down)
else if (y == -r) n(field.left)
else n(field.up)
next - 1
``````

}

def A316667(field: Field = Field(0, 0), alreadyVisited: Set[Field] = Set(Field(0, 0))): Stream[Field] = {
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)))

3. matthew said

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)
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)
```
```\$ python3 knight.py
1
10
3
6
...
3101
2880
2467
2084
```