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?