# Creating the hardest 7x7 maze

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.

• 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... May 31, 2020 at 6:29
• Nice work! I would be interested to see some results of this, especially for the next puzzle: puzzling.stackexchange.com/questions/98723/… May 31, 2020 at 6:43
• 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) May 31, 2020 at 6:47
• 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. May 31, 2020 at 6:54
• 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. May 31, 2020 at 12:44

I can get 52 steps out of this robot:

• Very well done and so quick! I believe this is one of the optimal solutions. May 29, 2020 at 1:27

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:

An Example of a 48 step Asymmetric solution

• First post, Im not sure how to use spoiler content (>!) May 29, 2020 at 15:57
• You just needed to add a space after the spoiler tag, that's all. Welcome to the site! May 29, 2020 at 16:03

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>

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> 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;
}
{
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)
{
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
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(;;) ;
}
}
}

• Well done my friend! Jun 16, 2020 at 5:36