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.

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: