# Generating hard puzzles for a backtracking snake

Let $M$ be a matrix of height $h$ and width $w$. Each entry of $M$ is an integer.

There is a snake that starts from the "left side" of $M$, and its goal is to reach the "right side" of $M$. To get from one side to the other, i.e. to move from column $c$ to column $c+1$, the snake must choose an integer from both. Whatever the snake picks from column $c$, it can never pick the same integer again in $c+1$, nor from any column that appears later.

For example, suppose each entry in column 1 has integer 1, each entry in column 2 has integer 2, and so on. Now the snake can move very freely: in fact, we have $h$ choices in each of the $w$ columns. Even a blind snake gets through the matrix easily.

The goal is to generate matrices that are difficult for a snake that performs some kind of exhaustive backtracking search. The matrices can be tall, but preferably not wide. Can we assign the integers to $M$ such that there is exactly one (i.e. a unique) path through it? The hope is matrices with unique valid paths through them are difficult 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 & 5 & 2 & 1 & 2 & 3 \\ 3 & 3 & 2 & 1 & 2 & 3 \\ 4 & 1 & 1 & 1 & 2 & 3 \\ 2 & 2 & 2 & 1 & 2 & 3 \\ 2 & 3 & 6 & 1 & 2 & 3 \\ 3 & 1 & 3 & 1 & 2 & 3 \\ 1 & 1 & 1 & 1 & 2 & 3 \\ \end{array}$$

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