Who invented the 3D maze puzzle that involves solving three 2D mazes simultaneously (probably mentioned in...

I own a plastic implementation and I have a copy of the article
somewhere around.  The box says "Oskar's Cube, invented by Dutch
computer wiz Oskar van Deventer..."  However, it also claims (c) 1991,
and I'm pretty sure of an older reference.

-- Izak van Langevelde <eezacque@xs4all.nl>

----------

I suspect you're thinking of Oskars Cube.  This was invented by Dutch
Puzzle Inventor Oskar van Deventer, probably back in the 80's (late?).
A commercial plastic version was produced in '94 by Crystal Lines P/L
of Australia and marketed until recently by Binary Arts Corporation in
the U.S. and Europe.  The puzzle should still be available.

-- Ray Bathke <bathke@villagegames.com>, Village Games, Camden Lock,
   London

----------

Yeah, this was Oscar (Oskar?) van Deventer.  My dad had that Scientific
American, and I remember the article you are talking about.  Much later
I found a plastic version on sale in toy shops, called Oscar's (or
maybe Oskar's) Cube.  I think the year of the Sci. Am. was 1978 but I'm
not sure.  There was also a section (maybe the same article) about a
three dimensional version of the right hand rule, which I think was
illustrated with a problem about Theseus and the Minotaur.

-- Geoff Bailey <ftww@cs.usyd.edu.au>

[ Editor: Paul Callahan's posting "C Program to solve "Oskar's Cube" 3D
maze puzzle" (rec.puzzles, January 1995), with his program, copied in
full. ]

I imagine I'm not the first person in the world to write a program to
do this, but I thought I'd post the source code anyway, since it took
a couple hours last night to get it running and debugged, and a little
more time to settle on the style of the output.  Anyone out there who
wants definitive solutions to the least number of moves between puzzle
positions may find this program useful (well, it's supposed to give
the least number of moves; let me know if there are problems).

For those who are not familiar with it, Oskar's Cube is a hollow cube
whose faces consist of mazes, each rendered in a 9x9 grid of blocks.
Opposite faces contain identical mazes (so there are three distinct
mazes, referred throughout this article as "face-mazes"), and these
mazes are traversed simulataneously using an intersection of three
mutually perpendicular bars, called the crossbeam.  It is very easy to
solve any one of the face-mazes by itself, but contraints imposed by
the other two mazes usually make it impossible to complete a simple
path in one face-maze without backtracking and changing position
within one of the other mazes.

Another way to view this (as noted in the instructions that come with
the puzzle) is that there is an internal "invisible" three-dimensional
maze.  This is also rendered in a grid (in this case, 9x9x9), and a
given grid cell is open if and only if the same cell is open when
projected on each of the face-mazes in turn.  Then, a cell is
accessible from another cell in the internal maze if and only if there
is a path from the source cell to the destination cell that uses only
open blocks (including the source and destination).

The program uses the above idea by explicitly considering the 9x9x9
maze and solving the shortest path problem within it.  In a single
move, we are allowed to slide the crossbeam as far as we like in any
one direction up to the contraints imposed by face-mazes. The position
of the crossbeam is given by coordinates (x,y,z), each in the range
0-8.  The program sets the origin at corner 5 (labeled that way on the
cube) and coordinates are interpreted by holding the green face up
with corner 5 in the upper left.  Then x increases from left to right,
y increases from top to bottom, and z increases with depth (vertical
distance from the observer).

The program assumes input is from standard I/O, and each line contains
a list of three coordinates.  The first line contains the coordinates
of the destination (since it solves shortest path to this point from
all others) and each additional line up to the end of the file
contains a starting position.  For each of these, the program outputs
a sequence of moves.  To change the destination, you must restart the
program.

A sequence of moves is given as a list of face-mazes, each labeled by
color and marked with "a" and "b".  Each face-maze is shown with
corner 5 in the upper left.  To perform a step in this sequence go to
the corresponding face-maze on the cube and move the crossbeam from "a"
to "b" within that face-maze while holding the remaining coordinate
fixed.

For example, to find the path from (0,0,0) (corner 5) to (6,6,6)
(the position marked by squares), you would supply the input:

6 6 6
0 0 0

The output would then be:

Sequence of moves from (0,0,0) to (6,6,6):
Green:
***********
*a......*.*
*.*.***.*.*
*.*.*.....*
***.*.*****
*.*.*.*...*
*.*.*.*.*.*
*b..*...*.*
*.***** *.*
*.*.....*.*
***********

Red:
***********
*......a..*
*.*****.***
*.*...*...*
*.*.*****.*
*.*.....*.*
***.***.*.*
*...*.*b..*
*.***.***.*
*...*.....*
***********

Blue:
***********
*......a..*
*.*****.***
*.*..b..*.*
*******.*.*
*.*...*...*
*.***.***.*
*.*.*.*...*
*.*.*.*.***
*.........*
***********

Red:
***********
*.........*
*.*****.***
*.*...*...*
*.*.*****.*
*.*....a*.*
***.***.*.*
*b..*.*...*
*.***.***.*
*...*.....*
***********

Blue:
***********
*.........*
*.*****.***
*.*....a*.*
*******.*.*
*.*...*...*
*.***.***.*
*.*.*.*b..*
*.*.*.*.***
*.........*
***********

Green:
***********
*......a*.*
*.*.***.*.*
*.*.*....b*
***.*.*****
*.*.*.*...*
*.*.*.*.*.*
*...*...*.*
*.***** *.*
*.*.....*.*
***********

Blue:
***********
*.........*
*.*****.***
*.*.....*.*
*******.*.*
*.*..b*...*
*.***.***.*
*.*.*.*...*
*.*.*.*.***
*......a..*
***********

Green:
***********
*.......*.*
*.*.***.*.*
*.*.*a....*
***.*.*****
*.*.*.*...*
*.*.*.*.*.*
*...*...*b*
*.***** *.*
*.*.....*.*
***********

Red:
***********
*.........*
*.*****.***
*.*...*...*
*.*.*****.*
*.*....a*.*
***.***.*.*
*...*b*...*
*.***.***.*
*...*.....*
***********

Blue:
***********
*.........*
*.*****.***
*.*.....*.*
*******.*.*
*.*...*...*
*.***.***.*
*.*.*.*..b*
*.*.*.*.***
*......a..*
***********

Red:
***********
*.........*
*.*****.***
*.*...*...*
*.*.*****.*
*.*.....*.*
***.***.*.*
*...*.*b..*
*.***.***.*
*...*a....*
***********


The rest of this posting is just the source code.  It should be
completely portable to any platform and C compiler.  Please let me know
if you have any problems, comments, improvements, etc.

#include <stdio.h>
#include <string.h>

#define LENGTH 9

typedef struct mazecl {int dist; struct mazecl *backptr;
                       short int x,y,z;} MazeCell;

  /* origin set to corner 5 of cube */

  /* xy face */
  static char green[][LENGTH+1]={
    ".......*.",
    ".*.***.*.",
    ".*.*.....",
    "**.*.****",
    ".*.*.*...",
    ".*.*.*.*.",
    "...*...*.",
    ".***** *.",
    ".*.....*."
    };

  /* yz face */
  static char red[][LENGTH+1]={
    ".........",
    ".*****.**",
    ".*...*...",
    ".*.*****.",
    ".*.....*.",
    "**.***.*.",
    "...*.*...",
    ".***.***.",
    "...*....."
    };

  /* zx face */
  static char blue[][LENGTH+1]={
    ".........",
    ".*****.**",
    ".*.....*.",
    "******.*.",
    ".*...*...",
    ".***.***.",
    ".*.*.*...",
    ".*.*.*.**",
    "........."
    };


main() {

  static MazeCell maze[LENGTH][LENGTH][LENGTH],*cell,*nextcell,*lastcell;
  int x,y,z;
  int startx,starty,startz;
  int marked_one;
  char s[100];

  /* initialize cell coordinates */
  for (x=0; x<LENGTH; x++)
    for (y=0; y<LENGTH; y++)
      for (z=0; z<LENGTH; z++){
        maze[x][y][z].x=x;
        maze[x][y][z].y=y;
        maze[x][y][z].z=z;
      }

  /* initialize distance entries */

#define MAXDIST LENGTH*LENGTH*LENGTH+1

  /* maximum possible distance to all unexamined cells */
  for (x=0; x<LENGTH; x++)
    for (y=0; y<LENGTH; y++)
      for (z=0; z<LENGTH; z++) maze[x][y][z].dist=MAXDIST;

  /* distance 0 to start cell */
  gets(s);
  sscanf(s,"%d %d %d",&startx,&starty,&startz);
  maze[startx][starty][startz].dist=0;


  /* perform search of maze by sweeping over
     maze repeatedly and reducing distance to each
     cell until no further reduction is possible */

  do {
    marked_one=0;


    for (x=0; x<LENGTH; x++)
      for (y=0; y<LENGTH; y++)
        for (z=0; z<LENGTH; z++) {
          if (maze[x][y][z].dist<MAXDIST) {
            marked_one|=update(maze,x,y,z, 1, 0, 0);
            marked_one|=update(maze,x,y,z,-1, 0, 0);
            marked_one|=update(maze,x,y,z, 0, 1, 0);
            marked_one|=update(maze,x,y,z, 0,-1, 0);
            marked_one|=update(maze,x,y,z, 0, 0, 1);
            marked_one|=update(maze,x,y,z, 0, 0,-1);
          }
        }

  } while (marked_one);


  while (gets(s)&&s[0]!='$') {
    int dir;
    int seen;

    sscanf(s,"%d %d %d",&x,&y,&z);
    if (x<0 || x>=LENGTH || y<0 || y>=LENGTH || z<0 || z>=LENGTH) {
       printf("Coordinate out of range\n");
       continue;
    }
    cell= &(maze[x][y][z]);

    if (cell->dist>=MAXDIST) {
       printf("Inaccessible cell\n");
       continue;
    }

    printf("Sequence of moves from ");
    outcell(*cell);
    printf(" to ");
    outcell(maze[startx][starty][startz]);
    printf(":\n");

    seen=0;

    lastcell=cell;
    while (cell!= &(maze[startx][starty][startz])) {

      nextcell=cell->backptr;
      if (cell->x!=nextcell->x) dir=0;
      else if (cell->y!=nextcell->y) dir=1;
      else dir=2;

      if (((seen|(1<<dir))&7) == 7) {
         outmove(lastcell,cell,seen);
         lastcell=cell;
         seen=0;
       }

      seen|=(1<<dir);

      cell=nextcell;
    }

    outmove(lastcell,cell);
    printf("\n");
  }

}


/* update distance to all cells accessible by one move */

int update(maze,x,y,z,dx,dy,dz)
MazeCell maze[LENGTH][LENGTH][LENGTH];
int x,y,z;
int dx,dy,dz;
{
MazeCell *cellfrom;
int marked_one=0;

  /* macro to determine if maze cell is blocked */
#define blocked(x,y,z) ((x<0)||(y<0)||(z<0)|| \
                        (x>=LENGTH)||(y>=LENGTH)||(z>=LENGTH) \
                          ||(green[y][x]=='*') \
                            ||(red[z][y]=='*') \
                              ||(blue[x][z]=='*') )

   cellfrom= &(maze[x][y][z]);

   while(1) {

     x+=dx; y+=dy; z+=dz;

     if (blocked(x,y,z)) break;

     if (cellfrom->dist+1 < maze[x][y][z].dist) {
        maze[x][y][z].dist=cellfrom->dist+1;
        marked_one=1;
        maze[x][y][z].backptr= cellfrom;
     }
   }

   return marked_one;
}



