9
\$\begingroup\$

Background

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.

Challenge

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):

  <------N------>
  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.

\$\endgroup\$
4
  • \$\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
    Jul 9 '20 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
    Jul 9 '20 at 8:26
  • 2
    \$\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
    Jul 9 '20 at 8:43
  • \$\begingroup\$ this is now oeis.org/A338426 \$\endgroup\$
    – ZaMoC
    Oct 27 '20 at 22:00

11 Answers 11

7
\$\begingroup\$

Wolfram Language (Mathematica), 76 72 bytes

LinearRecurrence[{6,12,-27,2,30,4,-6},{0,0,1,2,3,29,155}-6/5,{#+4}]+1/5&

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.

\$\endgroup\$
1
  • 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\$ Jul 9 '20 at 17:31
4
\$\begingroup\$

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:
    p==3*n+4
        and c+6>>3*n+3 # return 1 if all cells passed through else 0
    or
    # else return sum of:
     sum(
        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)
        and~c&(-p>~n*3)<<p
    )
)
\$\endgroup\$
2
  • \$\begingroup\$ I think 254&1<<p%3*3+d%3 can be replaced by (p%3*3+d%3)%8. \$\endgroup\$
    – ovs
    Jul 9 '20 at 7:44
  • \$\begingroup\$ And -p>~n*3 instead of p<3*n+3. \$\endgroup\$
    – ovs
    Jul 9 '20 at 7:45
4
\$\begingroup\$

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.

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

05AB1E, 26 bytes

_i1ëL3LâœʒθнQyннyüα2‹PPP}g

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\$).

Explanation:

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)
\$\endgroup\$
2
\$\begingroup\$

Brachylog, 40 bytes

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

0+₁|{;3⟦₁ᵐẋp{hh1&b;?zk{\-ᵐȧᵐ≤ᵛ1}ᵐ&th}?}ᶜ

Try it online!

How it works

0+₁|

If input is zero, return 1. Otherwise …

{…}ᶜ

Count all …

;3⟦₁ᵐẋ

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

p{ … }

permutations that fulfill:

hh1

The first point's x coordinate must be 1

&b;?zk

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

{\-ᵐȧᵐ≤ᵛ1}ᵐ

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.

&th}?

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

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

Charcoal, 128 bytes

Nθ⊞υE⁺³θ⁰⊞υE⁺³θ∧›ι¹‹ι⁺²θ⊞υE⁺³θ›ι¹⊞υ§υ¹⊞υ§υ⁰≔⟦E³∨ιυ⟧υ≔⁰ηFυF…·⊖§ι²⊕§ι²F…·⊖§ι¹⊕§ι¹F§§§ι⁰κλ¿‹λ⁺²θ⊞υ⟦E§ι⁰Eν∧∨⁻ξκ⁻ρλπλκ⟧≧⁺¬⊖ΣE§ι⁰ΣνηIη

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:

Nθ

Input n.

⊞υE⁺³θ⁰⊞υE⁺³θ∧›ι¹‹ι⁺²θ⊞υE⁺³θ›ι¹⊞υ§υ¹⊞υ§υ⁰

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

≔⟦E³∨ιυ⟧υ

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

≔⁰η

Start with zero successful paths.

FυF…·⊖§ι²⊕§ι²F…·⊖§ι¹⊕§ι¹F§§§ι⁰κλ

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 ...

⊞υ⟦E§ι⁰Eν∧∨⁻ξκ⁻ρλπλκ⟧

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

≧⁺¬⊖ΣE§ι⁰Σνη

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

Iη

Print the final count of successful paths.

\$\endgroup\$
1
  • 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
    Jul 9 '20 at 20:01
1
\$\begingroup\$

R, 191 168 bytes

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

f=function(p=-1,m=rep(0,3*n),n){if(p>0)m[p]=1		
`if`(all(m),p/3>n-1,`if`(!sum(q<-!m[a<-(a=p+(-4:4)[!!c((p+2)%%3,1,(p+3)%%3)])[a>0&a<=3*n]]),0,sum(sapply(a[q],f,m,n))))}

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(sum(sapply(split(a,seq(q))[q],f,m,n)))
                                                    # return the sum of all valid paths from here
                                                    # by recursively calling self with each new position
        }
    }
}   
\$\endgroup\$
1
\$\begingroup\$

Jelly, 28 25 27 bytes

Rp3Ḷ¤Æị€;ıŒ!ISḞ=ʋƇ³IA<2ẠƲƇL

or

Ḷp3R¤Æị€Œ!ISḞ=ʋƇ’IA<2ẠƲƇL+¬

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Ḷ¤Æị€;ıŒ!ISḞ=ʋƇ³IA<2ẠƲƇL
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
\$\endgroup\$
2
  • \$\begingroup\$ It gives an error for n=0 (it's an annoying edge case that wasted 4 bytes in my answer as well.. :/) \$\endgroup\$ Jul 9 '20 at 9:44
  • \$\begingroup\$ @KevinCruijssen Fixed, either by manually adding one or taking permutations of the list including the start point. \$\endgroup\$ Jul 9 '20 at 16:16
1
\$\begingroup\$

JavaScript (ES6),  82  79 bytes

This is using @user202729's linear recurrence.

f=n=>([5,5,6,7,8,34,160][n+3]||[6,12,-27,p=2,30,4,-6].map(c=>p+=c*f(--n))&&p)-6

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Husk, 22 bytes

#¹mo→→fΛδΛ≈fȯε→←P¤×eḣ3

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

Explanation

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.
\$\endgroup\$
0
\$\begingroup\$

R+gtools, 147 bytes

n=scan();m=3*n;`if`(!n,1,sum(apply((p=permutations(m,m,complex(m,rep(1:n,e=3),1:3)))[Re(p[,1])<2&Re(p[,m])==n,],1,function(x)all(abs(diff(x))<2))))

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.

\$\endgroup\$

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.