12
\$\begingroup\$

A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. For those who are not aware of how knights in chess work, knights are capable of moving in an L shape (see fig. 1). (Or a ߆ shape, or even a \ shape depending on who you ask.) Essentially, in one move, a knight moves two squares on one axis and one square on the other.

Tours generally apply to a regular chessboard but it can be calculated for other sizes. For example, see fig. 2 for a possible knight's tour on a chessboard of size \$5\$. The knight starts in the top-left square, denoted by a \$1\$ and works its way through every square until it finally ends in the \$25th\$ square it visits, in the very center. A tour's validity is not necessarily affected by the squares it starts and ends in.

all potential knight's moves an example of 5×5 knight's tour
fig. 1 fig. 2

For grid size \$n = 5\$, that is only one of \$1728\$ options. A regular chessboard, where \$n = 8\$, has slightly more possible tours, with a total of \$19,591,828,170,979,904\$. This is OEIS A165134.

Challenge

Write a program/function that takes a grid size \$n\$ and outputs either a possible valid board of integers or list of coordinates.

Specifications

  • Standard I/O rules apply.
  • Standard loopholes are forbidden.
  • \$n > 4\$, as there are no valid tours for those grid sizes.
  • Your solution can either be 0-indexed or 1-indexed for either step count and coordinates but please specify the format and indexing.
  • This challenge is not about finding the shortest approach in all languages, rather, it is about finding the shortest approach in each language.
  • Your code will be scored in bytes, unless otherwise specified.
  • Built-in functions that compute knight's tours (guessing it's just Mathematica here) are allowed but including a solution that doesn't rely on a built-in is encouraged.
  • Explanations, even for "practical" languages, are encouraged.

Potential outputs

Considering how many possible tours there are, test cases would serve no real purpose. Instead, a couple possible knight's tours have been provided below for the sake of understanding the format options. Note that the chosen delimiters for the following are not mandatory.

\$n\$ Board List
\$5\$
 1 24 13 18  7 
14 19 8 23 12
9 2 25 6 17
20 15 4 11 22
3 10 21 16 5
0,0 1,2 0,4 2,3 4,4 3,2 4,0 2,1 0,2 1,4 3,3 4,1 2,0 0,1 1,3 3,4 4,2 3,0 1,1 0,3 2,4 4,3 3,1 1,0 2,2
\$8\$
 1 50 15 32 55 28 13 30
16 33 54 57 14 31 64 27
51 2 49 44 61 56 29 12
34 17 60 53 58 47 26 63
3 52 45 48 43 62 11 40
18 35 20 59 46 41 8 25
21 4 37 42 23 6 39 10
36 19 22 5 38 9 24 7
0,0 2,1 4,0 6,1 7,3 6,5 7,7 5,6 7,5 6,7 4,6 2,7 0,6 1,4 0,2 1,0 3,1 5,0 7,1 5,2 6,0 7,2 6,4 7,6 5,7 3,6 1,7 0,5 2,6 0,7 1,5 0,3 1,1 3,0 5,1 7,0 6,2 7,4 6,6 4,7 5,5 6,3 4,4 2,3 4,2 5,4 3,5 4,3 2,2 0,1 2,0 4,1 3,3 1,2 0,4 2,5 1,3 3,4 5,3 3,2 2,4 4,5 3,7 1,6

Validators

For output as a board using spaces between columns and newlines between rows. For output as a coordinate list using commas between axes and spaces between coordinates.

This challenge was sandboxed. For over five years.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ Note that you are limited somewhat as to which starting and ending squares you can choose on an odd size board. \$\endgroup\$
    – Neil
    Commented Feb 1 at 12:52
  • \$\begingroup\$ Ok to output all possible solutions instead of just one? Since some solutions are already doing brute-force anyway \$\endgroup\$ Commented Feb 1 at 18:34
  • \$\begingroup\$ @noodleman I'm gonna say no because a) there's too many answers already and b) dumping 1728 (at minimum) outputs on somebody that asked for one is a bit rude. :P \$\endgroup\$ Commented Feb 2 at 2:59
  • \$\begingroup\$ Fair enough, although I don’t think “too many answers already” is good reasoning for not allowing less strict I/O. I don’t really mind either way \$\endgroup\$ Commented Feb 2 at 12:45
  • 1
    \$\begingroup\$ @noodleman It's not just "less strict I/O". It can fundamentally change the approach solutions take and can end up making solutions shorter. This would be unfair to those who've already answered and moved on hence the "too many answers". If it were only a couple answers and had I not been asleep when you suggested it, I would've considered making the change. \$\endgroup\$ Commented Feb 2 at 12:51

