Creating the hardest 10x10 maze

Question

You are given an empty 10x10 grid. You are allowed to paint some of its cells as walls (black), while the remaining cells stay empty (white). A robot is programmed to start in the top-left corner of the grid and visit the other three corners using the shortest path. All three corners must be reachable from the starting corner and no corner can be a wall. Once the maze is created the robot automatically knows the shortest path and its decisions cannot be influenced. At each step, the robot moves from one empty cell to an adjacent empty cell (horizontally or vertically, but not diagonally). Can you paint the walls in a way that forces the robot to take the most number of steps? Perhaps we may not solve this puzzle optimally, but can we at least find some good bounds on the solution? Computers are very welcome.

This puzzle is an extension of Creating the hardest 6x6 maze I hope that people forgive me for posting similar puzzles. I am just fascinated by this puzzle and I have an interesting theory about the general NxN case. I believe I have a good solution to this puzzle, but I am not convinced that it is optimal. This is why I need help from you the community. Let's make discoveries together!

I feel like the idea for an optimal answer here is to create a tree that branches as early as possible into 3 paths of close-to-equal lengths . — the default., May 31 '20 at 08:49
I agree. From my observation the best solutions have 3 separate paths. — Dmitry Kamenetsky, May 31 '20 at 08:52
It's mostly obvious that they will have 3 paths (why would anybody traverse a fourth one?) — the default., May 31 '20 at 09:10
Has anyone thought of some nice bounds for the general NxN problem? I feel that one cannot get N*N or more, but I can't prove it. — Dmitry Kamenetsky, Jun 04 '20 at 10:58
You can derive an upper bound of $(2N+1)(N-1)$ by maximizing $2x_1+2x_2+x_3$ subject to $x_1+x_2+x_3 \le N^2-1$ and $x_i \ge N-1$. The interpretation here is that $x_i$ is the distance from the root to corner $i$. — RobPratt, Jun 05 '20 at 03:47
Imposing $x_1 \le x_3$ and $x_2 \le x_3$ (the path to the farthest corner is traversed only once) yields a better bound of $5(N^2-1)/3$ from $x_1=x_2=x_3$ when $N^2 \equiv 1 \pmod 3$. For $N=10$, this upper bound is $165$, so maybe this is what @Vldi was getting at. — RobPratt, Jun 05 '20 at 04:13
You can do better than $N^2$. See this 32x32 maze, which requires 1049 steps to traverse. You can see that the number of unpainted squares must remain under $2N^2/3$, so the average path length, from top left to any other corner, cannot exceed $2N^2/9$. This provides a strict upper bound of $10N^2/9$ for total path length. I believe we can come arbitrarily close to this bound for sufficiently large values of $N$. @RobPratt — Daniel Mathias, Jun 06 '20 at 13:54
Daniel you just blew my mind! I did not expect this result. Well done! I am planning to publish an OEIS sequence with our best results. — Dmitry Kamenetsky, Jun 06 '20 at 14:30
I wonder what is the smallest N where we can do better than N^2? — Dmitry Kamenetsky, Jun 06 '20 at 14:43
@DanielMathias, nice find! I guess for both these upper bounds (yours and mine), we need to be explicit that we are assuming a tree. For example, the optimal score for $N=4$ is $15$, with $12>2N^2/3$ unpainted squares. Is there an argument that a tree is optimal for sufficiently large $N$? — RobPratt, Jun 06 '20 at 17:04
By tree, I mean that the unpainted cells form an acyclic connected graph. — RobPratt, Jun 06 '20 at 23:39
I see now. That makes sense. Would an empty 2x2 be counted as a cycle? — Dmitry Kamenetsky, Jun 07 '20 at 01:21
Hey guys! I started writing down the list of our best solutions. Please let me know if you have better results for any N. https://docs.google.com/spreadsheets/d/1ckFWeZh7zrrQZu9U8G2e-yjIEBoerr_wtq_DnISxbtY/edit?usp=sharing — Dmitry Kamenetsky, Jun 08 '20 at 12:54
Thank you Daniel. I updated the table. You probably already have improvements for N=17 and 19? — Dmitry Kamenetsky, Jun 09 '20 at 00:59
@DanielMathias I finally managed to find 193 for 14x14: https://pastebin.com/14bbd0dE Now all our records are an odd number away from N^2. I suspect 17x17 can be improved too. I will start making the sequence soon. Thank you for all your help! — Dmitry Kamenetsky, Jun 19 '20 at 01:08
@DanielMathias I can't seem to copy the grids from your spreadsheet. Do you happen to have them in a text-based format, something like '.' for empty and '#' for wall? That would be super useful. — Dmitry Kamenetsky, Jun 19 '20 at 03:24
Thank you @DanielMathias. Just wondering what happened to 19x19? Do you have the 360-step solution or just the 358-step one? — Dmitry Kamenetsky, Jun 21 '20 at 01:02
It was only 358, as stated in my earlier comment. The wrong cells were highlighted in the spreadsheet. — Daniel Mathias, Jun 21 '20 at 01:42
A minor change allows for 360. Spreadsheet and document updated. — Daniel Mathias, Jun 21 '20 at 01:56
I've submitted the sequence to OEIS, now waiting for approval. — Dmitry Kamenetsky, Jun 29 '20 at 03:13
The sequence has finally been published! http://oeis.org/A335753 — Dmitry Kamenetsky, Jul 22 '20 at 23:17
@DanielMathias many of our records have been improved. See https://oeis.org/A335753 — Dmitry Kamenetsky, Aug 10 '20 at 23:31

