8
\$\begingroup\$

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.

Task

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.

Input

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.

Output

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
  K
5   2
 4 3

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

Examples

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

\$\endgroup\$
  • \$\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
2
\$\begingroup\$

Mathematica, 151 bytes

Needs@"Combinatorica`"
{Reverse@#[[1]]-1,3-Floor[1.2Arg[Complex@@@Differences@#]]}&[#[[HamiltonianPath@MakeGraph[#,Norm[#-#2]^2==5&]]]&@Position[#,1]]&

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.

\$\endgroup\$
  • \$\begingroup\$ You can apply HamiltonianPath with @. \$\endgroup\$ – CalculatorFeline Feb 22 '16 at 5:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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