14
$\begingroup$

I went back in an old Flash game and was intrigued by this problem.

Rules

  1. There is an $n\times n$ grid and a mouse entering on the entrance cell and exiting on the exit cell.
  2. The entrance cell and the exit cell is found outside on the grid, on the top and bottom side respectively. You can move them around.
  3. You can build any number of walls in the grid, as long as it does not block the exit cell.
  4. When the walls are built, the mouse will be released.

    The mouse moves as follows:

    • The mouse moves one step towards one of the four cardinal directions: south, west, east, north.
    • The mouse moves to the square it has visited the least.
    • When there is a tie, the mouse prefers the order: down, right, left, up.

Here is an example animation on a $4\times 4$ grid: (Note that this is not the optimal solution, and you can use other $n\times n$ sized grids as well)
Mouse Maze problem

Questions:

  1. What is the maximum number of steps the mouse can have on a $n\times n$ grid?
  2. What is the maximum number of visits on the same cell can you have on a $n\times n$ grid?
$\endgroup$
  • $\begingroup$ Can the mouse reenter the entrance cell? (also, is the answer known?) $\endgroup$ – my pronoun is monicareinstate May 29 at 12:10
  • $\begingroup$ I have a gut for the second question, but I couldn't prove it.. $\endgroup$ – athin May 29 at 12:31
  • 2
    $\begingroup$ @mypronounismonicareinstate The mouse cannot reenter the entrance cell. The answer isn't known too, it looks like the problem needs brute-forcing / computer to find the max. $\endgroup$ – u-ndefined May 29 at 12:37
  • $\begingroup$ @u_ndefined While it can be brute-forced for a small value of \$n\$, I'm not sure how that will lead to the answer (unless if an OEIS argument is possible). $\endgroup$ – my pronoun is monicareinstate May 29 at 12:39
  • 2
    $\begingroup$ This game looks familiar! You may be interested in this related math paper: drops.dagstuhl.de/opus/volltexte/2016/5874 $\endgroup$ – Stomf May 29 at 17:58
8
$\begingroup$

Apparently there was a bug, and my brute-forcer missed some solutions. The actual answers are in a different answer below. I have fixed the bug in my script, and can confirm that the answers provided there are correct (or at least match mine).

Original answer:

Brute force reveals the solutions for 4×4:

Most steps: 78

+---+   +---+---+
| 1   3   3   4 |
+   +   +---+   +
| 1 | 1 | 5   5 |
+   +---+   +---+
| 1 | 8   9   5 |
+   +   +---+---+
| 1 | 9  12   9 |
+   +---+---+---+

Note that although they sum to 77, there is also another step for stepping out of the exit at the bottom, which is not accounted for by the cell visit counts.

Max visits for a single cell: 14

+---+   +---+---+
| 1   3   6   3 |
+   +   +   +---+
| 1 | 1 | 6   6 |
+   +---+---+   +
| 1     | 6  14 |
+   +   +---+   +
| 1         | 6 |
+   +---+---+---+

These solutions are not necessarily the only ones with these counts, just the first ones that I generated with my script.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Did you just stick with the entry/exit positions from the OP's example, or does this include varying those two elements as well? $\endgroup$ – Paul Sinclair May 29 at 18:54
  • $\begingroup$ @PaulSinclair it accounts for different positions. It’s just that they work really well for boxing the mouse into the side of the screen without the exit. $\endgroup$ – Ontonator May 29 at 18:56
  • 2
    $\begingroup$ @Ontonator I feel like this could be a competitive programming-type question. I wonder what they would be able to come up with. $\endgroup$ – rinspy May 29 at 19:51
  • $\begingroup$ I think there is at least a partially mathematical approach here, too. I've been looking at these examples, and I suspect there is a way to calculate the visit-totals for each cell without having to follow the path and count. Such a method could evaluate particular mazes more quickly, and maybe give ways of identifying potential candidates without having to test every one. But I haven't fully worked it out yet. The basic idea is the "pressure" needed to push the path in the correct direction, based on how many wrong directions it has to go through first. $\endgroup$ – Paul Sinclair May 30 at 0:06
  • $\begingroup$ Nice. Can you brute-force it for other $n\times n$ sized boards as well? $\endgroup$ – u-ndefined May 30 at 9:57
8
$\begingroup$

While writing some code to attempt to beat the high scores in the Mouse Maze 2 game (which is the game described, but on a 9x9 grid), I was testing it by brute forcing 4x4 mazes and comparing the results with the current brute force answer.

Apparently, this time brute force reveals the actual solutions for 4x4:

Most steps: 86 (up to off by one errors when counting steps)

