4
$\begingroup$

This puzzle is based on Creating the hardest 6x6 maze

You are given an empty 7x7 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 centre cell (4th row and column) and visit all the corners^ using the shortest path. 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? Are there multiple solutions? Good luck!

^ NOTE: All corners must be reachable from the starting centre cell. You cannot have a wall in the centre cell or any corners.

Improve this question
$\endgroup$
8
  • $\begingroup$ My brute force code currently estimates the running time as around 9-10 days (multi-threaded on an AMD Ryzen 2600 CPU), although that seems to be an underestimate... $\endgroup$
    – the default.
    Commented May 31, 2020 at 6:29
  • $\begingroup$ Nice work! I would be interested to see some results of this, especially for the next puzzle: puzzling.stackexchange.com/questions/98723/… $\endgroup$
    – Dmitry Kamenetsky
    Commented May 31, 2020 at 6:43
  • $\begingroup$ 10x10 seems completely unfeasible to brute force to me (it might be possible to find some good solutions by making random guesses, but 1) not to prove them optimal 2) searching by hand will likely be better) $\endgroup$
    – the default.
    Commented May 31, 2020 at 6:47
  • $\begingroup$ Definitely not feasible for brute force, but you can go quite far with heuristic methods. I am looking forward to people's solutions on that one and whether it can beat mine. $\endgroup$
    – Dmitry Kamenetsky
    Commented May 31, 2020 at 6:54
  • 1
    $\begingroup$ The brute forcer is 3.5% done, the best answer seen is 48, and each improvement seen becomes closer and closer to the 52-step answer. $\endgroup$
    – the default.
    Commented May 31, 2020 at 12:44

3 Answers 3

Reset to default
6
$\begingroup$

I can get 52 steps out of this robot:

enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ Very well done and so quick! I believe this is one of the optimal solutions. $\endgroup$
    – Dmitry Kamenetsky
    Commented May 29, 2020 at 1:27
4
$\begingroup$

I have found 2 solutions with 50 steps which can be made with 2 way symmetry, and 4 solutions with 48 steps that are not symmetrical at all. (I think there might be some sort of pattern here.) Every solution I try to refine ends up just like @AxiomaticSystem's answer. I believe he has the best solution.

My two 50 step solutions:

enter image description here

An Example of a 48 step Asymmetric solution

enter image description here

Improve this answer
$\endgroup$
2
  • $\begingroup$ First post, Im not sure how to use spoiler content (>!) $\endgroup$
    – Derager
    Commented May 29, 2020 at 15:57
  • $\begingroup$ You just needed to add a space after the spoiler tag, that's all. Welcome to the site! $\endgroup$
    – F1Krazy
    Commented May 29, 2020 at 16:03
1
$\begingroup$

I proved that the 52-step answer is optimal with brute force.

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>

