15
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ 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 . $\endgroup$ – my pronoun is monicareinstate May 31 at 8:49
  • 1
    $\begingroup$ 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$. $\endgroup$ – RobPratt Jun 5 at 3:47
  • 1
    $\begingroup$ 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. $\endgroup$ – RobPratt Jun 5 at 4:13
  • 1
    $\begingroup$ 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 $\endgroup$ – Daniel Mathias Jun 6 at 13:54
  • 1
    $\begingroup$ I have $224=N^2-1$ for 15x15, and $325>N^2$ for 18x18 $\endgroup$ – Daniel Mathias Jun 8 at 23:37
9
$\begingroup$

Continued improvement brings us to

97 steps

With this map:

enter image description here

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:

enter image description here

| improve this answer | |
$\endgroup$
  • $\begingroup$ OMG that is so cool! This is better than what I found, so well done! I think we are very close to optimal. $\endgroup$ – Dmitry Kamenetsky May 31 at 13:06
  • $\begingroup$ 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? $\endgroup$ – Dmitry Kamenetsky May 31 at 13:09
  • 1
    $\begingroup$ 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. $\endgroup$ – Oray May 31 at 13:44
  • $\begingroup$ @Dmitry That would shorten the BL-TR and BL-BR paths. $\endgroup$ – Daniel Mathias May 31 at 13:46
  • 1
    $\begingroup$ @Dmitry See edit for 9x9 $\endgroup$ – Daniel Mathias Jun 3 at 2:16
6
$\begingroup$

Here is my attempt which makes it

96 steps

Here is the map

enter image description here

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ This is a great start! Keep it up. $\endgroup$ – Dmitry Kamenetsky May 31 at 7:50
  • 1
    $\begingroup$ @DmitryKamenetsky thanks, this is what I could do by hand :) maybe I put something on computer later. great puzzle. $\endgroup$ – Oray May 31 at 10:39
  • $\begingroup$ Thank you @Oray! I am very impressed what you could achieve by hand. I only have a small improvement to this... $\endgroup$ – Dmitry Kamenetsky May 31 at 10:51
  • $\begingroup$ I also suspect that the optimal is 99, but I cannot find it. $\endgroup$ – Dmitry Kamenetsky May 31 at 12:29
  • 1
    $\begingroup$ 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 $\endgroup$ – Nij Jun 1 at 10:48
1
$\begingroup$

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;
    }
}
```
| improve this answer | |
$\endgroup$
  • $\begingroup$ Nice work! Can you explain how your program works? $\endgroup$ – Dmitry Kamenetsky Jun 2 at 7:35
  • $\begingroup$ 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 $\endgroup$ – Oray Jun 2 at 7:38
  • $\begingroup$ This is not using brute force, though... Of course, this is unlikely to find the optimal solution, but it can find fairly good ones. $\endgroup$ – my pronoun is monicareinstate Jun 2 at 8:30
  • 2
    $\begingroup$ I confirm that 46 is optimal for trees on 7x7. $\endgroup$ – RobPratt Jun 2 at 23:07
  • 1
    $\begingroup$ @Dmitry I managed 255 on 16x16 and 399 on 20x20 before jumping to the 32x32. I revisited 14x14 to find 192. $\endgroup$ – Daniel Mathias Jun 7 at 1:32
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Vldi Grigoryev Jun 1 at 8:00

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.