Generating hard puzzles for a backtracking snake
Here's an idea for generating instances with a non-unique solution that will be difficult to solve by backtracking but actually are quite easy to solve:

Let $M$ be $h$ tall and $2w$ wide. Take the integers ${1, 2, ... w}$ and fill $M$ with them randomly. For $i = 1$ to $w$, replace column $w + i$ to be the column with only the value $i$.

We know that $M$ has no solution, because it requires $2w$ unique integers to bring the snake across the matrix.

Now, for the first $w$ columns of $M$, replace a random element of column $i$ with the number $w + i$.

Then, it follows that the sequence of integers corresponding to any solution is $w + 1, w + 2 .... 2w, 1, 2, ...... w$. This is very easy to find, unless you are searching by backtracking. In particular, the first $w$ columns have a unique correct choice.

Here's an example of a matrix made by this algorithm:

$$ \begin{array}{ccc}
1 &amp; 5 &amp; 2 &amp; 1 &amp; 2 &amp; 3 \\
3 &amp; 3 &amp; 2 &amp; 1 &amp; 2 &amp; 3 \\
4 &amp; 1 &amp; 1 &amp; 1 &amp; 2 &amp; 3 \\
2 &amp; 2 &amp; 2 &amp; 1 &amp; 2 &amp; 3 \\
2 &amp; 3 &amp; 6 &amp; 1 &amp; 2 &amp; 3 \\
3 &amp; 1 &amp; 3 &amp; 1 &amp; 2 &amp; 3 \\
1 &amp; 1 &amp; 1 &amp; 1 &amp; 2 &amp; 3 \\ \end{array} $$

To make a given instance harder, just make the matrix arbitrarily taller.