7 Answers 7

6
\$\begingroup\$

Python 3.8 (pre-release), 170 bytes

def f(n,P=[(0,0)]):
 for j in range(8):
  x,y=P[0];q=x+~(j%2)*~-(j&2),y-(2-j%2)*~-(j//2&2)
  if(q in P)-(n>q[0]>-1<q[1]<n)<0and len(R:=f(n,[q]+P))==n*n:return R
 return P

Try it online!

Some people were really dedicated into golfing this, thanks to everyone!

  • -4 bytes thank to @movatica by using a - instead of a * when validating a position, and replacing all with a chained comparison between tuple elements

  • -3 bytes thank to @Arnauld by removing intermediate variables a and b when creating q

  • -3 bytes thank to @Mukundan314 by moving x and y to inside the loop and building the tour in reverse

Python 3.8 (pre-release), 205 192 188 186 180 bytes

Original version, with not-so-clever golfings :)

def f(n,P=[(0,0)]):
 x,y=P[-1]
 for j in range(8):
  a=j%2+1;b=3-a;q=x+a-a*(j&2),y+b-b*(j&4)//2
  if(q not in P)*all(n>v>=0for v in q)and len(R:=f(n,P+[q]))==n*n:return R
 return P

Try it online!

  • -4 bytes by calculating a using addition instead of indexing, and inlining b

  • -2 bytes thank to @xnor's nice remark about replacing & with % when calculating a

  • -4 bytes thank to @Mukundan314's improvements regarding returning directly instead of breaking, using list concatenation instead of unpacking, and removing () when creating q

  • -15 bytes thank to @movatica's amazing improvements regarding bitwise operations, reordering some declarations, and removing V completely (using only arithmetic)


Extremely inefficient, but it works in theory. It can run \$n = 5\$ on TIO, but it takes ~8 minutes to run \$n = 6\$ on my local interpreter.

A function that accepts \$n\$ as first argument and returns a list of sized-2 tuples.

How it works?

The algorithm always start on the top-left corner and uses P as a list[tuple[int, int]].

A horse can have 8 movements, so they can be encoded in an integer (for example, 0b101):

  1. if the first bit is set, then the horse moves 1 piece horizontally and 2 pieces vertically. Otherwise, it moves 2 pieces horizontally and 1 piece vertically
  2. if the second bit is set, then the horse moves up. Otherwise, it moves down
  3. if the third bit is set, then the horse moves left. Otherwise, it moves right

Therefore, for each movement a horse can make (for j in range(8):), decode a and b as the movement offsets on the board (by reading the first bit of j) and calculate q, a sized-2 tuple containing the new position of the horse on the board (decoding the movement directions by reading the second and third bits of j).

It then checks if the new calculated position is within the board (all(0<=v<n for v in q)) and if that position is not already occupied (q not in P). If it's valid, then it calls f again with that position stored in P. If, in any step of the recursion, P contains exactly \$n^2\$ elements (i.e. all positions in the board are occupied), then return it.

It outputs

  • [(0, 0), (1, 2), (2, 4), (4, 3), (3, 1), (1, 0), (2, 2), (0, 3), (1, 1), (3, 0), (4, 2), (3, 4), (1, 3), (0, 1), (2, 0), (4, 1), (3, 3), (1, 4), (0, 2), (2, 1), (4, 0), (3, 2), (4, 4), (2, 3), (0, 4)] for \$n=5\$

  • [(0, 0), (2, 1), (4, 0), (3, 2), (1, 1), (3, 0), (5, 1), (4, 3), (5, 5), (3, 4), (1, 3), (0, 1), (2, 0), (1, 2), (3, 1), (5, 0), (4, 2), (5, 4), (3, 5), (1, 4), (0, 2), (1, 0), (2, 2), (4, 1), (5, 3), (4, 5), (3, 3), (5, 2), (4, 4), (2, 5), (0, 4), (2, 3), (1, 5), (0, 3), (2, 4), (0, 5)] for \$n=6\$

