1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.