6
\$\begingroup\$

Your job is to solve this chess-related game.

The setup of the game is a 7x7 tile grid, you start on a random tile and you have to hop on each tile, until you hopped on all 49 tiles.

Top left corner is (0,0)

Rules:

  • you can hop on each tile once.
  • the only move allowed in the game is to hop two tiles horizontally and one tiles vertically, or two tiles vertically and one tiles horizontally, like a knight in a chess game.
  • your input should be a tuple representing the coordinates of the starting tile (stdin, file, what you prefer).
  • your output a list of tuples, representing the coordinates of each hop. If there's no valid combinations, return an empty list (same as above, any output is ok).

This is , so shortest code wins!

\$\endgroup\$
  • \$\begingroup\$ Is this seriously the only similar question? I thought this website covered the Knight's Journey/Knight's Tour pretty thoroughly. As it is, I have no idea if this is close enough to be a duplicate of the other post. \$\endgroup\$ – Justin Sep 28 '14 at 22:50
  • \$\begingroup\$ why won't this be called knight's tour straight away? \$\endgroup\$ – proud haskeller Sep 28 '14 at 22:52
  • 2
    \$\begingroup\$ According to mathworld.wolfram.com/KnightGraph.html There are no closed tours for m×m boards with m odd so it's not possible to take a single looped solution and simply start on a different square. That makes this reasonably interesting and not a direct duplicate of the linked question, which leaves the start square to choice. According to en.wikipedia.org/wiki/Knight's_tour there are 16557521832 directed tours on a 7x7 board so I imagine at least one starts on every square. I assume we only have to find one valid solution for the given input, not all of them! \$\endgroup\$ – Level River St Sep 28 '14 at 23:17
  • 2
    \$\begingroup\$ Actually, thinking about it, because a knight always alternates between black and white squares, he has to start and finish on squares of the same colour as the corner squares. If the corner squares are black and he starts on a white square, he will run out of white squares (24) before he has visited all the black squares (25). So it's not always possible to complete the tour. \$\endgroup\$ – Level River St Sep 29 '14 at 9:29
  • 1
    \$\begingroup\$ @Quincunx, no, it's not the only similar question. And there's another one which was closed as a dupe. \$\endgroup\$ – Peter Taylor Sep 29 '14 at 14:18
1
\$\begingroup\$

Python 3 - 272 263

Since this is a code-golf, this is built to be shorter in code, as opposed to faster in execution. Note that if you want solutions that will run in practical amounts of time, that almost requires some kind of dynamic programming, using a hash in addition to a list, and probably even some kind of heuristic. Otherwise, an exhaustive backtracking search may potentially take a very long time. It would be interesting to see a separate contest for the fastest knight's tour finder for all mxn boards for m0<=m<=M, n0<=n<=N

Anyway, here is the code. It expects an input as a tuple, i.e. (0,0)

p=[eval(input())]
def k():
 if 49==len(p):return 1
 n=[(p[-1][0]+x,p[-1][1]+y) for x in range(-2,3)for y in range(-2,3)if(abs(x)+abs(y)==3)]
 for z in n:
  if(min(z)<0 or max(z)>6 or z in p):continue
  p.append(z)
  if(k()):return 1
  p.remove(z)
if(k()):print(p)

Thanks to Fry for the golfing tips!

\$\endgroup\$
  • \$\begingroup\$ You can replace True and False with 1 and 0 (not that you need to replace False...). Also, wherever you have a closing bracket you don't need spaces after it: range(-2,3)for. You can also drop the brackets around if conditions: if 49==len(p):return 1. \$\endgroup\$ – FryAmTheEggman Sep 29 '14 at 16:31
0
\$\begingroup\$

Python 3 - 241 chars

This will work most of the time, if you live long enough to see the result...

It works by randomly reordering a list of all coordinates until it gets the right answer. If it takes more than 9*10^99 loops, it assumes that there is no answer. (It will be right the vast majority of the time, since the probability of getting the right order is roughly 1 in 6*10^63).

N.B. Yes, I know that this is not really a valid answer.

import random
l=[(x%7,x//7)for x in range(49)]
s=eval(input())
v=lambda x:all(abs((x[i][0]-x[i+1][0])*(x[i][1]-x[i+1][1]))==2 for i in range(len(x)-1))
t=0
while not all(v(l),l[0]==s,t<9e99):
 random.shuffle(l);t+=1
print(l if t<9e99 else[])
\$\endgroup\$
  • 1
    \$\begingroup\$ I think you could do l=[(x%7,x//7)for x in range(49)] to save a few chars. \$\endgroup\$ – stokastic Sep 29 '14 at 15:09
  • \$\begingroup\$ Also you can do x/7 instead of x//7, since x is already an integer, integer division is assumed. Every byte counts :) \$\endgroup\$ – stokastic Sep 29 '14 at 15:21
  • \$\begingroup\$ @stokastic I think this answer is in python 3, otherwise he wouldn't be using eval(input()). In python 3, x/7 will give floating point values. \$\endgroup\$ – FryAmTheEggman Sep 29 '14 at 16:35
  • \$\begingroup\$ @FryAmTheEggman That's correct. I've changed the title now to make it more clear. \$\endgroup\$ – monopole Sep 29 '14 at 17:06

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.