Achefe

How many paths the snake in the Snake game can take? I was given this challenge last week and I thought I would share my way of solving it with you all Y'all know the famous game "Snake", so no need for an introduction now. The question is easy: given the position of the snake within a map of known size and the number of movements the snake can do, how many distinct paths can the snake follow without intersecting itself and without going out of the map's boundaries? Maybe once you go over it the question is not as easy as it sounds, so let's illustrate it with an example. Let's imagine we have a map that contains 4 rows and 3 columns, like the one below. And let's imagine that we have a snake whose body occupies the following cells: [(2,2),(3,2),(3,1),(3,0),(2,0),(1,0),(0,0)]. The figure on the left represents the empty map and the one on the right represents the one with the snake, where the numbers are the positions of each "piece" of the snake