const char N = 7;
const char i0 = (N/2)*N + N/2;
const char i1 = N*N-1, i2 = N-1, i3 = 0, i4 = N*N-N;
std::vector<short> dbfs(int64_t mask, int from)
{
    std::vector<short> dists(N*N, 255);
    dists[from] = 0;
    std::queue<char> q;
    q.push(from);
    while(!q.empty())
    {
        char cur = q.front(); q.pop();
        short cd = dists[cur];
        char x = cur % N, y = cur / N;
        if(x != 0)
        {
            char ni = (x-1) + (y)*N;
            if((mask & (1ll<<ni)) && dists[ni] > cd+1) dists[ni] = cd+1, q.push(ni);
            //if(dists[ni] <= cd + 1) continue;
            //dists[ni] = cd + 1; q.push(ni);
        }
        if(x != N-1)
        {
            char ni = (x+1) + (y)*N;
            if((mask & (1ll<<ni)) && dists[ni] > cd+1) dists[ni] = cd+1, q.push(ni);
            //dists[ni] = cd + 1; q.push(ni);
        }
        if(y != 0)
        {
            char ni = (x) + (y-1)*N;
            if((mask & (1ll<<ni)) && dists[ni] > cd+1) dists[ni] = cd+1, q.push(ni);
            //dists[ni] = cd + 1; q.push(ni);
        }
        if(y != N-1)
        {
            char ni = (x) + (y+1)*N;
            if((mask & (1ll<<ni)) && dists[ni] > cd+1) dists[ni] = cd+1, q.push(ni);
            //dists[ni] = cd + 1; q.push(ni);
        }
    }
    return dists;
}
bool dfs(int64_t mask, char at, char prev, std::vector<char>& marks)
{
    marks[at] = true;
    char x = at % N, y = at / N;
    if(x != 0)
        {char ni = (x-1) + (y)*N; if((mask & (1ll<<ni)) && ni != prev && ((marks[ni] || dfs(mask, ni, at, marks)))) return true;}
    if(x != N-1)
        {char ni = (x+1) + (y)*N; if((mask & (1ll<<ni)) && ni != prev && ((marks[ni] || dfs(mask, ni, at, marks)))) return true;}
    if(y != 0)
        {char ni = (x) + (y-1)*N; if((mask & (1ll<<ni)) && ni != prev && ((marks[ni] || dfs(mask, ni, at, marks)))) return true;}
    if(y != N-1)
        {char ni = (x) + (y+1)*N; if((mask & (1ll<<ni)) && ni != prev && ((marks[ni] || dfs(mask, ni, at, marks)))) return true;}
    return false;
}
bool treeq(int64_t mask)
{
    std::vector<char> marks(N * N);
    if(dfs(mask, i0, -1, marks)) return false;
    for(int i = 0; i < N*N; i++) if(marks[i] == 0 && (mask & (1ll<<i))) return false;
    return true;
}
int main()
{
    setbuf(stdout, 0);
    const int64_t expected = 1ll << (N*N-5);
    printf("%lld\n", expected);
    volatile int64_t iters = 0;
    volatile short best_ans = 0;
    auto starttime = std::chrono::high_resolution_clock::now();
    const int64_t checkfor = 1l<<i0 | 1l<<i1 | 1l<<i2 | 1l<<i3 | 1l<<i4;
#pragma omp parallel for schedule(guided)
    //for(int64_t mask = 1ll<<(N*N); mask --> 0;)
    for(int64_t mask = checkfor; mask < 1ll<<(N*N); mask++)
    {
        if(__builtin_popcountll(mask & checkfor) != 5) continue;
        if(iters % 10000 == 0 && iters != 0)
        {
            //printf("%.5lf left\n", iters * 100.0 / expected),
            //printf("%ld done\n", iters);
            auto cur = std::chrono::high_resolution_clock::now();
            int64_t ns = std::chrono::duration_cast<std::chrono::nanoseconds>(cur - starttime).count();
            //printf("%ld\n", ns);
            int64_t tofinish = ns / iters * expected;
            //printf("%lld\n", expected);
            printf("%.5lf%% done (%ld), %.5lf second to finish\r", iters * 100.0 / expected, iters, (tofinish - ns) / 1e9);
        }
        #pragma omp atomic
        iters++;
        if(iters < 1099184650000) continue;
        if(!treeq(mask)) continue; //must be a connected tree
        std::vector<short> d0 = dbfs(mask, i0);
        std::vector<short> d1 = dbfs(mask, i1);
        std::vector<short> d2 = dbfs(mask, i2);
        std::vector<short> d3 = dbfs(mask, i3);
        std::vector<short> d4 = dbfs(mask, i4);
        int64_t ans = std::min<int>({
            d0[i1] + d1[i2] + d2[i3] + d3[i4],
            d0[i1] + d1[i2] + d2[i4] + d4[i3],
            d0[i1] + d1[i3] + d3[i2] + d2[i4],
            d0[i1] + d1[i3] + d3[i4] + d4[i2],
            d0[i1] + d1[i4] + d4[i2] + d2[i3],
            d0[i1] + d1[i4] + d4[i3] + d3[i2],
            d0[i2] + d2[i1] + d1[i3] + d3[i4],
            d0[i2] + d2[i1] + d1[i4] + d4[i3],
            d0[i2] + d2[i3] + d3[i1] + d1[i4],
            d0[i2] + d2[i3] + d3[i4] + d4[i1],
            d0[i2] + d2[i4] + d4[i1] + d1[i3],
            d0[i2] + d2[i4] + d4[i3] + d3[i1],
            d0[i3] + d3[i1] + d1[i2] + d2[i4],
            d0[i3] + d3[i1] + d1[i4] + d4[i2],
            d0[i3] + d3[i2] + d2[i1] + d1[i4],
            d0[i3] + d3[i2] + d2[i4] + d4[i1],
            d0[i3] + d3[i4] + d4[i1] + d1[i2],
            d0[i3] + d3[i4] + d4[i2] + d2[i1],
            d0[i4] + d4[i1] + d1[i2] + d2[i3],
            d0[i4] + d4[i1] + d1[i3] + d3[i2],
            d0[i4] + d4[i2] + d2[i1] + d1[i3],
            d0[i4] + d4[i2] + d2[i3] + d3[i1],
            d0[i4] + d4[i3] + d3[i1] + d1[i2],
            d0[i4] + d4[i3] + d3[i2] + d2[i1]
        });
        if(ans > best_ans)
        {
            #pragma omp critical
            if(ans > best_ans)
            {
                best_ans = ans; printf("\n%d (%ld)\n", ans, mask);
                for(int el : d0) printf("%d ", el); printf("\n");
                for(int el : d1) printf("%d ", el); printf("\n");
                for(int el : d2) printf("%d ", el); printf("\n");
                for(int el : d3) printf("%d ", el); printf("\n");
                for(int el : d4) printf("%d ", el); printf("\n");
            }
            //for(;;) ;
        }
    }
}
Improve this answer
$\endgroup$
1
  • $\begingroup$ Well done my friend! $\endgroup$
    – Dmitry Kamenetsky
    Commented Jun 16, 2020 at 5:36

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