Where is that snake going? Write a function (using as few bytes as possible) that takes a bi-dimensional array of any number of columns and rows in which:


0 represents empty block, 
1 represents snake block. 


The function must return the number of possible paths the snake traveled.

Example 1:

Input:

[
  [1,1,1,1,1],
  [0,0,0,0,1],
  [0,0,0,0,1],
]


Output: 2

In the example above, the function will return 2 because the answer is either one of:



Example 2:

Input:

[
  [1,1,1,1],
  [0,0,1,1],
  [0,0,1,1],
]


Output: 6

In this example the function will return 6 because the answer is either one of:



Note: 

When assessing the input, you can assume that:


The arrays representing columns will always have the same sizes (so the arrays are rectangular);
There exists at least 1 valid path;
The snake cannot walk through the edges (as can happen in some versions of snake);
The snake will always have at least 2 blocks;
The snake cannot move diagonally;
The paths are directed. (so, two paths ending at different positions but otherwise looking exactly the same are not the same path, it’ll add up to the total)
Wolfram Language (Mathematica), 16+83=99 bytes

Library import statement (16 bytes):

&lt;&lt;Combinatorica`


Actual function body (83 bytes):

Length@HamiltonianCycle[MakeGraph[#~Position~1~Join~{1&gt;0},##||Norm[#-#2]==1&amp;],All]&amp;


Try it online!



Note that the question just ask for the number of Hamiltonian path in the graph.

However, (for some reason) the HamiltonianPath function doesn't really work with directed graph (example). So, I used the workaround described in this Mathematica.SE question:


Add an vertex (called True) that is connected to all other vertices.
Count the number of Hamiltonian cycle on the resulting graph.


The graph is constructed using MakeGraph (annoyingly there are no directly equivalent built-in), using the boolean function ##||Norm[#-#2]==1&amp;, which returns True if and only if one of the arguments is True or the distance between the two vertices are 1.



Tr[1^x] cannot be used instead of Length@x, and &lt;2 cannot be used instead of ==1.



HamiltonianPath can be used if the graph is undirected, with the function body takes 84 bytes (exactly 1 byte more than the current submission):

Length@HamiltonianPath[MakeGraph[#~Position~1,Norm[#-#2]==1&amp;,Type-&gt;Undirected],All]&amp;


Try it online!