Daniel Mathias · Accepted Answer · 2020-06-03T02:15:14.280

9

Continued improvement brings us to

97 steps

With this map:

The various path lengths are

 TL to BL = 17 | BL-BR-TR = 97
 TL to TR = 23 | BL-TR-BR = 98
 TL to BR = 22 | BR-BL-TR = 101
 BL to TR = 40 | BR-TR-BL = 102
 BL to BR = 39 | TR-BL-BR = 102
 TR to BR = 41 | TR-BR-BL = 103

Here is a 9x9 maze:

edited Jun 03 '20 at 02:15

answered May 31 '20 at 12:51

Daniel Mathias

14,926
2
30
62

OMG that is so cool! This is better than what I found, so well done! I think we are very close to optimal. – Dmitry Kamenetsky May 31 '20 at 13:06
What happens if you shift the start of the BL and the BR paths one cell to the right? Does it help us improve things? – Dmitry Kamenetsky May 31 '20 at 13:09
1

good job finding 97, I believe the optimal answer is 99, let's see who finds it :) probably very hard and requires quite a luck without a code. – Oray May 31 '20 at 13:44
@Dmitry That would shorten the BL-TR and BL-BR paths. – Daniel Mathias May 31 '20 at 13:46
@DanielMathias I have verified with a program that your solution indeed achieves 97 steps. Well done. – Dmitry Kamenetsky Jun 02 '20 at 03:18
1

@Dmitry See edit for 9x9 – Daniel Mathias Jun 03 '20 at 02:16
Daniel that is very cool! Nice. I've noticed that it has a similar structure to your 10x10, so perhaps we can generalise this to any NxN? – Dmitry Kamenetsky Jun 03 '20 at 02:17
@Dmitry Yes. The T intersection of the paths two steps off the start is essential for larger grids. After that, its all about getting the path lengths as close to equal as possible. In the 10x10, these are 19, 20 and 21 (measured from the T), so I expect that it is optimal. – Daniel Mathias Jun 03 '20 at 02:43
I have found out that 7x7 as 46 as well. It seems theoretical maximum is $n\times n-1$, though you may not achieve that depending on the dimensions. but for 9x9 case, it seems $n\times n-1$ is achieveable. – Oray Jun 03 '20 at 09:14
I am now convinced that this is the best answer. – Dmitry Kamenetsky Jul 13 '20 at 04:18

