A Hamiltonian path is a path on a graph that steps through its vertices exactly once. On a grid, this means stepping through every cell exactly once.

On a square grid, a Chess King can move to a horizontally, vertically, or diagonally adjacent cell in one step.


Count the number of Hamiltonian paths using Chess King's moves through a square grid of 3 rows and N columns (denoted X below), starting at the left side of the entire grid (denoted S below) and ending at the right side (denoted E below):

  X X X ... X X X
S X X X ... X X X E
  X X X ... X X X

In other words, count all paths from S to E that passes through every X exactly once using only King's movements.

Standard rules apply. The shortest code in bytes wins. Kudos if you can solve this with short code in a way other than brute-forcing all possible paths.

Test cases

Generated using this APL code (equivalent Python 3 + Numpy) which I created by finding 15 possible states of the rightmost column and deriving a 15-by-15 transition matrix (figures up to N=3 are crosschecked with a pure brute-force Python).

N  -> Answer
0  -> 1
1  -> 2
2  -> 28
3  -> 154
4  -> 1206
5  -> 8364
6  -> 60614
7  -> 432636
8  -> 3104484
9  -> 22235310
10 -> 159360540

Thanks to @mypronounismonicareinstate and @ChristianSievers for confirming the test cases in the sandbox.

  • \$\begingroup\$ It seems like it would be really hard to get count paths in a way other than enumerating them. Maybe for 2-by-N there's some nice classification that leads to a formula. \$\endgroup\$
    – xnor
    Commented Jul 9, 2020 at 8:12
  • \$\begingroup\$ @xnor I tried it first, and it boiled down to power of 2 times fibonacci or something, which is... boring. \$\endgroup\$
    – Bubbler
    Commented Jul 9, 2020 at 8:26
  • 3
    \$\begingroup\$ Oh, I see it now. A 2-by-N path is specified by choosing non-overlapping pairs of adjacent columns for where the path doubles back left, which are counted by Fibonacci numbers, combined with specifying which of the two cells in each column is visited first, for a power of 2. Neat for combinatorics, boring for a golf challenge :) \$\endgroup\$
    – xnor
    Commented Jul 9, 2020 at 8:43
  • \$\begingroup\$ this is now oeis.org/A338426 \$\endgroup\$
    – ZaMoC
    Commented Oct 27, 2020 at 22:00

11 Answers 11


Wolfram Language (Mathematica), 76 72 bytes


Try it online!

The non-homogeneous linear recurrence equation is so much shorter to express that it saves a few bytes to modify the code to handle non-homogeneous linear recurrence.

More info: In this case, it cannot be represented as a polynomial. I tried to put the recurrence into RSolve, but it takes a long time to figure out the exact symbolic form (I terminate it before it completes), and I'm pretty sure that the required coefficients are irrational (approximate numerical formula can be obtained).

Returns a singleton list containing the result.

  • 2
    \$\begingroup\$ Indeed, the characteristic polynomial \$x^8-7 x^7-6 x^6+39 x^5-29 x^4-28 x^3+26 x^2+10 x-6\$ of the linear recurrence equals \$x-1\$ times an irreducible degree-7 polynomial, and so the exact formula will involve the degree-7 algebraic numbers that are the roots of this polynomial. \$\endgroup\$ Commented Jul 9, 2020 at 17:31

Python 2, 136 129 bytes

f=lambda n,c=0,p=1:p==3*n+4and c+6>>3*n+3or sum(f(n,c|1<<p,p+d-4)for d in range(9)if~47&1<<p+3and(p%3*3+d%3)%8and~c&(-p>~n*3)<<p)

Try it online!

-5 bytes thanks to @ovs

Performs a depth-first search starting at S and ending at E. The start position is encoded as p=1, and increase down and to the right, so the top row for n=4 is 0,3,6,9 and the bottom row is 5,8,11,14.

