# Connecting dots in order on a grid

I wrote a mini-game where you are on a 5x5 grid and need to pick up 3 items in order without going through any location twice. Most of the times, the random distributions for your starting point and the item locations worked okay.

But I found one that didn't, and I want to be able to check for that and re-distribute the items and starting location until there's a winnable position, without eliminating arrangements that are solvable.

Now, (and a comment and answer called attention to a problem in my initial question) your initial position and the position of 1/2/3 are dictated thus: if the 5x5 board is a checkerboard, and black is in the upper left, then U must be on a white square, and 1/2/3 must be on black squares. I wanted to put U on a white square so it would be possible to traverse the whole board.

So this could not be generated:

1....
U2...
3....
.....
.....


And neither would this impossible case, since 1 is in the wrong position:

.....
.....
.....
3U...
12...


But this could be:

.3...
.....
....U
....2
.1...


My hypothesis is that the game is unwinnable if and only if

• all four points are on the edge of the grid
• they are such that the straight line 3-2 would intersect the straight line U-1 (note this would include the tricky looking boundary case where they are all on one edge or 3-2 goes through U)

I'm falling down on why this has to be true, though. It looks intuitive ("any path from U to 1 not touching 2 cuts the board in half, separating 2 and 3, QED,") but that's not good enough. Is there a rigorous way to prove this?

• If I understand the rules and the claim correct, the unwinniable position $$.....$$ $$.....$$ $$.....$$ $$...1.$$ $$..3U2$$ is a counterexample since not all points are on the edge. Do I miss something ? – Peter Oct 5 '17 at 11:30
• And what about $$.....$$ $$...3.$$ $$.....$$ $$U1...$$ $$2....$$ ? – Peter Oct 5 '17 at 11:33
• @Peter no, you didn't. I thought I could simplify the problem this way, but it turns out that I had more restraints on the original coordinates than I thought. The main thing is this: if the grid is a checkerboard with the upper left being black, then 1/2/3 are on white squares and U is always on a black square. I should probably re-check and update the question once I'm sure what's going on. Thanks for pointing this out. – aschultz Oct 5 '17 at 12:21

Some special cases to consider:

.....    .....
...3.    ...U.
.....    .....
.1...    .2...
...U2    ...31


Some hints:

• Suppose you were to color $\color{red}{\text{red}}$ vertices $\color{red}{1}$ and $\color{red}{U}$ and $\color{blue}{\text{blue}}$ vertices $\color{blue}{2}$ and $\color{blue}{3}$.
• What you would get is similar to the game of hex, and you might be interested in the proof that it always has a winner. You could use a similar technique to prove "unwinnable if".
• The "winnable if" could be proven by an algorithm to find a path.
• Precise formulation should highlight all the special cases like @Peter's and the above (you will need to alter your theorem to account for them).

I hope this helps $\ddot\smile$