\$\endgroup\$
12
  • 1
    \$\begingroup\$ can't you just strip the >>0? :) \$\endgroup\$
    – movatica
    Commented Feb 1 at 18:15
  • 1
    \$\begingroup\$ 200 bytes using a,b=[1,2][::V[j&1]];q=(x+a*V[j&2>0],y+b*V[j&4>0]) \$\endgroup\$
    – movatica
    Commented Feb 1 at 18:17
  • 2
    \$\begingroup\$ (j&1)+1 can be j%2+1 \$\endgroup\$
    – xnor
    Commented Feb 1 at 18:30
  • 1
    \$\begingroup\$ 188 bytes \$\endgroup\$
    – movatica
    Commented Feb 1 at 18:33
  • 2
    \$\begingroup\$ q=(x+a*V[j&2>0],y+(3-a)*V[j&4>0]) -> q=x+a*V[j&2>0],y+(3-a)*V[j&4>0] (removes surrounding brackets) for two bytes \$\endgroup\$ Commented Feb 1 at 18:43
5
\$\begingroup\$

Vyxal 3, 14 13 12 bytes

-1 byte thanks to Mukundan314

ẊṖΩᵃȧᵛΠ2p≈}h

(Don’t) Try it Online! (link is to literate version) because it's way too slow.

This brute-forces solutions, so it’s horribly inefficient. It times out on the online interpreter very quickly, and hits Scala's garbage collection limit with the native build after a few minutes.

The last 2 bytes can be removed if outputting all possible solutions instead of just the first one is OK.

Explanation

ẊṖΩᵃȧᵛΠ2p≈}h­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌⁣⁡​‎‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁣⁢​‎‎⁡⁠⁣⁤‏‏​⁡⁠⁡‌⁣⁣​‎‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌­
Ẋ             ##  ‎⁡Treating the input as the range [1, it], take the
              ##  ‎⁡  cartesian product with itself. This gives the
              ##  ‎⁡  list of coordinates of the n*n chessboard.
 Ṗ            ##  ‎⁢Take the permutations (all orders of the elements)
              ##  ‎⁢  of the board. This is the slow part.
  Ω           ##  ‎⁣Filter the permutations, only keeping those for
              ##  ‎⁣  which the following function returns true:
   ᵃ          ##  ‎⁤    Apply the following to each pair (including
              ##  ‎⁤      those which overlap):
    ȧ         ##  ‎⁢⁡        Absolute difference.
     ᵛ        ##  ‎⁢⁢    Apply to each resulting pair:
      Π       ##  ‎⁢⁣        Take the product of the list. This will 
              ##  ‎⁢⁣          be 2 if and only if the two pieces were
              ##  ‎⁢⁣          a knight's move away.
       2p     ##  ‎⁢⁤    Prepend a 2 to this list.
         ≈    ##  ‎⁣⁡    Are all elements of the list equal?
          }   ##  ‎⁣⁢Close the filter function.
           h  ##  ‎⁣⁣Return the first successful solution.
💎

Created with the help of Luminespire.

Independently derived from, but using a very similar method to, @Mukundan314’s solution.

\$\endgroup\$
4
  • \$\begingroup\$ Is this missing an absolute value? (The product of differences can be -2 and +2) \$\endgroup\$
    – ovs
    Commented Feb 1 at 18:50
  • \$\begingroup\$ @ovs Yep, I forgot how the knight moves, fortunately Vyxal has an absolute difference builtin so it’s the same length \$\endgroup\$ Commented Feb 1 at 18:52
  • \$\begingroup\$ The initial dup doesn't seem to be required, as vyxal seem cycle the input once all input is exhausted \$\endgroup\$ Commented Feb 2 at 2:29
  • \$\begingroup\$ @Mukundan314 Nice catch \$\endgroup\$ Commented Feb 2 at 12:39
4
\$\begingroup\$

Vyxal 3, 19 14 bytes

-4 bytes thanks to @noodleman

ẊṖΩᵃȧᵛSu2ɾw₌}h

This program involves exhaustively examining every coordinate list, making it impractical to run within a reasonable timeframe, even for the smallest input value of \$n = 5\$.

Should output a 1-indexed coordinate list.

Try it Online!

