A snake is a path over the cells of a square grid, such that it doesn't touch itself on a side of a unit square. Touching at a corner is allowed.

An example snake:


Some example non-snakes:





Given an empty grid with the two endpoints of a snake marked on it, find the longest possible snake that fits on the grid. If there are multiple answers having the same length, you may choose to output one or all of them.

The input can be given as a character matrix (or equivalent) with two endpoints marked on it, or the dimensions (width, height) and the coordinates of the endpoints. You may choose to output the grid containing the snake or a list of coordinates of cells occupied by the snake (or equivalent).

Standard rules apply. The shortest code in bytes wins.

Example I/O

Each I/O example is given as a character matrix, # being the part of the snake.


Input: (corner case)
Output: same as input (no way to get longer without violating no-touch condition)


  • 2
    \$\begingroup\$ I feel like shortest code here would be to generate all the possible solutions and then just pick one with longest snake \$\endgroup\$
    – NoOorZ24
    Commented Jun 3, 2020 at 12:26
  • \$\begingroup\$ Can we input the endpoint positions as x+w*y (that is, their positions in row-major order)? \$\endgroup\$ Commented Jun 3, 2020 at 16:26
  • \$\begingroup\$ @mypronounismonicareinstate No. \$\endgroup\$
    – Bubbler
    Commented Jun 4, 2020 at 6:55
  • \$\begingroup\$ Can the input endpoints be marked in different characters? \$\endgroup\$
    – Neil
    Commented Jun 5, 2020 at 21:09

6 Answers 6


Python 3.8 (pre-release), 207 194 181 bytes

-7 bytes thanks to @ovs


The width \$ w \$, the height \$ h \$, the starting point \$ s \$, and the ending point \$ e \$. \$ s \$ and \$ e \$ are complex numbers which represent the coordinates of the endpoints.


A list of points, in the form of complex numbers.

def f(w,h,s,e):P=[[s]];exec("P=[j+[t+(t==e==(A:=j+[t]))]for j in P for k in C if w>(t:=j[-1]+k).real>-1<t.imag<h>0<all({t+l}-{*j}for l in{0}|C-{-k})];"*w*h);return A

Try it online!


We use a breadth-first search to search for all possible snakes, starting at \$ s \$, making sure that the next tile is not adjacent to any previous tile, and that we do not go past the boundary. After each iteration, we check for all paths whose last element is \$ e \$, meaning that we have found a complete path from \$ s \$ to \$ e \$. Instead of storing all complete paths and returning the one with maximum length, we can simply return the last path found, since breadth-first search already searches for paths by length.

  • \$\begingroup\$ -7 by replacing the inner for-loop with [j[-1]==e!=(A:=j)for j in P]. \$\endgroup\$
    – ovs
    Commented Jun 4, 2020 at 6:39
  • \$\begingroup\$ @ovs Thanks for the improvement :) \$\endgroup\$ Commented Jun 4, 2020 at 17:17

R, 275 272 251 229 206 197 bytes


Try it online!

Edits 1-4: -69 bytes by using increasingly-arcane golfing obfuscations

Edit 5: -9 more bytes by removing useless explicit return of NULL for 'touching' cases, and instead just falling-off the end of the function