f=lambda n,c=0,p=1:(
    # if at final position:
        and c+6>>3*n+3 # return 1 if all cells passed through else 0
    # else return sum of:
        f(n,c|1<<p,p+d-4)  # ways from that point
        for d in range(9) # for all 9 points within distance 1
        if~47&1<<p+3 # except if off to the left

        and(p%3*3+d%3)%8 # or that would be walking off top or bottom
        # (-p>~n*3) # or off to the right
        # (if this evaluates False, then the next condition is ~c&0<<p, which always gives falsey 0;
        #  if this evaluates True, then the next condition is ~c&1<<p, which tests if location already visited)
  • \$\begingroup\$ I think 254&1<<p%3*3+d%3 can be replaced by (p%3*3+d%3)%8. \$\endgroup\$
    – ovs
    Commented Jul 9, 2020 at 7:44
  • \$\begingroup\$ And -p>~n*3 instead of p<3*n+3. \$\endgroup\$
    – ovs
    Commented Jul 9, 2020 at 7:45

Python 3, 104 bytes

f=lambda n,a=[154,28,2,1,0,-1,-1]:n and f(n-1,[sum(map(int.__mul__,a,(6,12,-27,2,30,4,-6)))-4]+a)or a[3]

Try it online!

Unlike Mathematica, Python doesn't have a built-in for linear recurrence equations, so calculating a homogeneous recurrence equation takes approximately the same number of bytes as a non-homogeneous one.

Alternative solution.


05AB1E, 26 bytes


Brute-force approach, so it's pretty slow. Also, 4 bytes are wasted on edge-case n=0.

Try it online or verify the \$[0,1,2]\$ test cases (times out for \$n\geq3\$).


In general:

  1. Get all possible coordinates based on the input \$n\$
  2. Get all permutations of these coordinates
  3. Filter this list of permutations and only keep those that satisfy:
    • The first coordinate in this permutation is in the first column
    • The last coordinate in this permutation is in the last column
    • The difference between each overlapping pair of coordinates in this permutation is 1 step (in either a horizontal, vertical, or (anti-)diagonal direction)
  4. Get the amount of valid permutations left to get the result
  5. (Fix edge case \$n=0\$.)
_i       # If the (implicit) input-integer is 0:
  1      #  Push 1 (which is implicitly printed as result)
 ë       # Else:
  L      #  Push a list in the range [1, (implicit) input]
   3L    #  Push list [1,2,3]
     â   #  Take the cartesian product of the lists to get all (1-based) coordinates
      œ  #  Get all permutations of these coordinates
ʒ        #  Filter the list of permutations by:
  н      #   Get the x-coordinate
 θ       #   of the last coordinate in this permutation
   Q     #   And check if it's equal to the (implicit) input-integer
 y н     #   Also get the x-coordinate
  н      #   of the first coordinate in this permutation
 yü      #   For each overlapping pair of coordinates:
   α     #    Get the absolute difference between the two: [|x1-x2|,|y1-y2|]
    2‹   #   Check for each difference in each pair if it's 0 or 1: [|x1-x2|<2,|y1-y2|<2]
      P  #   Check if both values within each pair are truthy: (|x1-x2|<2)*(|y1-y2|<2)
       P #   Check if all checks for each overlapping pair are truthy
 P       #   Get the product of all three checks (note: only 1 is truthy in 05AB1E)
}g       #  After the filter: get the amount of valid permutations by taking the length
         #  (which is output implicitly as result)

Brachylog, 40 bytes

Bruteforce for now. Times out on TIO for test cases > 2, but at least 3 was verified locally.


Try it online!

How it works


If input is zero, return 1. Otherwise …


Count all …


coordinates [[1,1],[1,1],[1,2],…,[N,1],[N,2],[N,3]]

p{ … }

permutations that fulfill:


The first point's x coordinate must be 1


Zip the permutation with itself shifted by one, drop the wrapped around. [[[1,1],[2,2]], …]


Check king moves: For each of the pairs, [[1,1],[2,2]] transpose [[1,2],[1,2]] subtract [-1,-1] absolute values [1,1] all of them must be less or equal than 1.


Also, the last point's x coordinate must unify with the input.


Charcoal, 128 bytes


Try it online! Link is to verbose version of code. Brute force version, because I haven't figured out a recurrence relation, assuming one is even possible. Explanation:


Input n.


Build up an array of unvisited squares, but with a border of 0s so the starting square is actually [2, 1] (and is visited).


Start a breadth-first search with this array and the starting square just mentioned.


Start with zero successful paths.


For each position, loop through all of the unvisited squares of the 3×3 square that has the current square at its centre.


If we have not reached the finish, then ...


... push the grid with this square visited plus the new position to the list of positions to search...


