Create a multi-level 5x5x5 Labyrinth with only one solution

Question

The aim of this challenge is to create the shortest code (in characters) that successfully do the following:

Specifications:

• Must create a 5x5x5 labyrinth with exactly 1 possible solution (no more, no less)
• The labyrinth must be created randomly It must be able to generate every existing solution if left running for years
• The start and finish must be placed in *opposite corners
• The map output must in one of the following formats:

Option output format 1 strings, printed or alerted:

xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx

Option output format 2 arrays:

[[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx]]

Output Notes:

• Use 0 for empty and 1 for squares

• Break lines are NOT necessary

• You decide what index is what, but just make sure to explain it well

---

*Here is an example of what I mean by opposite corners:

Clarifications:

• Can NOT move in diagonal
• Can NOT pass twice on the same path
• Having inaccessible areas is allowed
• You can go up/down more than one level in a row

Tips:

• Don't see them as walls, instead see them as a 5x5x5 stack of squares that some of them are missing and you can go through the missing ones

Answer 1

C++ C, about 1000 670 643 395 297 248 chars

Sample output:

00111,10011,10111,00110,11000,
11001,01010,00100,11011,10101,
10111,10101,10001,01010,00101,
11001,11110,11100,11110,10101,
11100,10010,11001,10101,00000,

How it works: The program uses Brownian Motion to generate solutions. The start point is set. Then, a random point is selected and repeatedly moved randomly until it touches one and only one point on the start branch. The point is then set, and if it also touches the end point, the program exits and the matrix displayed. Since no point can join two branches, there is only one path through the labyrinth. The program uses the rand function, and a command line integer argument as the seed, so with a sufficient rand function it should be possible to eventually generate all valid labyrinths (this algorithm will not create unconnected areas however, so it won't generate all possible labyrinths).

Brownian motion was dropped since it turned out to be unneeded and it's removal simplifies the code significantly. I do think it made nicer labyrinths though. Likewise, the seed argument was dropped, since requiring a stateless random number generator makes more sense to me than a 128-bit seed.

It is possible for the program to get stuck in an infinite loop, since it is possible for situations where any point added to the branches would create multiple paths. This is fixable, but I think that it is rare enough to not be a concern for code golf.

#define M m[*p+1][p[1]][p[2]]
#define F(a,b)for(p[a]=5;p[a]--;putchar(b))
#define f for(i=3;i--;p[i]
p[]={4,4,4},h[3],m[7][6][6]={1};
main(i){
    for(M=2;h[1]^1||(M=1)^h[2];){
        f=rand()%5)
            h[i]=0;
        f++)
            p[i]++,
            h[M]++,
            p[i]-=2,
            h[M]++;
    }
    F(0,10)
        F(1,44)
            F(2,48+!M);
}

I've added newlines and indentation to the displayed code for readability.

Answer 2

JavaScript, 874 816 788 686 682 668 637 characters

sample output:

00000,10111,10111,01010,11000
01011,01000,01010,01111,00011
00100,11010,00111,10111,11010
01111,10001,01110,01010,01000
00000,11110,00001,10101,10110

this one works by starting from point [0,0,0] and randomly adding attaching one more 0 next to an 0 wherever allowed (allowed==the new 0 is not next to any other 0s except the originator) until there are no more possible additions.

if any new 0 is next to the exit point (x*y*z == 48) then we open up the exit.

golfed

b=[]
I=Math.random
for(i=5;i--;)for(j=5,b[i]=[];j--;)b[i][j]=[1,1,1,1,1]
b[0][0][0]=0
k=[[0,0,0]]
function q(x,y,z){J=b[x]
if(x<0||y<0||z<0||x>4||y>4||z>4||!J[y][z])return 
n=6-!x||b[x-1][y][z]
n-=!y||J[y-1][z]
n-=!z||J[y][z-1]
n-=x==4||b[x+1][y][z]
n-=y==4||J[y+1][z]
n-=z==4||J[y][z+1]
n==1&&v.push([x,y,z])}while(I){F=k.length
B=k[C=0|I(v=[])*F]
x=B[0]
q(x-1,y=B[1],z=B[2])
q(x,y-1,z)
q(x,y,z-1)
q(x+1,y,z)
q(x,y+1,z)
q(x,y,z+1)
if(D=v.length){k.push(A=v[0|I()*D])
b[A[0]][A[1]][A[2]]=0
if(A[0]*A[1]*A[2]==48)b[4][4][4]=I=0}else{for(E=[];F--;)F^C&&E.push(k[F])
k=E}}for(i=25;i--;)b[H=0|i/5][i%5]=b[H][i%5].join('')
alert(b.join("\n"))

