Find the number of paths in a n×n grid

Question

Information

• Given a non-negative odd integer (let's call it \$n\$), find the number of all possible paths which covers all squares and get from the start to end on a grid.
• The grid is of size \$n\$×\$n\$.
• The start of the path is the top left corner and the end is the bottom right corner.
• You have to count the number of all paths which go from the start to end which covers all squares exactly once.
• The allowed movements are up, down, left and right.
• In other words compute A001184, but numbers are inputted as grid size.

Scoring

This is code-golf, write the shortest answer in bytes.

Test cases

1  → 1
3  → 2
5  → 104
7  → 111712
9  → 2688307514
11 → 1445778936756068
13 → 17337631013706758184626

Answer 1

Python 3, 109 bytes

f=lambda n,x=0,*s:1-(x in s)and(x==n*n-1==len(s)or sum(f(n,x+a,x,*s)for a in(~x%n>0,x%n//-n,n,-n)if-1<x<n*n))

Try it online!

Port of my answer to Find the shortest route on an ASCII road. Brute forces all paths and returns the number of valid ones. Slow as molasses, though.

-4 bytes thanks to Jakque

-8 bytes thanks to att

Answer 2

Jelly, 21 bytes

æịþḶFµḢ;ⱮṖŒ!;€ṪƲIỊẠ€S

Try it online!

Takes forever for n>3 because it tries to generate all permutations of n**2-2 items.

æịþḶFµḢ;ⱮṖŒ!;€ṪƲIỊẠ€S    Monadic link. Input: n
æịþḶF                    Generate complex numbers (1..n)+(0..n-1)i
     µḢ;ⱮṖŒ!;€ṪƲ         Generate all permutations with 1st and last fixed:
      Ḣ;Ɱ                  Chain 1st to each of...
         ṖŒ!;€               Permutations of the middle with...
              ṪƲ               The last chained to the end of each
                IỊẠ€S    Count those whose pairwise distances are all 1

Answer 3

Python 3, 185 bytes

def f(n):k=range(n);v=[-~x+y*1j for x in k for y in k];return sum(all(abs(z-y)<=1for y,z in zip(x,x[1:]))for x in[[1]+[*q]+[v[-1]]for q in permutations(v[1:-1])])
from itertools import*

Try it online!

@Bubbler's Jelly answer port

-3 thanks to @KevinCruijssen

Answer 4

05AB1E, 27 bytes

LD<⩨¦œε®нš®θªü2€øÆnOtΘP}O

Try it online!

Basic idea is like Bubblers, represent the grid as complex numbers, jumble all the intermediate cells between the first and last, and compute their distances and check if they are adjacent

a byte save thanks to @KevinCruijssen

Explanation (pseudo-code)

range
dup
decrement
cartesian product
copy to register (no pop)
cut tail
behead
permutations
map
  push register
  head
  prepend
  push register
  tail
  append
  cumulative pairs
  map
    zip
  deltas
  square
  sum
  square root
  equals 1?
  product
end map
sum

Answer 5

Wolfram Language (Mathematica), 58 bytes

-3 bytes thanks to @att.

Length@FindPath[GridGraph@{#,#},1,#^2,{#^2-1},All]/. 0->1&

n = 7 takes 3 minutes on my computer.

Try it online!

Answer 6

05AB1E, 36 33 bytes

nÍLœε0šZ>ªü2εDI÷ËiÆëI‰ø`ËsÆ*]ÄPΘO

Brute-force approach generating permutations of the grid (minus first and last item), so times out for anything \$n>3\$ (\$n=3\$ takes about 5 seconds).

Try it online.

Explanation:

Step 1: Generate all permutations of the list \$[1,n^2-2]\$, and prepend a leading \$0\$ and trailing \$n^2-1\$ to each:

n                 # Push the square of the (implicit) input-integer
 Í                # Decrease it by 2
  L               # Push a list in the range [1,n²-2]
   œ              # Pop and push all permutations of this list
    ε             # Map each permutation-list to:
     0š           #  Prepend a leading 0
       Z          #  Push the maximum (without popping the list)
        >         #  Increase it by 1
         ª        #  And append it as trailing item

Try just the first step.

Step 2: Check for each list whether it's a valid path:

ü2               #  Create overlapping pairs of the current list
  ε              #  Inner map the list of pairs to:
   D             #   Duplicate the current pair
    I÷           #   Integer-divide both integers in this copy by the input-integer
      Ëi         #   If both are the same (they're in the same row of the grid):
        Æ        #    Reduce the current pair by subtracting
       ë         #   Else:
        I‰       #    Divmod both integers in the current pair by the input-integer
          ø      #    Zip/transpose; swapping rows/columns
           `     #    Pop and push both pairs separated to the stack
            Ë    #    Check if the top pair (the [a%input,b%input]) are both the same
             s   #    Swap to get the other pair (the [a//input,b//input])
              Æ  #    Reduce it by subtracting
               * #    Multiply it to the a%input==b%input check
]                # Close the if-else statement and nested maps
 Ä               # Take the absolute value of each innermost integer
  P              # Taking the product of each inner list
   Θ             # Check for each if it's equal to 1 (1 if 1; 0 if not)

The I÷Ë checks if the integers in the current pair are in the same row of the grid, and with Æ + Ä it checks if their absolute difference is 1.
For any remaining pair that are not in the same row, the I‰ø`ËsÆ* + Ä checks if the two integers are in the same column and their absolute (vertical) difference is also 1.
The P after the map then checks if this was truthy for all of the pairs in the list.

Try the first two steps.

Step 3: Check how many valid paths were valid after the map, and output it as result:

O                 # Pop and sum to get the amount of valid paths
                  # (which is output implicitly as result)

Answer 7

Charcoal, 82 bytes

ＮθＵＯθ#Ｊ⊖θ⊖θＰ0⊞υ⌕ＡＫＶ#≔⁰ηＷυ«≔⊟υι¿ι«⊞υι≔⊟ιιＭ✳⁻χ⊗ιＰＩι⊞υ⌕ＡＫＶ#»«≧⁺¬∨∨ⅈⅉ№ＫＡ#η✳⁻⁶⊗ＫＫ#»»⎚Ｉη

Try it online! Link is to verbose version of code. Will do n=5 on TIO but larger numbers are probably too slow. Explanation: Works by counting the paths from the bottom right corner back to the top left corner of an n×n square drawn on the canvas.

Ｎθ

Input n.

ＵＯθ#

Draw an n×n square of #s.

Ｊ⊖θ⊖θＰ0

Start at the bottom right corner. (Any digit works here, it's just a placeholder showing that the square has been visited.)

⊞υ⌕ＡＫＶ#

Start with the possible moves from the corner. (This is empty for n=1 of course.)

≔⁰η

Start with 0 paths found.

Ｗυ«

Repeat until all paths have been attempted.

≔⊟υι

Pop the remaining moves to try from the current cell from the stack.

¿ι«

If there are any moves left, then:

⊞υι

Push the moves back to the stack again.

≔⊟ιι

Pop the next move to try.

Ｍ✳⁻χ⊗ι

Move in that direction.

ＰＩι

Overwrite the current cell with the direction, so that we can find our way back, and also so that we don't try to re-enter the cell.

⊞υ⌕ＡＫＶ#

Push the available moves from this cell to the stack.

»«

Otherwise:

≧⁺¬∨∨ⅈⅉ№ＫＡ#η

If the current cell is at the top left and there are no #s left indicating that we've covered all of the squares, then increment the count of paths found.

✳⁻⁶⊗ＫＫ#

Overwrite the current cell with a # and move back to the previous cell.

»»⎚Ｉη

Clear the canvas and output the number of paths found.

Answer 8

Python 3, 138 bytes

f=lambda n,a={0},x=0,y=0:n==len(a)/n<x+2<y+3or sum(f(n,a|{(x,y)},i,j)for i in range(n)for j in range(n)if(x-i)**2+(y-j)**2==1and{(i,j)}-a)

Try it online!

returns True for f(1)

How it works :

take as input :

• n the size of the grid
• a={0} the set of all visited positions initialized with a 0 to avoid typing set()
• x=0,y=0 the current position in the grid

then :

• n==len(a)/n<x+2<y+3 verify if we visited all positions and if we are in the bottom right of the grid

• f(n,a|{(x,y)},i,j)for i in range(n)for j in range(n) if recursively call f with all the position verifying

  • (x-i)**2+(y-j)**2==1 the position is at distance 1 of (x,y)
  • {(i,j)}-a the position is unvisited