We've all heard of the Knight's Tour puzzle: find a route for a knight that passes through all the squares on a chess board. But let's be honest, it's a little bit boring. So, let's give the knight a bit of a challenge.


Write a program that takes the knight through all the squares on an arbitrary-sized, arbitrary-shaped chess board. It should take the chess board as input and output the set of moves and the starting position. In the event of an impossible board, it should output the set of moves and starting position for a tour with the longest possible length. Note: the knight doesn't need to take a round trip; assume (s)he has another way to get home.

Chess pieces are small, so your code needs to be small enough for the knight to carry around.


The input will be a string-based or array-based representation of a chess board, where a non-blank / truthy value is a square, and a blank / falsy value is an empty space. For simplicity's sake I will use #s and s arranged in a grid for the examples.


The output will be two large integers, followed by a series of 4-bit integers, or your language's equivalent. The two large integers will represent the starting co-ordinates, and the following numbers will represent a move like so:

 7 0
6   1
5   2
 4 3

where K is the position before the move, and the number is the position after the move.


As there are a lot of possible solutions to the Knight's Tour puzzle, I will only provide example outputs. There may be more outputs.

# #
0 0 3 0 5 2 7 4 1

New challenge: Come up with more examples

  • \$\begingroup\$ "for the longest" ​ -> ​ "for a longest ​ ​ ​ ? ​ ​ ​ ​ ​ ​ ​ ​ \$\endgroup\$ – user30594 Feb 22 '16 at 6:18
  • \$\begingroup\$ Are you after a Hamiltonian path or a Hamiltonian cycle? \$\endgroup\$ – Peter Taylor Feb 22 '16 at 10:28
  • \$\begingroup\$ @PeterTaylor Whichever's golfier! A path is fine; so is a cycle because it's a valid path. \$\endgroup\$ – wizzwizz4 Feb 22 '16 at 16:35

Mathematica, 151 bytes


Obviously, HamiltonianPath@MakeGraph[#,Norm[#-#2]^2==5&] does all the work.

Input is a 2D (0,1)-matrix like {{0,0,1},{1,1,1},{1,0,1},{1,1,1}}.

Output looks like this: {{2, 0}, {5, 3, 0, 5, 2, 7, 4, 1}}

I don't know a lot about Mathematica golf, so feel free to point out improvements. Is there a better way to save individual results than using a billion pure functions?

Saved a byte; thanks, CatsAreFluffy.

  • \$\begingroup\$ You can apply HamiltonianPath with @. \$\endgroup\$ – CalculatorFeline Feb 22 '16 at 5:09
  • 2
    \$\begingroup\$ This answer is invalid because it doesn't satisfy "In the event of an impossible board, it should output the set of moves and starting position for a tour with the longest possible length." \$\endgroup\$ – Bubbler Dec 27 '19 at 9:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.