//
//  Schlangenspiel
//
//  Solves the "Schlangen" game
//  Ronald Holzloehner, 10 March 2004
//  (c) Copyright 2004
//
//   The Schlange game consists of a string of 27 wooden cubes.
//  The cubes can be rotated against each other. The string can
//  be thought of as consisting of 17 straight segments, in which
//  the cubes form a straight row. In between these straight segments,
//  the direction of the string changes by 90 degrees. Starting from
//  one side of the string, the lengths of the straight sequences (number
//  of cubes) are
//  3-1-1-2-1-2-1-1-2-2-1-1-1-2-2-2-2
//  Note that this sequence is not symmetric.
//  It is the purpose of the game to arrange the string into 3x3x3 cube
//  similar to Rubick's cube.
//
//   To solve this problem, it is actually easier to start from the other
//  side: Doing a few twists and turn, it becomes obvious that the last
//  cube must sit in a corner of the final 3x3x3 cube.
//  Suppose you are looking a face of the 3x3x3 cube. Let's denote
//  the direction from left to right by +0, from left to right by -0,
//  front to back by +2, back to front by -2, from down to up by +1,
//  and up to down by -1. Give a wooden cube that sits in the left lower
//  front corner the coordinates (0,0,0), then position the first three
//  wooden cubes to the right so that the third one occupies the cell 
//  (2,0,0). The second segment, or branch, goes to (2,2,0). All other
//  arrangements would obviously just be rotations or mirrors of this
//  beginning. However, one has the choice now to turn the third branch
//  either in direction -0 so that it ends at (0,2,0), or in direction
//  +2 so that it ends at (2,2,2). From here on, a tree of possiblities
//  starts. At least one of the leaves hopefully fills the 3x3x3 cube.
//
//   Variables below: 
//    dir:		direction of a branch (0 = left/right, 1 = front/back, 2 = up/down)
//    orientation:		orientation (positive or negative,
//       e.g. +1 = left to right, -1 opposite)
//    dir_try:	tentative direction of the following branch
//    orientation_try:  tentative orientation  of the following branch
//    dir_try_start:    tentative direction to start with at given level
//    orientation_try_start: same for the orientation
//    cells[]:     Boolean array, "1" if cube is filled, "0" otherwise
//    branch_try:  index of branch to try
//    branch_lengths[]:  list of branch lengths, starting from one side
//    pos[]:  coordinates of the beginning of currently tried branch
//
//   The program runs through the entire tree, checking 342 configurations.
//   Information is printed on the screen. The depth of the current branch
//   in the tree is shown by the number of whitespace characters preceding
//   each line.
//
//   Solution: Start at the 3-1 side. Place the first branch in the right
//   upper front corner of the 3x3x3 cube. Then take the directions
//   -1  -0  +1  -2  -0  +2  -1  -2  +0  +1  -0  +2  -0  -2  +0  -1  -0 
//   This is the only solution, not counting rotations and mirrored images.


#include <iostream.h>
#include <math.h>
#include <stdio.h>
#include <math.h>

// cube length
#define LEN 3

// dimension of cube
#define DIM   3

// number of branchs
#define BRANCH_NUM   17
// index of first branch to vary
#define BRANCH_START     2
// the first two paths
#define PATH_0      (0+1)
#define PATH_1      (1+1)
#define POS_0       2
#define POS_1       2
#define POS_2       0

#define DIR_START		1
#define DIR_TRY_START		0
#define ORIENTATION_START		1
#define ORIENTATION_TRY_START		-1

// macro to convert from coordinates in 3x3x3 cube to array index in cells[]
#define coord(x,y,z) ((x) + (y)*LEN + (z)*(LEN*LEN))

// template to initialize an array; see bottom of file
template<class T> inline void init_zero(T* in, size_t t);


