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.

$\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$ May 31 '20 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$ May 31 '20 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$ May 31 '20 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$ May 31 '20 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$ May 31 '20 at 12:44
6
$\begingroup$

I can get 52 steps out of this robot:

enter image description here

$\endgroup$
1
  • $\begingroup$ Very well done and so quick! I believe this is one of the optimal solutions. $\endgroup$ May 29 '20 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

$\endgroup$
3
  • $\begingroup$ First post, Im not sure how to use spoiler content (>!) $\endgroup$
    – Derager
    May 29 '20 at 15:57
  • $\begingroup$ You just needed to add a space after the spoiler tag, that's all. Welcome to the site! $\endgroup$
    – F1Krazy
    May 29 '20 at 16:03
  • $\begingroup$ Thanks a bunch! $\endgroup$
    – Derager
    May 29 '20 at 16:10
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(;;) ;
        }
    }
}
$\endgroup$
1
  • $\begingroup$ Well done my friend! $\endgroup$ Jun 16 '20 at 5:36

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.