Knight's tour game (7x7)

Question

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 code-golf, so shortest code wins!

Answer 1

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), ⁵³ 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.

Answer 2

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!

Answer 3

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[])