29
$\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$
12
  • 4
    $\begingroup$ Is there a fixed starting corner or can the robot choose its corner after seeing the grid? $\endgroup$
    – Magma
    May 27, 2020 at 15:17
  • 1
    $\begingroup$ Are computers intended to be used, or must be solve this and prove optimality by hand? $\endgroup$ May 27, 2020 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, 2020 at 1:16
  • 2
    $\begingroup$ @DanielB Now just need to add the robot's shortest path finding algorithm :) $\endgroup$
    – zennehoy
    May 28, 2020 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, 2020 at 19:54

4 Answers 4

31
$\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.

$\endgroup$
2
  • 2
    $\begingroup$ Correct! That's the best answer that I managed to find. $\endgroup$ May 28, 2020 at 1:19
  • 8
    $\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, 2020 at 12:47
17
$\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.

$\endgroup$
1
  • $\begingroup$ Very nice solution! Can you do better? $\endgroup$ May 28, 2020 at 0:39
12
$\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.

$\endgroup$
4
  • $\begingroup$ Great start! I actually counted more steps. Just saw the edit. $\endgroup$ May 27, 2020 at 14:11
  • $\begingroup$ Thanks for the fix @msh210. You are quite right I miscounted, so it is even better than I thought. $\endgroup$ May 27, 2020 at 14:11
  • 2
    $\begingroup$ I actually wouldn't be surprised if this is optimal. This was the first thing I thought of. $\endgroup$ May 27, 2020 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$ May 27, 2020 at 15:17
9
$\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";
  }
}
$\endgroup$
3
  • $\begingroup$ My approach would be, find all shortest paths when only one square is painted ...find all shortest paths when two squares are painted ,etc. We then note down which shortest path turned out to be the longest . But I am unable to understand how to figure out the shortest path for a given configuration . Can you please tell me how to do so ? Secondly, for those who don't understand programming much, please explain how your programme works. $\endgroup$ Apr 24, 2021 at 5:50
  • $\begingroup$ Just noticed a pattern... Is it always 1 smaller than the number of squares in the grid? $\endgroup$
    – mathlander
    Jan 14, 2023 at 5:50
  • $\begingroup$ The pattern works also for 3, 2 and 1. Intriguing. $\endgroup$
    – Florian F
    Sep 22, 2023 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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