Oray · Answer 2 · 2020-05-31T11:42:21.450

6

Here is my attempt which makes it

96 steps

Here is the map

Here is how I solved it;

First of all I defined two centers, one of them is S, the other one is M. and noted the distance from M to LB and RB, and S to RT. and try to calculate which is has the lowest value for the shortest path

as shown below:

+---------+----------+--------+-------+------+------+
| S -> M  | M  -> RB | M ->LB | S->RT | Max1 | Max2 |
+---------+----------+--------+-------+------+------+
|      5  |        16|     17 |    21 |   96 |   97 |
+---------+----------+--------+-------+------+------+

If I increase S->RT by one, it will decrease S->M2 value by 1, which reduced changes the optimal longest length, tried to maximize one of the max1 or max2 values by playing with it and draw it.

I believe the optimal answer should be

99

edited May 31 '20 at 11:42

answered May 31 '20 at 07:44

Oray

30,307
6
61
215

This is a great start! Keep it up. – Dmitry Kamenetsky May 31 '20 at 07:50
1

@DmitryKamenetsky thanks, this is what I could do by hand :) maybe I put something on computer later. great puzzle. – Oray May 31 '20 at 10:39
Thank you @Oray! I am very impressed what you could achieve by hand. I only have a small improvement to this... – Dmitry Kamenetsky May 31 '20 at 10:51
I also suspect that the optimal is 99, but I cannot find it. – Dmitry Kamenetsky May 31 '20 at 12:29
Is it possible to move M 1 cell higher here (and adjust the paths and make R3C5 be empty and R4C456 be walls)? (I have no idea how you draw these beautiful diagrams and also how do you solve the mazes by hand in a reasonable amount of time) (I am not sure whether that would help) – the default. May 31 '20 at 12:50
1

The mazes look pretty straightforward to do in a spreadsheet, and there is evidence of this being the approach used (as it also allows multiple copies of a particular version to be made and edited separately). @mypronounismonicareinstate – Nij Jun 01 '20 at 10:48

score 1 · Answer 3 · edited May 31 '20 at 20:09

I think I have an idea how to to give O boundary for max step a and it's by abstracting the problem.

Let's say we have a tree with 100 vertices and we want to find the number of steps it takes to get to the leafs when the tree has only 2 leafs, 3 leafs, 4 leafs.

For 2 leafs it's easy: number of steps is 100.
For 3 steps it's not too hard: you want to max the return path from leaf 2 to 3 by making the roots 1 step from the start and divide the path to two the robot will take the path to closer leaf for making the return smaller. Number of steps is 134 I think.
For 4 leafs similar from start to root 1 step 99/3 = 33 steps from the root to other leafs. The number of steps becomes 1+2×33+2×33+33= 166 I think.

Maybe the approach for 100 nodes isn't correct but a rough estimation; you can get a rougher estimation if you can guess the correct number of nodes.

For summary it can't be more then 166 steps.

I think I found a way to lower the amount of node to check by dynamic programing approach. I think for grid 10x 10 the max node of tree graph with 2 node is 59. I know length of tree with 2 leafs in 2x1 grid is 2. and for 2xn when n >2 will be l(2,n-1) +1 or +2 if n divided by 2 then +1. after that you the length we sign with opt(i,j) of tree with 2 nodes is max opt(i,j-1) +1 , opt(i,k)+ 1 + opt(i,j-k-1) when k = 2 .. j-2. I think this way we can lower the amount of nodes — Vlad Barkanass, Jun 01 '20 at 08:00

score 1 · Answer 4 · answered Jun 02 '20 at 06:42

I have written a program that tries to find a solution. Currently the best result I achieved with it is 96:

....#...#.
.##...#.#.
...###....
.#....####
..###.#...
#...#...#.
###..#.##.
...#..#...
.#..#.#.##
..#...#...

C++ code:

