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

#define TOUCH       0  /* 1 arg */
#define ALIGNED     1  /* 2 arg */
#define NOT_ALIGNED 2  /* 2 arg */
#define CUBE        3

int *piece_constraints = (int[]){
  CUBE,
  CUBE, TOUCH, 0,
  CUBE, TOUCH, 1, NOT_ALIGNED, 0, 1,
  CUBE, TOUCH, 1, ALIGNED, 0, 1,
  -1
};

typedef struct {
  int x, y, z;
  int fx, fy, fz;    /* fx == -1 if not forced */
} pos_t;

int touch(pos_t *p, int p1, int p2)
{
  int dist = abs(p[p1].x - p[p2].x)
           + abs(p[p1].y - p[p2].y)
           + abs(p[p1].z - p[p2].z);
  return dist == 1;
}

int aligned(pos_t *p, int a, int b, int c)
{
  return p[b].x - p[a].x == p[c].x - p[b].x &&
         p[b].y - p[a].y == p[c].y - p[b].y &&
         p[b].z - p[a].z == p[c].z - p[b].z;
}

int constraints(pos_t *p, int l)
{
  int i = -1;
  int other;
  int p1, p2;
  int *cur = piece_constraints;
  int is_aligned;

  while (*cur != -1) {
    switch (*cur) {
    case CUBE:
      i++;
      if (i > l) return 1;
      /* check correct forced position */
      if (p[i].fx != -1 &&
          (p[i].fx != p[i].x ||
           p[i].fy != p[i].y ||
           p[i].fz != p[i].z))
        return 0;
      cur++;
      break;
    case TOUCH:
      other = cur[1];
      if (!touch(p, i, other)) return 0;
      cur += 2;
      break;
    case ALIGNED:
    case NOT_ALIGNED:
      is_aligned = *cur == ALIGNED;
      p1 = cur[1];
      p2 = cur[2];
      if (is_aligned != aligned(p, p1, p2, i)) return 0;
      cur += 3;
      break;
    }
  }

  return 1;
}

void solution(pos_t *p)
{
  int a[5][5][5];
  int i;
  int x, y, z;

  /* print canonical solution (order according to x, y, and z) */
  printf("  {");
  memset(a, 0, sizeof(a));
  for (i = 0; i < 4; i++) {
    if (a[p[i].x][p[i].y][p[i].z]) printf("no\n");
    a[p[i].x][p[i].y][p[i].z] = 1;
  }
  for (x = 0; x < 5; x++) for (y = 0; y < 5; y++) for (z = 0; z < 5; z++) {
    /* move center from (2,2,2) to (0,0,0 */
    if (a[x][y][z]) printf(" {%d, %d, %d, },", x - 2, y - 2, z - 2);
  }
  printf("},\n");
}

void go(pos_t *p, int cur, int busy[5][5][5])
{
  int x, y, z;

  if (cur == 4) { solution(p); return; }

  for (x = 0; x < 5; x++) for (y = 0; y < 5; y++) for (z = 0; z < 5; z++) {
    if (busy[x][y][z]) continue;
    busy[x][y][z] = 1;
    p[cur].x = x;
    p[cur].y = y;
    p[cur].z = z;
    if (constraints(p, cur)) go(p, cur+1, busy);
    busy[x][y][z] = 0;
  }
}

int main(void)
{
  pos_t p[4];
  int busy[5][5][5];

  memset(busy, 0, sizeof(busy));

  memset(p, -1, sizeof(p));
  /* force first small cube to (2,2,2) */
  p[0].fx = p[0].fy = p[0].fz = 2;
  go(p, 0, busy);

  memset(p, -1, sizeof(p));
  /* force second small cube to (2,2,2) */
  p[1].fx = p[1].fy = p[1].fz = 2;
  go(p, 0, busy);

  memset(p, -1, sizeof(p));
  /* force third small cube to (2,2,2) */
  p[2].fx = p[2].fy = p[2].fz = 2;
  go(p, 0, busy);

  return 0;
}