Recursive function:

  • find adjacent squares
  • count touching squares
  • mark position (differently to finish point)
  • if touching < 3 and we're touching the finish: return the matrix
  • else if touching > 1 (it's either a loop or an illegal position): return NULL
  • otherwise (there should always be at least one adjacent empty square left)
    • call self recursively with each adjacent empty square to get snakes from this position
    • return the longest snake

Code before golfing:


    # find adjacent squares
    adjacent_squares=lapply(list(-1:0,1:0,0:-1,0:1),function(p){n=pos+p;if(all(n>0 & n<=d)){n}})

    # count touching squares

    # mark current position (differently to end, which is 1)

    # if touching<3 & pos is touching finish => return matrix
    if((touching<3)&&any(adjacent_vals==1)){ return( matrix ) }

    # else if touching>1 then its either an illegal position or a loop  
    else if(touching>1){ return( NULL ) }

    else { # there should always be at least one adjacent empty square

        # now consider each of the adjacent empty squares
        new_pos=lapply(which(adjacent_vals==0),function(i) adjacent_squares[i,,drop=F])

        # get the longest snake from each of them

        # and return the longest of these

Python 3.8 (pre-release), 214 bytes

Takes a 1D boolean array g where the endpoints are marked True, and returns a 1D boolean array where snake tiles are marked True.

Try it online!

lambda w,h,g:max((list(map(v,range(w*h)))for x in range(2<<(w*h))if all((v:=lambda i:0<=i<w*h and(g[i]or x>>i&1))(i)==0 or(i%w>0 and v(i-1))+(i%w<w-1 and v(i+1))+v(i-w)+v(i+w)+g[i]==2 for i in range(w*h))),key=sum)


def f(w, h, g):
    return max(
            # Brute force all possible grid configurations by counting in binary.
            # For each iteration, let the ith binary digit of x signify
            # whether the ith tile is considered part of the snake.
            [v(i) for i in range(w*h)] # <- Return a boolean array.
            for x in range(2<<(w*h))

            # Check if there is a valid snake path.
            if all(
                # The ith tile is part of the path if it's a given endpoint (g[i])
                # or the ith binary digit of x is 1 (x>>i&1).
                ( v:=lambda i:0<=i<w*h and (g[i] or x>>i&1) )(i) == 0
                # For a grid to have a valid snake path,
                # every tile must either not be part of the snake (v(i) == 0)...
                # ...or the tile must have exactly 2 neighbors in the snake path.
                # (If the tile is an endpoint (g[i]), count itself as a neighbor.)
                (i%w>0 and v(i-1)) + (i%w<w-1 and v(i+1)) + v(i-w) + v(i+w) + g[i]
                == 2

                # Repeat this check for every tile.
                for i in range(w*h)

        # Use max() to find the grid configuration with the most snake tiles;
        # that is, the most times that v(i) == True.
  • 8
    \$\begingroup\$ Your conditions aren't sufficient. Certain illegal combination still satisfy the condition that each square is either 1) an endpoint, 2) isn't occupied or 3) has exactly two neighours. Disconnected loops for instance. A tiny modification of your test input shows that. I don't think you can solve this by looking locally, you need at least one global condition. \$\endgroup\$
    – Abigail
    Commented Jun 3, 2020 at 13:43

JavaScript (Node.js), 199 bytes


Try it online!

Seems this way is not that good one


Charcoal, 76 bytes


Try it online! Link is to verbose version of code. Takes input as two @ endpoints in a field of ASCII characters greater than # (e.g. .). Explanation:


Input the field.


Start a breadth-first search with an empty path, and for each path...


... search over the four possible paths formed by concatenating each direction.


Print the field and move to the position of the first endpoint.


Print the path.


Test whether the current position is legal (not off the edge, doubled back, or touching itself).


If we reached the other endpoint,


then overwrite it with a # and save the canvas.


Otherwise add this path to the search candidates.


Restore the canvas from the saved last (i.e. longest) path that reached the other endpoint.


R, 178 169 164 161 bytes

f=function(s,e,w,h,l=length,`/`=c,`*`=`%in%`,k=s[1]-1/-1i/-1/1i)if(!any(s[-2]*k))`if`(e*k,s/e,{for(j in k[Re(k)*1:w&Im(k)*1:h])if(l(F)<l(n<-f(j/s,e,w,h)))F=n;F})

Try it online!

This works with complex numbers, similarly to @dingledooper's answer. Inputs are 1-indexed coordinates of start and end points, as well as width and height of the grid. Output is a vector of points which form the snake.


f = function(s, e, w, h) # start, end, width, height
{ # Select points to try at next iteration as neighbors of the snake head cell:
  k = s[1] + c(-1,1i,1,-1i) 
  # To avoid touches, only proceed if none of k points are already in snake:
  if(!any(s[-2] %in% k)) #s[2] is an exception - this is where we came from
    `if`(e %in% k, # If the neighbors include the endpoint, then...
      c(s,e)       # The loop is closed, add the endpoint to snake and return
      {# Loop through k, filtered so that all points fit in 1:w by 1:h grid:
        for(j in k[Re(k) %in% 1:w & Im(k) %in% 1:h])
        { # Prepend j to snake, and construct it further by recursive call:
          n <- f(c(j, s), e, w, h)
          if(length(F) < length(n))
            F = n # Select the longest snake that we encountered        
        F # Return the longest snake
  • \$\begingroup\$ You need to check for touches before checking you've reached the endpoint: otherwise, if they both happen at once, you'll accidentally register an 'illegal' snake like this \$\endgroup\$ Commented Jun 5, 2020 at 19:25
  • \$\begingroup\$ ...but, otherwise, the complex number-based indexing is very nice and I'm jealous I didn't think of it myself! \$\endgroup\$ Commented Jun 5, 2020 at 19:26
  • \$\begingroup\$ Well, technically the Python answer posted the same technique before me! Anyway, thanks for pointing the mistake, it looks like a direct swap of the order of conditions fixes it. \$\endgroup\$
    – Kirill L.
    Commented Jun 5, 2020 at 19:58
  • \$\begingroup\$ Wow - /=c is a super sneaky-trick! \$\endgroup\$ Commented Jun 6, 2020 at 9:57
  • \$\begingroup\$ (I tried to write that in a formatted way, but finding a valid combination of triple-backticks, escaped-backtick and escaped / character together got the better of me...) \$\endgroup\$ Commented Jun 6, 2020 at 10:00

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.