original

window.map=[];
for (i=0;i<5;++i) {
  map[i]=[];
  for (j=0;j<5;++j) {
    map[i][j]=[1,1,1,1,1];
  } 
} 
points=[[0,0,0]];
map[0][0][0]=0;
function spaces(x,y,z) {
  var n=6;
  if (x<0 || y<0 || z<0) return 0;
  if (x>4 || y>4 || z>4) return 0;
  if (!map[x][y][z]) return 0;
  if (!x || map[x-1][y][z]) n--;
  if (!y || map[x][y-1][z]) n--;
  if (!z || map[x][y][z-1]) n--;
  if (x==4 || map[x+1][y][z]) n--;
  if (y==4 || map[x][y+1][z]) n--;
  if (z==4 || map[x][y][z+1]) n--;
  return n;
} 
do {
  var index=Math.floor(Math.random()*points.length);
  point=points[index];
  v=[];
  x=point[0];
  y=point[1];
  z=point[2];
  spaces(x-1,y,z)==1 && v.push([x-1,y,z]);
  spaces(x,y-1,z)==1 && v.push([x,y-1,z]);
  spaces(x,y,z-1)==1 && v.push([x,y,z-1]);
  spaces(x+1,y,z)==1 && v.push([x+1,y,z]);
  spaces(x,y+1,z)==1 && v.push([x,y+1,z]);
  spaces(x,y,z+1)==1 && v.push([x,y,z+1]);
  if (v.length) {
    var point=v[Math.floor(Math.random()*v.length)];
    points.push(point);
    map[point[0]][point[1]][point[2]]=0;
    if (point[0]*point[1]*point[2]==48) {
      map[4][4][4]=0;
    } 
  } 
  else {
    var np=[];
    for (var i=0;i<points.length;++i) {
      i!=index && np.push(points[i]); 
    } 
    points=np;
  } 
} while(points.length);
for (i=0;i<5;++i) {
  for (j=0;j<5;++j) {
    map[i][j]=map[i][j].join('');
  } 
  map[i]=map[i].join();
} 
alert(map.join("\n"));

Answer 3

Mathematica: True Labyrinth (827 chars)

Originally, I produced a path from {1,1,1} to {5,5,5} but because there were no possible wrong turns to be made, I introduced forks or "decision points" (vertices of degree >2) where one would need to decide which way to go. The result is a true maze or labyrinth.

The "blind alleys" were far more challenging to solve than finding a simple, direct path. The most challenging thing was to eliminate cycles within the path while allowing cycles off the solution path.

The following two lines of code are only used for rendering the drawn graphs, so the code does not count, as it is not employed in the solution.

o = Sequence[VertexLabels -> "Name", ImagePadding -> 10, GraphHighlightStyle -> "Thick", 
    ImageSize -> 600];

o2 = Sequence[ImagePadding -> 10, GraphHighlightStyle -> "Thick", ImageSize -> 600];

Code used:

e[c_] := Cases[EdgeList[GridGraph[ConstantArray[5, 3]]], j_ \[UndirectedEdge] k_ /; (MemberQ[c, j] && MemberQ[c, k])]

