Creating the hardest 6x6 maze

Question

You are given an empty 6x6 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. 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?

I've had really good fun solving this myself. Good luck to you!

^ NOTE: all three corners must be reachable from the starting corner. No corner can be a wall.

Answer 1

I can make the robot take

35 steps:

The robot must take this many steps because

7 steps are required to get from top left to bottom left, 7 from bottom left to bottom right, 10 from bottom right to top left and 11 from top left to top right.
If the robot visits the bottom region first, it must take at least 7 + 7 + 10 + 11 = 35 steps. If the robot visits the top right corner first, it must take at least 11 + 11 + 7 + 7 = 36 steps.
So 35 steps is the minimum.

Answer 2

Assuming there is a fixed starting corner, I can make the robot take

34 steps:

12 white squares are entered once, 11 yellow squares are entered twice.

Answer 3

Here is a first attempt. It takes

33 moves, 11 between any two adjacent corners.

My solution:

o x . . . o
. x . x x x
. x . . . .
. . . . x .
x x x . x .
o . . . x o

I have no doubt it can be improved.

Answer 4

Using brute force, I confirmed that

35 steps is indeed optimal for 6x6.
0 0 0 0 1 0
0 1 0 0 1 0
0 0 1 0 1 0
1 0 1 0 0 0
0 0 0 1 1 1
0 1 0 0 0 0

The program took a little under 2 minutes to run (single-threaded, i9-9900k).

For fun, here are the results for 5x5:

24 steps is optimal for 5x5.
0 0 0 0 0
0 1 1 0 0
0 0 0 1 0
1 1 0 1 0
0 0 0 1 0

And for 4x4:

15 steps is optimal for 4x4.
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0

Here is the C++ code I used:

#include <algorithm>
#include <array>
#include <iostream>
#include <utility>
#include <vector>

// size of maze
static constexpr int N = 6;

// 0 = top left, 1 = top right, 2 = bottom left, 3 = bottom right
static constexpr std::array<int, 4> cornerPos{
    {0, N - 1, (N - 1) * N, (N * N) - 1}};

struct Workspace {
  Workspace(int N) : visited(N * N) {
    queue.reserve(N * N);
    newQueue.reserve(N * N);
    for (int i = 0; i < 3; ++i) {
      distances.emplace_back(3 - i);
    }
  }

  std::vector<int> visited;
  std::vector<int> queue;
  std::vector<int> newQueue;
  std::vector<std::vector<int>> distances;
};

bool calcDistances(
    const std::vector<int>& maze,
    int startCorner,
    Workspace& ws) {
  auto& distances = ws.distances[startCorner];
  int distanceCount = 0;

  std::copy(maze.begin(), maze.end(), ws.visited.begin());

  ws.queue.clear();
  ws.queue.push_back(cornerPos[startCorner]);

  for (int distance = 0;; distance++) {
    if (ws.queue.empty()) {
      break;
    }
    ws.newQueue.clear();
    for (int pos : ws.queue) {
      if (ws.visited[pos]) {
        continue;
      }
      ws.visited[pos] = true;
      for (int i = 0; i < distances.size(); ++i) {
        if (pos == cornerPos[startCorner + 1 + i]) {
          distances[i] = distance;
          ++distanceCount;
          if (distanceCount == distances.size()) {
            return true;
          }
        }
      }
      int row = pos / N;
      int col = pos % N;
      // up
      if (row > 0 && !ws.visited[pos - N]) {
        ws.newQueue.push_back(pos - N);
      }
      // down
      if (row < N - 1 && !ws.visited[pos + N]) {
        ws.newQueue.push_back(pos + N);
      }
      // left
      if (col > 0 && !ws.visited[pos - 1]) {
        ws.newQueue.push_back(pos - 1);
      }
      // right
      if (col < N - 1 && !ws.visited[pos + 1]) {
        ws.newQueue.push_back(pos + 1);
      }
    }
    ws.queue.swap(ws.newQueue);
  }

  // a corner was unreachable
  return false;
}

int mazeLength(const std::vector<int>& maze, Workspace& ws) {
  // fail fast if any corner is blocked
  // corner 0 is never blocked since we set maze[1] == 0
  if ((maze[N - 2] && maze[2 * N - 1]) ||
      (maze[(N - 2) * N] && maze[(N - 1) * N + 1]) ||
      (maze[(N - 1) * N - 1] && maze[N * N - 2])) {
    return -1;
  }
  if (!calcDistances(maze, 0, ws)) {
    return -1;
  }
  calcDistances(maze, 1, ws);
  calcDistances(maze, 2, ws);
  auto& d = ws.distances;
  return std::min<int>(
      {d[0][0] + d[1][0] + d[2][0],
       d[0][0] + d[1][1] + d[2][0],
       d[0][1] + d[1][0] + d[1][1],
       d[0][1] + d[2][0] + d[1][1],
       d[0][2] + d[1][1] + d[1][0],
       d[0][2] + d[2][0] + d[1][0]});
}

int main() {
  std::vector<int> maze(N * N);
  std::vector<int> toggles;

  // the corners are always 0
  // we can let square 1 always be 0 (by symmetry)
  for (int i = 1; i < N * N - 1; ++i) {
    if (i != 1 && i != N - 1 && i != (N - 1) * N) {
      toggles.push_back(i);
    }
  }

  std::vector<int> bestMaze;
  int highestLength = -1;
  Workspace ws(N);
  bool done = false;
  int progress = 0;

  while (!done) {
    if (++progress % 10000000 == 0) {
      std::cout << progress << "\n";
    }
    auto length = mazeLength(maze, ws);
    if (length > highestLength) {
      bestMaze = maze;
      highestLength = length;
    }
    for (int i = toggles.size() - 1; i >= 0; --i) {
      int& bit = maze[toggles[i]];
      if (bit) {
        bit = 0;
        if (i == 0) {
          done = true;
        }
      } else {
        bit = 1;
        break;
      }
    }
  }
  std::cout << "Highest length: " << highestLength << "\n";
  std::cout << "Maze:\n";
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      std::cout << bestMaze[i * N + j] << " ";
    }
    std::cout << "\n";
  }
}