Connecting dots in order on a grid

Question

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?

Answer 1

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$