2
$\begingroup$

Say you have a grid of 16x16 squares. Label them A through P and 1 through 16.

Now say that at H8 there's a mouse that moves at 1 slot every turn. Also, you get to block a tile every turn.

Say the mouse gets to move first; can you, with perfect play by both you and the mouse, completely box the mouse in, before it escapes the board? If so, how, and how many turns will it take? If not, explain why.

BONUS: What is the smallest square board size (1x1, 2x2, 3x3, 4x4, 5x5, 6x6, etc.) for which this is possible? What's the largest that's impossible? You may assume the rules above apply, except the one about the mouse starting at H8; the mouse begins as close to the center as possible.

Improve this question
$\endgroup$
14
  • $\begingroup$ Can the mouse move diagonally? $\endgroup$
    – Rob Watts
    Commented Nov 20, 2014 at 21:48
  • $\begingroup$ @Rob Yes, he can move 1 space is any direction, like the king in Chess. $\endgroup$
    – warspyking
    Commented Nov 20, 2014 at 21:49
  • 1
    $\begingroup$ This is the Angel Problem for an angel of power one. This paper claims that a 32x33 board suffices. $\endgroup$
    – xnor
    Commented Nov 20, 2014 at 22:04
  • $\begingroup$ @xnor It also uses tiles not intersections, giving the ability of diagonal movement. $\endgroup$
    – warspyking
    Commented Nov 20, 2014 at 22:11
  • 1
    $\begingroup$ @warspyking I don't understand. The Angel Problem also uses King moves. $\endgroup$
    – xnor
    Commented Nov 20, 2014 at 22:13

3 Answers 3

Reset to default
0
$\begingroup$

If the mouse can move diagonally, you can't box it in, since the most efficient net would normally be a diagonal line. The king will move towards a corner, and since you have to cover 2 sides, you can't solid lines fast enough to hold the king in. If you do manage to get a solid line, the king can just move towards the short side diagonally.

If the mouse is not able to move diagonally, I would say that you would need to be able to put a blocking piece out just 3 spaces from the mouse, then box it in diagonally.

I think a winning strategy for the blocker involves a board at least 21 squares wide. Essentially, the mouse moves diagonally to a corner. If the blocker can get to this, I think he/she can win:

Blocking position

Improve this answer
$\endgroup$
3
  • $\begingroup$ Could you answer the bonus? $\endgroup$
    – warspyking
    Commented Nov 20, 2014 at 22:12
  • $\begingroup$ It looks good. +1 Accept! $\endgroup$
    – warspyking
    Commented Nov 20, 2014 at 22:46
  • 4
    $\begingroup$ This isn't right. It's well-known that you can hem in a mouse that makes King moves, as per the Angel of power one result. The key idea is to make a wall progressively, filling in every 8th square, then every fourth square, and so on, omitting squares not in the "cone" of threatened escape squares. $\endgroup$
    – xnor
    Commented Nov 20, 2014 at 23:01
8
$\begingroup$

The mouse can win on a 34x34 moving first, but will lose on a 35x35 board.

The proof of this is in Winning Ways for Your Mathematical Plays, Vol 3 (1982) by Berlekamp, Conway, and Guy. Here's the relevant extract, starting from "The Game of Kinggo", which is the same as the game in the question. Thanks to @Julian Rosen for tracking down this source.

The proofs are very intricate, and I'm sorry that I cannot summarize them. Perhaps someone with a better understanding can explain the general gist of the strategy.

The general version of this problem is known as the Angel Problem. It is known that an angel can escape indefinitely if it can make move to spaces up to two king's moves away.

Improve this answer
$\endgroup$
-1
$\begingroup$

The basic idea is as follows:

The mouse situated in H8 will run either upwards or to the left, as it will take it less moves to do so. Let us assume that the mouse runs left for this purpose. The most efficient way is to start by blocking up the outer wall to the left, leaving one block gaps between each block placed. By doing this, when the mouse reaches the left wall you may simply block off the holes before it attempts to go through them. By expanding this holed border around the back of the mouse, you can effectively box it in. I got the idea from an hour playing Circle the Dot.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is this with perfect play? $\endgroup$
    – warspyking
    Commented Nov 20, 2014 at 22:16
  • $\begingroup$ @warpsyking This is assuming that the mouse simply travels toward the nearest wall in attempt of leaving via that side, always following the shortest route to any exit. If the mouse was considered to play perfectly in regard to strategy, we can expect to require a larger board in order to create the net around the mouse, if that made any sense. $\endgroup$
    – For I In Range
    Commented Nov 20, 2014 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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