Explanation

ẊṖΩᵃȧᵛSu2ɾw₌}h­⁡​‎‏​⁢⁠⁡‌⁢​‎‎⁡⁠⁡‏⁠⁠‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢‏⁠⁠‏​⁡⁠⁡‌⁤​‎⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏⁠⁠⁠‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏⁠‎⁡⁠⁢⁡⁢‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠⁠‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠⁠‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁢⁤‏⁠⁠‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏⁠⁠⁠⁠‎⁡⁠⁤⁤‏‏​⁡⁠⁡‌⁣⁡​‎⁠‎⁡⁠⁤⁢‏⁠‎⁡⁠⁤⁣‏⁠‎⁡⁠⁢⁡⁣‏‏​⁡⁠⁡‌­
                # ‎⁡implicitly push input onto stack
Ẋ               # ‎⁢generate all coordinates (cartesian product of [1;n] with [1;n])
 Ṗ              # ‎⁣all permutations of the coordinates
  ΩᵃȧᵛSu2ɾw₌}   # ‎⁤filter for knight tours:
   ᵃȧ           # ‎⁢⁡  absolute difference between adjacent coordinates
     ᵛS         # ‎⁢⁢  sort each coordinate
       u        # ‎⁢⁣  uniquify all coordinates
         ɾw₌    # ‎⁢⁤  equals [[1, 2]]
             h  # ‎⁣⁡first element of filtered permutations
💎

Created with the help of Luminespire.


Note: This is one of my first Vyxal programs, and given that it won't run in a reasonable amount of time for even the smallest input, it is very possible I have made a mistake in the code

\$\endgroup\$
8
  • \$\begingroup\$ Absolute difference between adjacent coordinates gives false positives like [3, 3] [2, 5] -> [1, 2]. You have to take the simple difference, and check for either [1, 2] or [-1, -2]. Or, just take the product like in my solution \$\endgroup\$ Commented Feb 1 at 18:32
  • \$\begingroup\$ In Vyxal, numbers are in many cases automatically converted to ranges, so you don’t need the first byte. You could get 1 2; with . \$\endgroup\$ Commented Feb 1 at 18:43
  • 1
    \$\begingroup\$ @noodleman, I am having some trouble understanding the first comment, shouldn't all 8 differences [1, 2], [-1, 2], [1, -2], [-1, -2], [2, 1], [-2, 1], [2, -1], [-2, -1] for each possible knight moves be valid? \$\endgroup\$ Commented Feb 1 at 18:49
  • \$\begingroup\$ Ah, you’re correct, my mistake \$\endgroup\$ Commented Feb 1 at 18:52
  • \$\begingroup\$ You can remove the first ɾ, as I was getting at in my first comment. λ ... }F can be Ω ... }. \$\endgroup\$ Commented Feb 2 at 0:24
3
\$\begingroup\$

JavaScript (ES6), 141 bytes

Returns a list of 0-indexed coordinates as a single string.

f=(n,x=0,y=0,o="",k=n*n)=>x/n|y/n||(o+=p=` ${[x,y]} `).match(p+".|-")?0:--k?[...s="01344310"].some((d,i)=>f(n,d-2+x,s[i+6&7]-2+y,o,k))&&O:O=o

Try it online!

Commented

f = (                   // f is a recursive function taking:
  n,                    //   n = input
  x = 0, y = 0,         //   (x, y) = current position
  o = "",               //   o = output string
  k = n * n             //   k = move counter
) =>                    //
x / n |                 // if x >= n
y / n ||                // or y >= n
( o += p =              // or the updated output obtained by adding
  ` ${[x,y]} `          // the new position p = x,y surrounded by spaces
).match(                // contains:
  p + ".|-"             //   either p followed by any character
                        //   or the minus sign
) ?                     // then:
  0                     //   abort
:                       // else:
  --k ?                 //   decrement k; if it's not 0:
    [...s = "01344310"] //     s = offset sequence
    .some((d, i) =>     //     for each value d at index i in s:
      f(                //       do a recursive call:
        n,              //         pass n unchanged
        d - 2 + x,      //         update x
        s[i + 6 & 7] -  //         use the shifted sequence "10013443"
        2 + y,          //         to update y
        o,              //         pass the new output
        k               //         pass the updated counter
      )                 //       end of recursive call
    )                   //     end of some()
    && O                //     if truthy, return O
  :                     //   else:
    O = o               //     success: save o in O

