A mouse and a maze on a n x n grid

Question

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)

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?

Answer 1

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)

Max visits for a single cell: 16

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

Most steps: 283

Most visits for a single cell: 59

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

Most steps: 1368

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.

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.

Answer 2

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.

Answer 3

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             |
+   +---+---+---+

Answer 4

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

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.

Answer 5

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:

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.