Say you have a 4x4 grid.  How would you generate a path so that every tile is touched once?

Rules:

• You can start and end anywhere, just not the same tile
• You can go off one side and resume on the opposite side.  You don't have to use this but you're encouraged to (this is also easily fixed by shifting the path either vertically or horizontally)
• You must use all 16 tiles once and only once (no crossing paths)

I could probably do something like this with a recursive function but the problem is that sometimes you'd end up with the following situation where you'd trap yourself:

How would you prevent this?  It's easy enough to detect; you haven't generated a path on all 16 tiles.  You can brute force it then by starting over and hoping it doesn't happen often.  But what's the proper way to do this?

1 hour ago, GameCreator said:

How would you prevent this?  It's easy enough to detect; you haven't generated a path on all 16 tiles.  You can brute force it then by starting over and hoping it doesn't happen often.  But what's the proper way to do this?

Don't throw away everything and start over -- backtrack. When you hit a dead-end without covering all 16 tiles, backup a step and choose a different direction than you did before. If all possible choices lead to dead-ends then back-up another step and try a different choice from there. Back up (recursively) as far as you need to until you find a solution.

Google "backtracking algorithms" if you want more examples.

If you simply restart when you get stuck, you only fail about 2/3 or the time.

This code produces a sequence of moves that will fill the 4x4 grid. You can start anywhere:

#include <iostream>
#include <vector>
#include <cstdint>

enum Direction {N, S, W, E};

std::ostream &operator<<(std::ostream &os, Direction d) {
  switch (d) {
  case N: return os << 'N';
  case S: return os << 'S';
  case W: return os << 'W';
  case E: return os << 'E';
  }
  return os << '?';
}

uint16_t shift(uint16_t x, Direction d) {
  switch (d) {
  case N: return (x<<4) | (x>>12);
  case S: return (x<<12) | (x>>4);
  case W: return ((x&0x7777)<<1) | ((x&0x8888)>>3);
  case E: return ((x&0x1111)<<3) | ((x&0xeeee)>>1);
  }
  throw "Invalid direction";
}

bool recursive_random_path(uint16_t o, std::vector<Direction> &history) {
  o |= uint16_t(1);
  if (o == 0xffff)
    return true;
  bool N_allowed = !(o & (uint16_t(1) << 12));
  bool S_allowed = !(o & (uint16_t(1) << 4));
  bool W_allowed = !(o & (uint16_t(1) << 3));
  bool E_allowed = !(o & (uint16_t(1) << 1));
  int num_allowed = N_allowed + S_allowed + W_allowed + E_allowed;

  if (num_allowed == 0)
    return false;
  
  int r = std::rand() % num_allowed;
  
  if (N_allowed && r == 0) {
    history.push_back(N);
    return recursive_random_path(shift(o,N), history);
  }
  r -= N_allowed;
  
  if (S_allowed && r == 0) {
    history.push_back(S);
    return recursive_random_path(shift(o,S), history);
  }
  r -= S_allowed;
  
  if (W_allowed && r == 0) {
    history.push_back(W);
    return recursive_random_path(shift(o,W), history);
  }
  r -= W_allowed;
  
  history.push_back(E);
  return recursive_random_path(shift(o,E), history);
}

std::vector<Direction> random_path() {
  while (1) {
    std::vector<Direction> history;
    if (recursive_random_path(0, history))
      return history;
  }
}

int main() {
  for (auto step : random_path())
    std::cout << step;
  std::cout << '\n';
}

Interesting.  Yes, it makes sense to backtrack and so you'd have to do several attempts to find a path that doesn't end in failure.  Given alvaro's statement, it might be faster to just start from scratch, given the size of the grid and so the odds of success.  alvaro, thank you very much for the code.

You only have to start at one position, the others can be constructed by shifting the resulting grids. If you add rotation of the result, the initial direction can be fixed too.

And yeah, for 16 positions, recursively brute-forcing all directions is the simple solution.

8 hours ago, Alberth said:

You only have to start at one position, the others can be constructed by shifting the resulting grids. If you add rotation of the result, the initial direction can be fixed too.

If you add mirror symmetry, the first direction that is different than the initial direction can be fixed too. All in all, there are 714 different paths.

I guess this is a minimal example, but are there any more conditions that you didn't mention? Will there be roadblocks in the grid, do you want multiple different paths, will the grid change shape somehow? Because, if you only need a single path that covers an empty grid, the "simple and stupid" solution is to just hardcode one that works, like this one:

Are there any reasons why you can't do that?

1024 said:
I guess this is a minimal example, but are there any more conditions that you didn't mention? Will there be roadblocks in the grid, do you want multiple different paths, will the grid change shape somehow? Because, if you only need a single path that covers an empty grid, the "simple and stupid" solution is to just hardcode one that works ... Are there any reasons why you can't do that?

True. There are two related reasons though. One is general replayability. The second is that the puzzle is timed. If the player doesn't solve the puzzle in time, I don't want him to be able to restart and just redo the first several moves because he remembers what they were.

By the way, I did create several manually generated versions in Photoshop (before I posted the question), knowing that I could randomly shift/mirror/rotate the path. Just having a handful of paths to start from would create a lot of possibilities. But generating the path (especially if I can brute force it) isn't too hard.