JavaScript (ES8), 151 bytes (faster)

Returns a matrix with 0-based indexing.

n=>(m=[...s="".padEnd(n)].map(_=>[...s]),g=(x,y,k)=>!(m[y][x]=--k)|m.some((r,Y)=>r.some((v,X)=>v|(X-x)**2+(Y-y)**2-5?0:g(X,Y,k)))?m:m[y][x]=0)(0,0,n*n)

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 77 bytes

NθFθFθ⊞υ⟦⁰ικ⟧Fυ⊞ιΦυ⁼⁵ΣXEι∧ν⁻§κνμ²≔⟦§υ⁴⟧υ≔⟦⟧ηW⌊υ«⊞ηι≔⁻⊟ιηυFυ§≔κ⁰L⁻§κ³η»Eη⭆¹✂ι¹

Try it online! Link is to verbose version of code. Outputs a list of 0-indexed coordinates. Explanation: Uses Warnsdorff's rule, but always starting from [0, 4], because the rule won't work starting at the corner of the size 11 board.

NθFθFθ⊞υ⟦⁰ικ⟧

Input n and create a "board" of squares, with each square initially represented by its unvisited neighbour count and co-ordinates.

Fυ⊞ιΦυ⁼⁵ΣXEι∧ν⁻§κνμ²

Loop over the board, calculating the list of neighbours of each square.

≔⟦§υ⁴⟧υ

Start with [0, 4] as a potential next square, to work around the case of the size 11 board. (Otherwise this line of code would have been unnecessary.)

≔⟦⟧η

Start with no squares visited yet.

W⌊υ«

Until there are no squares left to visit, get the one with the fewest unvisited neighbours.

⊞ηι

Save this to the tour of visited squares.

≔⁻⊟ιηυ

Get the list of unvisited neighbours of the current square.

Fυ§≔κ⁰L⁻§κ³η

Update the number of unvisited neighbours for each unvisited neighbour.

»Eη⭆¹✂ι¹

Pretty-print the final tour.

\$\endgroup\$
2
\$\begingroup\$

Haskell + hgl, 37 bytes

g1(mF(fe[(1,2),(2,1)])<δ')<pm<j2q<e1

This is horrendously slow. It's time complexity is \$\mathcal O(4^n! 4^n)\$ (careful analysis might show that this bound could be lowered) on the number of bits in input. I've only been able to get it to halt for cases where \$n < 4\$, so I've never observed it produce a correct output.

Explanation

  • e1: enumerate from 1 to the input
  • j2q: get the cartesian product of this with itself to get the coordinates of the board
  • pm: get all permutations of the input
  • g1: get the first permutation satisfying a predicate
  • δ': get the absolute difference between consecutive elements
  • mF$fe[(1,2),(2,1)]: check if they are (1,2) or (2,1).

In summary this searches through all the permutations for one that consists solely of knights moves.

Reflection

At some point in the future there will be some graph utility functions, which would be able to handle this sort of thing not only shorter, but faster. But that's a bit of a long term requirement.

Here are some short term possibilities:

  • There should be something along the lines of "apply this function or not", currently it seems the way to do this is ap[f,id] which is pretty long.
  • There should be a function to determine if all elements of one list belong to another.
\$\endgroup\$
1
\$\begingroup\$

Python 3.8 (pre-release), 123 bytes

f=lambda n,x=0,*p:x%(y:=n+2)<n>x/y>=(x in p)<1and max((f(n,x+b,x,*p)for a in(n+4,n,n+n+5,n+n+3)for b in(a,-a)),key=len)or p

Try it online!

Brute force approach, an adaptation of my answer to Holey Knight's Tour.

Essentially, the board is a 1D-representation of a 2D padded grid. The horsey will hop recursively over the board while avoiding the padding and keeping track of the current (x) and previously visited (p) squares.

Coordinates are 0-indexed and 1-dimensional from left to right and top to bottom, with a gap of 2 indices at the edges. That is, for a 5x5 grid:

 0  1  2  3  4
 7  8  9 10 11
14 15 16 17 18
21 22 23 24 25
28 29 30 31 32
\$\endgroup\$

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.