outcell(cell)
MazeCell cell;
{
  printf("(%d,%d,%d)",cell.x,cell.y,cell.z);
}



outmove(cell,nextcell,seen)
MazeCell *cell,*nextcell;
int seen;
{
static char side[LENGTH][LENGTH+1];
int i;
int ax,ay;
int bx,by;

   if (seen==3 || seen==2) {
     for (i=0; i<LENGTH; i++) strcpy(side[i],green[i]);
     ax=cell->x; ay=cell->y;
     bx=nextcell->x; by=nextcell->y;
     printf("Green: \n");
   }
   else if (seen==5 || seen==1) {
     for (i=0; i<LENGTH; i++) strcpy(side[i],blue[i]);
     ax=cell->z; ay=cell->x;
     bx=nextcell->z; by=nextcell->x;
     printf("Blue: \n");
   }
   else {
     for (i=0; i<LENGTH; i++) strcpy(side[i],red[i]);
     ax=cell->y; ay=cell->z;
     bx=nextcell->y; by=nextcell->z;
     printf("Red: \n");
   }

   side[ay][ax]='a';
   side[by][bx]='b';

   for (i=0; i<LENGTH+2; i++) printf("*");
   printf("\n");

   for (i=0; i<LENGTH; i++) printf("*%s*\n",side[i]);

   for (i=0; i<LENGTH+2; i++) printf("*");
   printf("\n");

   printf("\n");

}

-- Paul Callahan <callahan@biffvm.cs.jhu.edu>