7
\$\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!

| improve this question | | | | |
\$\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
2
+200
\$\begingroup\$

APL (Dyalog Extended), 39 bytes

7 7{3::0⋄(⍋,(⊢⊃⍨⍵⍳⍨⊃∘⍸¨∘=)¯1⌂kt⍺)⊇,⍳⍺}⊂

Try it online!

A version provided by @Adám.

Dyalog Extended has a shortcut to the dfns library , and a few convenience functions e.g. monadic = which is equivalent to 0∘=, and dyadic for multiple indexing. Unfortunately an inner assignment is buggy, so we use a tacit inner function to reference the value of ¯1⌂kt⍺ twice. Otherwise we'd have a 38 byte solution:

7 7{3::0⋄(⍋,w⊃⍨⍵⍳⍨⊃∘⍸¨=w←¯1⌂kt⍺)⊇,⍳⍺}⊂

How the inner tacit function (⊢⊃⍨⍵⍳⍨⊃∘⍸¨∘=) works

This tacit function has 5 terms: `⊢`  `⊃⍨`  `⍵`  `⍳⍨`  `⊃∘⍸¨∘=`
A tacit function is grouped by 3 terms from the right:
  ⊢ ⊃⍨ (⍵ ⍳⍨ ⊃∘⍸¨∘=)
A group of 3 terms is interpreted as follows:
  (f g h)w → (f w) g (h w)     ⍝ f, g, h are functions
  (A g h)w → (A  ) g (h w)     ⍝ A is an array
Then we can interpret the above tacit function as
  (⊢ ⊃⍨ (⍵ ⍳⍨ ⊃∘⍸¨∘=))w
  → (⊢ w) ⊃⍨ (⍵ ⍳⍨ (⊃∘⍸¨∘= w))   ⍝ Expand tacit function
  → w ⊃⍨ ⍵ ⍳⍨ ⊃∘⍸¨∘= w           ⍝ ⊢ is identity function; simplify parens
  → w ⊃⍨ ⍵ ⍳⍨ ⊃∘⍸¨ = w           ⍝ (f∘g)w simply expands to f g w
So the code `(⊢⊃⍨⍵⍳⍨⊃∘⍸¨∘=)w` is equivalent to `w⊃⍨⍵⍳⍨⊃∘⍸¨=w`.

APL (Dyalog Unicode), 53 49 bytes

⎕CY'dfns'
7 7{3::0⋄(,⍳⍺)[⍋,w⊃⍨⍵⍳⍨⊃∘⍸¨0=w←¯1kt⍺]}⊂

Try it online!

Golfed 4 bytes by extracting some terms out of the dfn using a tacit form.


Original submission: APL (Dyalog Unicode), 53 bytes

⎕CY'dfns'
{3::0⋄(,⍳7 7)[⍋,w⊃⍨(⊃∘⍸¨0=w←¯1 kt 7 7)⍳⊂⍵]}

Try it online!

Because we've got a language that has a Knight's tour solver built in.

Since ¯1 kt 7 7 tries to find all solutions, it's infeasible to actually run the code as-is. For demonstration purposes, the TIO link uses 3x4 board instead.

How it works

The function dfns.kt finds a (possibly open) Knight's tour, where the right argument is the board's dimensions, and the optional left argument is the number of solutions to find. Giving -1 on the left causes the function to search all possible solutions.

⎕CY'dfns'  ⍝ Import the 'dfns' workspace

{3::0⋄(,⍳7 7)[⍋,w⊃⍨(⊃∘⍸¨0=w←¯1 kt 7 7)⍳⊂⍵]}  ⍝ ⍵←starting coordinates
                          w←¯1 kt 7 7        ⍝ Find ALL solutions of 7x7 knight's tour
                   (⊃∘⍸¨0=           )       ⍝ Extract the starting coordinates from each solution
                                      ⍳⊂⍵    ⍝ Find the index of the solution that starts at ⍵
               ,w⊃⍨                          ⍝ Fetch the solution and flatten it
      (,⍳7 7)                                ⍝ Take the flattened list of coordinates on 7x7 board
             [⍋                          ]   ⍝ Sort the coordinates by flattened solution
 3::0⋄                                       ⍝ If there's no solution starting with ⍵,
                                             ⍝ catch the Index Error and return 0 instead

Every black square on 7x7 board can be the starting location of a Knight's tour.

The following isn't directly related to the code above, but nevertheless here is a proof by example.

Starting at (0,0), Ending at (5,1)

0  11 22 45 2  13 24
21 46 1  12 23 44 3
10 27 34 39 36 25 14
47 20 37 26 33 4  43
28 9  40 35 38 15 32
19 48 7  30 17 42 5
8  29 18 41 6  31 16

Starting at (1,3), Ending at (6,4)

20 27 10 33 44 1  12
9  32 21 0  11 34 45
26 19 28 43 40 13 2
31 8  41 22 29 46 35
18 25 30 39 42 3  14
7  38 23 16 5  36 47
24 17 6  37 48 15 4

Starting at (2,2), Ending at (3,3)

30 19 40 3  28 17 38
41 2  29 18 39 4  27
20 31 0  13 10 37 16
1  42 11 48 15 26 5
32 21 14 9  12 47 36
43 8  23 34 45 6  25
22 33 44 7  24 35 46

By swapping heads and tails, reflection, and rotation, all black squares can be the starting point of some Knight's tour.

I found these three tours by splitting the board into four groups that can form a continuous loop:

O O O . O O O  |  . . . O . . .  |  . . . . . . .  |  . . . . . . .
O . O O O . O  |  . O . . . O .  |  . . . . . . .  |  . . . . . . .
O O . . . O O  |  . . . . . . .  |  . . O O O . .  |  . . . . . . .
. O . . . O .  |  O . . . . . O  |  . . O . O . .  |  . . . O . . .
O O . . . O O  |  . . . . . . .  |  . . O O O . .  |  . . . . . . .
O . O O O . O  |  . O . . . O .  |  . . . . . . .  |  . . . . . . .
O O O . O O O  |  . . . O . . .  |  . . . . . . .  |  . . . . . . .

and breaking and gluing the chains whenever needed. It's kind of a heuristic, so it would be usually shorter to hardcode the three boards or just run naive DFS.

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ 39 in Extended \$\endgroup\$ – Adám Jan 2 at 11:49
  • \$\begingroup\$ 50 \$\endgroup\$ – Adám Jan 2 at 11:57
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!

| improve this answer | | | | |
\$\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
1
\$\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[])
| improve this answer | | | | |
\$\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.