26
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Is there a fixed starting corner or can the robot choose its corner after seeing the grid? $\endgroup$ – Magma May 27 at 15:17
  • 1
    $\begingroup$ Are computers intended to be used, or must be solve this and prove optimality by hand? $\endgroup$ – greenturtle3141 May 27 at 16:58
  • 3
    $\begingroup$ codepen.io/danjruss/full/mdeYNqK If people want a playground for this I threw a really basic one together. $\endgroup$ – Daniel B May 28 at 1:16
  • 2
    $\begingroup$ @DanielB Now just need to add the robot's shortest path finding algorithm :) $\endgroup$ – zennehoy May 28 at 10:14
  • 3
    $\begingroup$ I turned the 6x6 maze 45 degrees, making it a diamond instead of a square. Hardest maze achieved. $\endgroup$ – Davy M May 28 at 19:54
27
$\begingroup$

I can make the robot take

35 steps:
Maze

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.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Correct! That's the best answer that I managed to find. $\endgroup$ – Dmitry Kamenetsky May 28 at 1:19
  • 6
    $\begingroup$ Doesn't look like anyone's able to beat this. Any ideas on how we might prove that no harder maze exists? $\endgroup$ – theosza May 29 at 12:47
15
$\begingroup$

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

34 steps:
enter image description here
12 white squares are entered once, 11 yellow squares are entered twice.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Very nice solution! Can you do better? $\endgroup$ – Dmitry Kamenetsky May 28 at 0:39
10
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Great start! I actually counted more steps. Just saw the edit. $\endgroup$ – Dmitry Kamenetsky May 27 at 14:11
  • $\begingroup$ Thanks for the fix @msh210. You are quite right I miscounted, so it is even better than I thought. $\endgroup$ – Jaap Scherphuis May 27 at 14:11
  • 2
    $\begingroup$ I actually wouldn't be surprised if this is optimal. This was the first thing I thought of. $\endgroup$ – Don Thousand May 27 at 14:40
  • 1
    $\begingroup$ @DonThousand In my solution it does not matter which corner is the starting corner. It can likely be improved by making use of the knowledge which corner the robot starts on. $\endgroup$ – Jaap Scherphuis May 27 at 15:17
4
$\begingroup$

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";
  }
}
| improve this answer | |
$\endgroup$

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.