//#define _GLIBCXX_DEBUG
#include <x86intrin.h>
#include <cstring>
#include <iostream>
#include <streambuf>
#include <bitset>
#include <cstdio>
#include <atomic>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <random>
#include <set>
#include <list>
#include <map>
#include <unordered_map>
#include <deque>
#include <stack>
#include <queue>
#include <string>
#include <iomanip>
#include <unordered_set>
#include <thread>

std::array<std::array<short, 10>, 10> getDists(const std::array<short, 10>& maze, int sx, int sy)
{
    static const int ddx[4] { 0, 0, 1, -1 };
    static const int ddy[4] { 1, -1, 0, 0 };
    std::array<std::array<short, 10>, 10> dists{};
    for(int i = 0; i < 10; i++) for(int j = 0; j < 10; j++) dists[i][j] = SHRT_MAX >> 3;
    dists[sy][sx] = 0;
    std::array<std::pair<char, char>, 105> dq; dq[0] = {sx, sy};
    //std::deque<std::pair<int,int>> dq; dq.push_back({sx, sy});
    int qi1 = 0, qi2 = 1; //qi2 = index to insert, qi1 = index to read
    while(qi1 != qi2)
    {
        auto[cx, cy] = dq[qi1++];
        short cd = dists[cy][cx];
        short nd = cd + 1;
        for(int di = 0; di < 4; di++)
        {
            int dx = ddx[di], dy = ddy[di];
            int nx = cx + dx, ny = cy + dy;
            if(nx < 0 || ny < 0 || nx >= 10 || ny >= 10) continue;
            if((maze[ny] & (1<<nx)) == 0) continue;
            if(dists[ny][nx] <= nd) continue;
            dists[ny][nx] = nd;
            dq[qi2++] = {nx, ny};
        }
    }
    return dists;
}
bool dfs(const std::array<short, 10>& maze, std::array<char, 100>& marks, int x, int y, int px = -1, int py = -1)
{
    static const int ddx[4] { 0, 0, 1, -1 };
    static const int ddy[4] { 1, -1, 0, 0 };
    marks[y * 10 + x] = true;
    for(int di = 0; di < 4; di++)
    {
        int dx = ddx[di], dy = ddy[di];
        int nx = x + dx, ny = y + dy;
        if(nx < 0 || ny < 0 || nx >= 10 || ny >= 10) continue;
        if(ny == py && nx == px) continue;
        if((maze[ny] & (1<<nx)) == 0) continue;
        if(marks[ny*10+nx]) return true;
        if(dfs(maze, marks, nx, ny, x, y)) return true;
    }
    return false;
}
bool isTree(const std::array<short, 10>& maze)
{
    std::array<char, 100> marks {};
    if(dfs(maze, marks, 0, 0)) return false;
    //for(int i = 0; i < marks.size(); i++) if(marks[i] == 0 && ...) return false; -- unnecessary
    return true;
}
int getScore(const std::array<short, 10>& maze, bool treecheck = false)
{
    if((maze[0] & (1<<0)) == 0) return -1;
    if((maze[0] & (1<<9)) == 0) return -1;
    if((maze[9] & (1<<0)) == 0) return -1;
    if((maze[9] & (1<<9)) == 0) return -1;
    if(treecheck && !isTree(maze)) return -1;
    //get distances between corners
    auto dTL = getDists(maze, 0, 0);
    auto dTR = getDists(maze, 9, 0);
    auto dBL = getDists(maze, 0, 9);
    auto dBR = getDists(maze, 9, 9);
    //printf("TL -> TL=%d, TR=%d, BL=%d, BR=%d\n", dTL[0][0], dTL[0][9], dTL[9][0], dTL[9][9]);
    //printf("TR -> TL=%d, TR=%d, BL=%d, BR=%d\n", dTR[0][0], dTR[0][9], dTR[9][0], dTR[9][9]);
    //printf("BL -> TL=%d, TR=%d, BL=%d, BR=%d\n", dBL[0][0], dBL[0][9], dBL[9][0], dBL[9][9]);
    //printf("BR -> TL=%d, TR=%d, BL=%d, BR=%d\n", dBL[0][0], dBR[0][9], dBR[9][0], dBR[9][9]);
    int mindist = std::min<int>({
        dTL[9][0] + dBL[9][9] + dBR[0][9],
        dTL[9][0] + dBL[0][9] + dTR[9][9],
        dTL[9][9] + dBR[9][0] + dBL[0][9],
        dTL[9][9] + dBR[0][9] + dTR[9][0],
        dTL[0][9] + dTR[9][0] + dBL[9][9],
        dTL[0][9] + dTR[9][9] + dBR[9][0]});
    if(mindist >= (SHRT_MAX >> 3)) return -1;
    return mindist;
}
int main()
{
    std::mt19937 mt(time(0));
    //std::array<short, 10> maze {
    //  0b1110111111,
    //  0b0010100101,
    //  0b1110101101,
    //  0b1001101011,
    //  0b1011001010,
    //  0b1110111011,
    //  0b0000100001,
    //  0b1110101111,
    //  0b1010101000,
    //  0b1011101111 }; //the current 97 answer
    std::array<short, 10> maze {
        0b1111111111,
        0b1111111111,
        0b1111111111,
        0b1111111111,
        0b1111111111,
        0b1111111111,
        0b1111111111,
        0b1111111111,
        0b1111111111,
        0b1111111111 };
    printf("%d\n", getScore(maze));
    std::array<short, 10> bestmaze = maze;
    std::set<std::array<short, 10>> seen;
    int bestscore = getScore(maze), lastSeen = 0;
    seen.insert(maze);
    for(int64_t its = 0; bestscore < 98; its++)
    {
        int cx, cy;
        cx = mt() % 10, cy = mt() % 10;
        maze[cy] ^= 1 << cx;
        if(its - lastSeen > 100)
        {
            lastSeen = its;
            int i = mt() % seen.size();
            auto it = seen.begin(); std::advance(it, i);
            maze = *it;
        }
        int score = getScore(maze, bestscore >= 75);
        if(score > bestscore || (score == bestscore && seen.count(maze) == 0))
        {
            if(score > bestscore) seen.clear();
            bestscore = score;
            seen.insert(maze);
            printf("%d\n", score);
            for(int y = 0; y < 10; y++)
            {
                for(int x = 0; x < 10; x++) printf("%c", maze[y] & (1<<x) ? '.' : '#');
                printf("\n");
            }
        }
        if(score > bestscore) bestscore = score, bestmaze = maze, lastSeen=its;
    }
}
```

not sure programming would find the optimal solution, there are too many options. I wrote my own program but 6x6 takes 3-4 mins, tried 7x7 takes 30 mins was still going on... not sure it will be possible with 10x10... It will take months. but if you apply some restrictions, such as the number of # between 30-36, and some other restrictions, it will take for a few weeks maybe :P — Oray, Jun 02 '20 at 07:38
This is not using brute force, though... Of course, this is unlikely to find the optimal solution, but it can find fairly good ones. — the default., Jun 02 '20 at 08:30
Thank you Rob! Here are my other best results: 63 on 8x8 and 78 on 9x9. My hypothesis is that you can achieve n*n-1 for even n, so I expect 99 on this puzzle to be possible. — Dmitry Kamenetsky, Jun 03 '20 at 01:37
@Dmitry On 14x14, I have managed 191. There might be a way to reach 192... — Daniel Mathias, Jun 03 '20 at 22:42
@Dmitry I managed 255 on 16x16 and 399 on 20x20 before jumping to the 32x32. I revisited 14x14 to find 192. — Daniel Mathias, Jun 07 '20 at 01:32
Daniel superb results! Your method seems superior to mine as I can't get close to those results. I wonder at what N can we reach N^2? — Dmitry Kamenetsky, Jun 07 '20 at 02:53

Creating the hardest 10x10 maze

4 Answers4

Linked