... otherwise if this is the last unvisited square then increment the number of successful paths.


Print the final count of successful paths.

  • 1
    \$\begingroup\$ JFTR, I found a counterexample to my original recurrence relation approach, so it was never going to work out. I still wonder how @Bubbler derived his transition matrix... \$\endgroup\$
    – Neil
    Commented Jul 9, 2020 at 20:01

R, 191 168 bytes

Edit: -23 bytes by switching to linear instead of matrix coordinates


Try it online!

Recursively tries all paths & counts-up those that end in last column & visit all positions.

Commented version:

paths=f=function(p=c(2,0),m=matrix(0,3,n),n){       # start at position 'S'; fill matrix with zeros
    m[t(p)]=1                                       # set visited positions to 1
    if(all(m)){                                     # visited all positions?
        if(p[2]==n){                                # if we're in the last column...
            return(1)}                              # ...then this is a valid path
        else{return(0)}                             # otherwise it isn't.  
    } else {                                        # if there are still some positions to visit:
        a=p+rbind(1:3,rep(1:3,e=3))-2               # a = all possible king moves...
        a<-t(a[,!colSums(a<1|a>dim(m))])            # ...limited to bounds of matrix
        q=!m[a]                                     # q = moves to unvisited positions
        if(!sum(q)){return(0)}                      # if we can't move, it's not a valid path
        else{                                       # if we can move...
                                                    # return the sum of all valid paths from here
                                                    # by recursively calling self with each new position

Jelly, 28 25 27 bytes




Try it online!

Not the most exciting answer: brute-forces all possible paths and times out on TIO for n>2.

+3 bytes for fixing n=0 case.

I have temporarily paused golfing since the bytecount reached f(2)=28.

Rp3Ḷ¤Æị€                       # Generate all points on a lattice from 1+0j to n+2j
        ;ı                     # Append 0+1j (start position)
          Œ!                   # Take all permutations
                ʋƇ             # Filter for
            ISḞ=  ³              # real(last-first)=n
                        ƲƇ     # Filter for
                   IA<2Ạ         # All moves have magnitude less than 2
                          L    # Length
  • \$\begingroup\$ It gives an error for n=0 (it's an annoying edge case that wasted 4 bytes in my answer as well.. :/) \$\endgroup\$ Commented Jul 9, 2020 at 9:44
  • \$\begingroup\$ @KevinCruijssen Fixed, either by manually adding one or taking permutations of the list including the start point. \$\endgroup\$ Commented Jul 9, 2020 at 16:16

JavaScript (ES6),  82  79 bytes

This is using @user202729's linear recurrence.


Try it online!


Husk, 22 bytes


Try it online!

It's just brute force, so not that fast, though TIO can handle \$n = 3\$. Husk's default return values line up nicely so that I don't waste any bytes special casing \$n = 0\$.


P¤×eḣ3  Generate all permutations of vertices.
 ¤   3  Apply to both 3 and n:
    ḣ   Range from 1.
  ×e    Cartesian product.
P       Permutations.
        For n=0 the range and the product are empty,
        and P gives [[]].
        Note that the second coordinates run from 1 to n.

f(ε→←)  Check initial vertex.
f(   )  Filter by condition:
    ←     First element.
   →      Last element of that
  ε       has absolute value at most 1.
        For n=0 the condition is checked for [],
        which is a list of lists of numbers.
        ← defaults to [], an empty list of numbers in this case.
        → defaults to 0 on it, and ε reports true.

fΛδΛ≈  Check adjacent vertices.
f      Filter by condition:
 Λ       For all adjacent pairs,
  δΛ     in both coordinates
    ≈    the values differ by at most 1.
       For the empty list, Λ is always true regardless of the condition.

#¹mo→→  Check last vertex.
  mo    Map
    →→  Last element of last element.
#¹      Count occurrences of n.
        The defaults work as with the initial vertex.

R+gtools, 147 bytes


Try it online!

Tests all permutations of coordinates as complex numbers, and counts those that start with Re=1, end with Re=n, and for which all steps have an absolute value less than 2.

I felt that I couldn't consider myself a 'real' code-golfer unless I'd submitted a ridiculously-inefficient 'brute-force' answer that would time-out with anything except the shortest input...

Completes on TIO for n up to 3.


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.