1
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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 ? $\endgroup$ – Peter Oct 5 '17 at 11:30
  • 2
    $\begingroup$ And what about $$.....$$ $$...3.$$ $$.....$$ $$U1...$$ $$2....$$ ? $\endgroup$ – Peter Oct 5 '17 at 11:33
  • $\begingroup$ @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. $\endgroup$ – aschultz Oct 5 '17 at 12:21
2
$\begingroup$

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$

$\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.