int solve(void)
{
    unsigned long trial_num = 0UL;
    unsigned long solution_num = 0UL;
    // branch configuration
    const int branch_lengths[] = {3,2,2,2,1,1,1,2,2,1,1,2,1,2,1,1,2};
    // position of current last element
    int pos[DIM];
    pos[0] = POS_0;
    pos[1] = POS_1;
    pos[2] = POS_2;
    // path taken so far
    int path[BRANCH_NUM];
    init_zero(path, BRANCH_NUM);
    path[0] = PATH_0;
    path[1] = PATH_1;
    
    int branch_try = BRANCH_START;
    int dir = DIR_START;
    int orientation = ORIENTATION_START;
    int dir_try_start = DIR_TRY_START;
    int orientation_try_start = ORIENTATION_TRY_START;

    // the "cells" structure
    const int cell_num = int(rint(pow(double(LEN),double(DIM))));
    bool  *cells = new bool[cell_num];
    init_zero(cells, cell_num);
    cells[coord(0,0,0)] = cells[coord(1,0,0)] = cells[coord(2,0,0)] = 1;
    cells[coord(2,1,0)] = cells[coord(2,2,0)] = 1;
    
    cout << "Cube length: " << LEN << ", dimension: " << DIM
        << ", # of cells: " << cell_num << endl << endl;
    int sum1 = 0;
    for(int k=0; k<BRANCH_NUM; k++)
      sum1 += branch_lengths[k];
    if(sum1 != cell_num)
    {
        cerr << "ERROR: Sum of branch lengths (" << sum1 << ") must equal number of cells!" << endl;
        exit(-1);
    }
        
    char spacer[BRANCH_NUM+1]; // whitespace characters
    int skip2 = 0;
    // main loop
    do{
          int branch_lengths_l = branch_lengths[branch_try];
          bool *cells_l = cells + coord(pos[0], pos[1], pos[2]);
          
          for(int l=0; l < branch_try - BRANCH_START; l++)
          	spacer[l] = ' '; // fill in whitespace characters
   	    spacer[branch_try - BRANCH_START] = 0;
          printf("%sdir: %c%d, branch_try: %d, pos: [%d %d %d]\n",
          	spacer, ((orientation>0)? '+':'-'), dir, branch_try, pos[0], pos[1], pos[2]);
          
          for(int orientation_try = orientation_try_start; orientation_try <= 1; orientation_try +=2)
          {
           	const int branch_step = orientation_try * branch_lengths_l;
            for(int dir_try = dir_try_start; dir_try < DIM; dir_try++)  // try all directions
            {
            	if(dir_try == dir)
               	continue;
             
            	printf("%s  Trying dir: %c%d -- ",
            		spacer, ((orientation_try>0)? '+':'-'), dir_try);
             
 	            // the coordinate in the direction the branch will be taken
	             const int pos_dir_try = pos[dir_try] + branch_step;
	             // bounds test: see if end piece extends beyond cube
	             if(pos_dir_try < 0 || pos_dir_try >= LEN)  // last element out of bounds?
	             {
	               // count this as tree leaf
	               trial_num++;
	               printf("Out of bounds: %d\n", pos_dir_try);
	               continue;
	             }
	             
	             // collision test: try each new cell for a collision
	             const int skip = orientation_try
           		 	* ((dir_try==0)? 1:((dir_try==1)? LEN:(LEN*LEN)));
	             for(int i = 1; i <= branch_lengths_l; i++)
	               if(*(cells_l + i*skip))
	               {
	                  // count this as tree leaf
	                  trial_num++;
	                  printf("Collision at: %d\n", i);
	                  goto next_dir;  // collision found
	               }
	             
                  path[branch_try] = orientation_try * (dir_try + 1);
	             	if(branch_try < BRANCH_NUM-1)
		             {
		             	// accept this branch; recurse
			             dir = dir_try;
			             orientation = orientation_try;
			             pos[dir] = pos_dir_try;
			             orientation_try_start = -1;
			             dir_try_start = 0;
			             branch_try++;
			             // mark all new cells in this branch as occupied
			             for(int i2 = 1; i2 <= branch_lengths_l; i2++)
			               *(cells_l + i2*skip) = 1;
			             
			             printf("Accepted!\n");
			             goto next_branch; // start new iteration in main loop
	             	}
	             	else  // success
	             	{
	             		// count this as tree leaf
	             		trial_num++;
	             		solution_num++;
	             		cout << "\n\n*** Solution: (put it together starting from the last item)\n";
	             		for(int j=0; j<BRANCH_NUM; j++)
	             			cout << "\t" << branch_lengths[j]
                 			<< "\t" << ((path[j]>0)? '+':'-') << (abs(path[j])-1) << endl;
	           			cout << endl << endl;
	           			system("PAUSE");
	           			goto kill_branch;
	       			}
                      
	             next_dir:
	             1;   // dummy statement for compiler: a label must be followed by a statement
           }//for(dir_try)
           dir_try_start = 0;
          }//for(orientation_try)      
          
          // no new branch could be added --> kill the current branch
          kill_branch:
          
          path[branch_try] = 0;
          branch_try--;
          branch_lengths_l = branch_lengths[branch_try];
          pos[dir] -= branch_lengths_l * orientation; // restore previous value
          if(pos[dir] < 0 || pos[dir] >= LEN)
       	 {
       	 	cerr << "\n\nERROR: pos[dir] < 0 || pos[dir] >= LEN" << endl;
       	 	exit(-1);
     	    }
          cells_l = cells + coord(pos[0], pos[1], pos[2]);
          // use the old dir to determine the skip
          skip2 = orientation * ((dir==0)? 1:((dir==1)? LEN:(LEN*LEN)));
          // free all cells in this branch
          for(int i3 = 1; i3 <= branch_lengths_l; i3++)
         	*(cells_l + i3*skip2) = 0;
          
          
          // continue search from next direction
          dir_try_start = dir + 1; // CAUTION: dir_try_start might equal DIM now (out of bounds)
          orientation_try_start = orientation;
          dir = abs(path[branch_try-1]) - 1; // try next direction in previous branch
          orientation = (path[branch_try-1] > 0) ? 1:-1;
   	    
          printf("%sKilled this branch. Dir now: %c%d\n\n",
            spacer, ((orientation>0)? '+':'-'), dir);
          
          // jump here in case of success
          next_branch:
          1; // dummy statement for compiler: a label must be followed by a statement
          
          int p, sum2=0, sum3=0;
          for(p=0; p<cell_num; p++)
          	sum2 += cells[p];
          for(p=0; p < branch_try; p++)
          	sum3 += branch_lengths[p];
       	if(sum2 != sum3)
       	{
       		printf("ERROR! sum2: %d, sum3: %d\n", sum2, sum3);
       		exit(-1);
       	}
          
    }while(! (branch_try == BRANCH_START-1) );
    cout << "\n\n\nChecked " << trial_num << " configurations, found "
    	<< solution_num << " solution(s). Completed." << endl;
     
    delete[] cells;
    return 0;
}

// template to initialize an array
template<class T> inline void init_zero(T* in, size_t t)
{
  register T* T_end = in+t;
  for(; in<T_end; in++)
    *in = T(0);
}
// End of file