//
// 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