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


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

## ##
(4, 0) [5, 6, 3, 1, 6, 3, 0]

New challenge: Come up with more examples

  • \$\begingroup\$ "for the longest" ​ -> ​ "for a longest ​ ​ ​ ? ​ ​ ​ ​ ​ ​ ​ ​ \$\endgroup\$
    – user30594
    Commented Feb 22, 2016 at 6:18
  • \$\begingroup\$ Are you after a Hamiltonian path or a Hamiltonian cycle? \$\endgroup\$ Commented Feb 22, 2016 at 10:28
  • \$\begingroup\$ @PeterTaylor Whichever's golfier! A path is fine; so is a cycle because it's a valid path. \$\endgroup\$
    – wizzwizz4
    Commented Feb 22, 2016 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\$
    – user7467
    Commented Aug 4, 2021 at 5:34
  • 1
    \$\begingroup\$ @Anush Like this? \$\endgroup\$
    – wizzwizz4
    Commented Aug 4, 2021 at 22:15

1 Answer 1


Python 3.8 (pre-release), 254 bytes

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

  • \$\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\$ Commented Aug 2, 2021 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
    Commented Aug 3, 2021 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
    Commented Aug 3, 2021 at 12:12
  • \$\begingroup\$ Um, holy... +1, and I hope it ends up being +1000 or so. Great answer! \$\endgroup\$ Commented Aug 5, 2021 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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