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';
}