Programming Praxis

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.

Pages: 1 2