m[] :=
Module[{d = 5, v = {1, 125}},
   While[\[Not] MatchQ[FindShortestPath[Graph[e[v]], 1, 125], {1, __, 125}],

v = Join[v, RandomSample[Complement[Range[125], v], 1]]];
   Graph[e[Select[ConnectedComponents[Graph[e[v]]], MemberQ[#, 1] &][[1]]]]]

w[gr_, p_] := EdgeDelete[gr, EdgeList[PathGraph[p]]]

y[p_, u_] := Select[Intersection[#, p] & /@ ConnectedComponents[u], Length[#] > 1 &]

g = HighlightGraph[lab = m[],  PathGraph[s = FindShortestPath[lab, 1, 125]],o]
u = w[g, s]
q = y[s, u]

While[y[s, u] != {}, u =  EdgeDelete[u, Take[FindShortestPath[u,  q[[1, r = RandomInteger[Length@q[[1]] - 2] + 1]], 
  q[[1, r + 1]]], 2] /. {{a_, b_} :> a \[UndirectedEdge] b}];

q = y[s, u]]

g = EdgeAdd[u, EdgeList@PathGraph[s]];

Partition[StringJoin /@ Partition[ReplacePart[Table["x", {125}], 
Transpose[{VertexList[g], Table["o", {Length[VertexList@g]}]}]/. {{a_, b_} :>  a -> b}], {5}], 5]

Sample output

{{"oxooo", "xxooo", "xoxxo", "xoxxo", "xxoox"}, {"ooxoo", "xoooo", "ooxox", "oooxx", "xooxx"}, {"oooxx", "ooxxo", "ooxox", "xoxoo", "xxxoo"}, {"oxxxx", "oooox", "xooox", "xoxxx", "oooxx"}, {"xxxxx", "ooxox", "oooox", "xoxoo", "oooxo"}}

Under the hood

The picture below shows the labyrinth or maze that corresponds to the solution ({{"ooxoo",...}} displayed above:

Here is the same labyrinth inserted in a 5x5x5 GridGraph. The numbered vertices are nodes on the shortest path out of the labyrinth. Note the forks or decision points at 34, 64, and 114. I'll include the code used for rendering the graph even though it is not part of the solution:

HighlightGraph[gg = GridGraph[ConstantArray[5, 3]], g,  
 GraphHighlightStyle ->"DehighlightFade", 
 VertexLabels -> Rule @@@ Transpose[{s, s}] ]

And this graph shows only the solution to the labyrinth:

HighlightGraph[gg = GridGraph[ConstantArray[5, 3]], 
   Join[s, e[s]], GraphHighlightStyle -> "DehighlightFade", VertexLabels -> Rule @@@    Transpose[{s, s}] ]

Finally, some definitions that may help reading the code:

---

Original solution (432 char, Produced a path but not a true maze or labyrinth)

Imagine a 5x5x5 large solid cube made up of distinct unit cubes. The following begins without unit cubes at {1,1,1} and {5,5,5}, since we know they must be part of the solution. Then it removes random cubes until there is an unimpeded path from {1,1,1} to {5,5,5}.

The "labyrinth" is the shortest path (if more than one is possible) given the unit cubes that have been removed.

d=5
v={1,d^3}
edges[g_,c_]:=Cases[g,j_\[UndirectedEdge] k_/;(MemberQ[c,j]&&MemberQ[c,k])]

g:=Graph[v,edges[EdgeList[GridGraph[ConstantArray[d,d]]],v]];

While[\[Not]FindShortestPath[g,1,d^3]!={},
    v=Join[v,RandomSample[Complement[Range[d^3],v],1]]]

Partition[Partition[ReplacePart[
   Table["x",{d^3}],Transpose[{FindShortestPath[g,1,d^3],Table["o",{Length[s]}]}]
      /.{{a_,b_}:>  a->b}],{d}]/.{a_,b_,c_,d_,e_}:>  StringJoin[a,b,c,d,e],5]

Example:

{{"ooxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxx"}, 
 {"xoxxx", "xoooo", "xxxxo", "xxxxo", "xxxxo"}, 
 {"xxxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxo"}, 
 {"xxxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxo"}, 
 {"xxxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxo"}}

Technically this is not yet a true labyrinth, since there are no wrong turns that one can make. But I thought it interesting as a start since it relies on graph theory.

The routine actually makes a labyrinth but I plugged up all empty locations that could give rise to cycles. If I find a way to remove cycles I will include that code here.