16
\$\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 they have 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
AFC
D H
GBE

## ##
  ##
 ##
(4, 0) [5, 6, 3, 1, 6, 3, 0]
CF HA
  BE
 DG

New challenge: Come up with more examples

\$\endgroup\$
7
  • \$\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\$ 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
  • \$\begingroup\$ In your first example, does the tour start in the top left? If so it looks like “3 0 5 2” takes you to the bottom right corner and the final move “1” takes you to row 2, column 3. It might be helpful to spell this out. \$\endgroup\$
    – Anush
    Aug 4 at 5:34
  • 1
    \$\begingroup\$ @Anush Like this? \$\endgroup\$
    – wizzwizz4
    Aug 4 at 22:15
5
+100
\$\begingroup\$

Python 3.8 (pre-release), 254 bytes

n=-2,-1,1,2,2,1,-1,-2
l=len
e=enumerate
s=lambda b,x,y,t:max([1>((a:=[p:=x+_,q:=y+n[i-6]])in t)<l(b)>p>-1<q<l(b[p])>0<b[p][q]and[i]+s(b,p,q,t+[a])or[]for i,_ in e(n)],key=l)
f=lambda b:max([(z:=[x,y])+s(b,*z,[z])for x,r in e(b)for y,c in e(r)if c],key=l)

Try it online!

Pass input to the function f as a 2d array of truthy/falsey values.

Thanks to ovs and wizzwizz4

\$\endgroup\$
4
  • \$\begingroup\$ Welcome to Code Golf, and nice first answer! You may not assume the input is saved in a variable, such as b, per our default rules. You can change it to a function for 276 bytes. Additionally, this qualifies for this bounty offer of mine, so I've gone ahead and started a +100 bounty for you \$\endgroup\$ Aug 2 at 23:16
  • \$\begingroup\$ You can save two bytes by replacing and b[p][q]and with if b[p][q]if - list comprehensions can have multiple if's. \$\endgroup\$
    – ovs
    Aug 3 at 11:07
  • \$\begingroup\$ I added another example, which your answer fails; I think your solution's finding the first, rather than the longest, solution. (Unless I typed it in wrong, that is.) \$\endgroup\$
    – wizzwizz4
    Aug 3 at 12:12
  • \$\begingroup\$ Um, holy... +1, and I hope it ends up being +1000 or so. Great answer! \$\endgroup\$ Aug 5 at 21:41

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.