86-step illustration

Max visits for a single cell: 16

16-visit illustration

I have also brute forced all 5x5 mazes (6x6 will take a few millions as much time):

Most steps: 283

enter image description here

Most visits for a single cell: 59

59-visit illustration

I tried to optimize for good 6x6 mazes (of course, the results probably won't be optimal).

Most steps: 1368

1368-step illustration

Most visits on one cell: 201. I suspect this is optimal, because it seems like almost all threads produce this solution or a very similar one with the same score.

201-visit illustration

The approximation algorithm is a local greedy search. It makes up to 5 random changes (the number of changes is chosen randomly), and if no improvement is seen within 300000 steps, it accepts this as the solution and starts a gain. The program is multi-threaded and each thread runs for 1 billion steps.

My best score for 9x9 mazes is 74283 steps with 5784 visits on a single cell. This seems to be better than the current record.

enter image description here

| improve this answer | |
$\endgroup$
  • $\begingroup$ Out of curiosity, what language do you use for brute-forcing problems like this? $\endgroup$ – Ontonator Jun 7 at 5:58
  • $\begingroup$ C++ with OpenMP, compiled with g++ -march=native -Ofast -flto -fopenmp -no-pie [warnings and stuff]. $\endgroup$ – my pronoun is monicareinstate Jun 7 at 6:07
  • $\begingroup$ For 6x6 and up, it might be interesting to use some kind of genetic algorithm to find solutions. Of course it will be impossible to prove whether found solutions are optional, but maybe it gets some nice results. $\endgroup$ – sarsaparilla Jun 7 at 11:45
5
$\begingroup$

Not sure this is the upper limit, but this layout gets 10 visits to a single cell:

+---+   +---+---+
|     1 | 2 |   |
+   +   +   +---+
| 1   3   8   3 |
+   +   +   +---+
| 1 | 1 | 4 |   |
+   +---+   +---+
| 1 | 4  10   4 |
+   +---+---+---+

OLD:

+---+   +---+---+
|     1 | 2 |   |
+   +   +   +---+
| 1   3   9   3 |
+   +   +   +---+
| 1 | 1 | 3 |   |
+   +---+---+   +
| 1             |
+   +---+---+---+
| improve this answer | |
$\endgroup$
  • $\begingroup$ @PaulSinclair Perhaps. After I found this, I gave up and brute-forced it (see my other answer). $\endgroup$ – Ontonator May 29 at 17:43
  • $\begingroup$ I was wrong, but I apparently deleted the suggestion after you replied. $\endgroup$ – Paul Sinclair May 29 at 18:48
4
$\begingroup$

Don't have an answer yet, but I think for the second question at least 5 is actually possible:

enter image description here

By having a visit count of 2 on the 2;2 cell, we can force the mouse to go in circles in the right sector, visiting column 3 row 2 cell 5 times before being able to head left towards the exit.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Ahh...this is correct and I retract my answer! I did not think of this case. $\endgroup$ – Jeremy Dover May 29 at 15:17
  • $\begingroup$ The path in the diagram is actually slightly wrong, as the mouse does an extra loop in the top right corner because the other option already has 2 visits, although this doesn't change the maximum visit count of 5. $\endgroup$ – Ontonator May 29 at 15:30
  • $\begingroup$ @Ontonator you are right, I miscounted the visits of the dead-end cells. $\endgroup$ – rinspy May 29 at 15:33
4
$\begingroup$

As the comment here and other answers indicate, this answer is INCORRECT. I leave in case the idea behind bounding the number of exits from a square can be used with other arguments to construct a bound.

For the second question, I'm pretty sure the maximum is four. To see four is achievable, consider:

Maze

The mouse will visit the square in the second row, third column 4 times: the initial entry from left, returning after exploring the alcove below, returning after exploring the alcove at right, and then returning after exploring the alcove above.

The rules, namely the preference for least visited squares, ensure that once you exit a square in one direction, you will not return to it until there are no unvisited squares reachable in that direction. Since the game must terminate, for every reachable square there must be some direction you can leave it and reach the exit. Thus, you can only leave a reachable square at most four times. Since the game begins outside the maze, this means you can only enter a square at most four times.

You can use this to bound the maximum number of steps to $4n^2$, but that is doubtless far from the actual maximum.

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Correct me if I'm wrong, but doesn't it cross that square 6 times? It would do exactly what you have stated, but once it has explored all of the alcoves, there is a tie, and it would prefer to go down, then right, then finally left again, so it enters from the left, bottom, right, top, bottom and right, in that order. $\endgroup$ – Ontonator May 29 at 15:11

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.