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.

Advertisements

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 + $_->[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 ;
    }
    
  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] = {
    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)))

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: