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

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: