Oh, you ask what is a snake cube puzzle? A Google image search should give you an idea.
I wont put the solution here, you might be tempted to try it instead of trying to solve it yourself...
However the code is here:
#!/bin/perl
# What : Snake Cube Solver
# Who : baswarna
# When : 06-Sep-2011
# Where: Bangalore
#
use POSIX;
#use strict;
################## DATA structures ##################
# Segments representation --> Hash with following entries
# segnum : Segment number in the range of 0 to 16 (for the cube with 17 segments) I am having
# taillen : Tail legnth of the segment (1 or 2 for 3X3X3 cube)
# fc : Fulcrum co-ordinate
# spin : Axis on which the segment can be rotated (x or y or z)
# moves : list of moves, along with a flag indicating whether the move has been tried
# mvfound : Flag indicating that the moves have been found for this segment
# mvtaken : Indicates which of the allowed moves was taken
# bounds : 2D array with boundary entries for x, y and z (lower, upper)
@seg = (
{ segnum => 0, taillen => 2, mvfound => 0, mvtaken => -1, bounds => [[-2, 2], [-2, 2], [-2, 2]], fc => [0, 0, 0], spin => 'y'},
{ segnum => 1, taillen => 1, mvfound => 0, mvtaken => -1, bounds => [[-2, 2], [-2, 2], [-2, 2]]},
{ segnum => 2, taillen => 1, mvfound => 0, mvtaken => -1, bounds => [[-2, 2], [-2, 2], [-2, 2]]},
{ segnum => 3, taillen => 2, mvfound => 0, mvtaken => -1, bounds => [[-2, 2], [-2, 2], [-2, 2]]},
{ segnum => 4, taillen => 1, mvfound => 0, mvtaken => -1, bounds => [[-2, 2], [-2, 2], [-2, 2]]},
{ segnum => 5, taillen => 2, mvfound => 0, mvtaken => -1, bounds => [[-2, 2], [-2, 2], [-2, 2]]},
{ segnum => 6, taillen => 1, mvfound => 0, mvtaken => -1, bounds => [[-2, 2], [-2, 2], [-2, 2]]},
{ segnum => 7, taillen => 1, mvfound => 0, mvtaken => -1, bounds => [[-2, 2], [-2, 2], [-2, 2]]},
{ segnum => 8, taillen => 2, mvfound => 0, mvtaken => -1, bounds => [[-2, 2], [-2, 2], [-2, 2]]},
{ segnum => 9, taillen => 2, mvfound => 0, mvtaken => -1, bounds => [[-2, 2], [-2, 2], [-2, 2]]},
{ segnum => 10, taillen => 1, mvfound => 0, mvtaken => -1, bounds => [[-2, 2], [-2, 2], [-2, 2]]},
{ segnum => 11, taillen => 1, mvfound => 0, mvtaken => -1, bounds => [[-2, 2], [-2, 2], [-2, 2]]},
{ segnum => 12, taillen => 1, mvfound => 0, mvtaken => -1, bounds => [[-2, 2], [-2, 2], [-2, 2]]},
{ segnum => 13, taillen => 2, mvfound => 0, mvtaken => -1, bounds => [[-2, 2], [-2, 2], [-2, 2]]},
{ segnum => 14, taillen => 2, mvfound => 0, mvtaken => -1, bounds => [[-2, 2], [-2, 2], [-2, 2]]},
{ segnum => 15, taillen => 2, mvfound => 0, mvtaken => -1, bounds => [[-2, 2], [-2, 2], [-2, 2]]},
{ segnum => 16, taillen => 2, mvfound => 0, mvtaken => -1, bounds => [[-2, 2], [-2, 2], [-2, 2]]});
# moves_stack : stack of hashes with following entries (segnum, fc, pos)
@moves_stack = ();
# positions_taken : For marking the positions taken. 5X5X5 (2n-1) for 3X3X3 cube
@positions_taken = ( [ [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0] ],
[ [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0] ],
[ [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0] ],
[ [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0] ],
[ [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0] ] );
# main : Main routine
# segidx : Pointing to the segment currently being considered
my $segidx = 0;
CUBE: while(1) {
$curseg = $seg[$segidx];
$nexseg = $seg[$segidx+1];
# if mvfound is not true find moves for curseg
if($curseg->{mvfound} == 0) {
&find_moves($curseg);
# set as true, the move found flag
$curseg->{mvfound} = 1;
}
# Initialize the starting index for the remaining moves to be tried
$mvstart = $curseg->{mvtaken} + 1;
my $i;
# foreach move
MOVE: for($i = $mvstart; $i <= 5; $i++) {
# continue if the move is not valid
next if($curseg->{moves}->[$i] == 0);
# Find positions needed for the blocks of this segment
&pos_needed($curseg, $i);
# If not overalapping and not out of bounds
if( (&check_overlap($curseg->{pos}, $curseg->{taillen}) == 0) &&
(&check_bounday_violation($curseg) == 0) ) {
# set mvtaken to current move index
$curseg->{mvtaken} = $i;
# mark position in the matrix
&mark_pos($curseg->{pos}, $curseg->{taillen}, 1);
# Update bounds
&update_bounds($curseg, $i);
# push move in to moves_stack
push(@moves_stack, [$curseg->{segnum}, $curseg->{mvtaken}, $curseg->{fc}, $curseg->{pos}, $curseg->{taillen}]);
# print_move("Added ", $curseg->{segnum}, $curseg->{mvtaken}, $curseg->{fc}, $curseg->{pos}, $curseg->{taillen}) ;
# print_bounds($segidx);
# print_pos_taken();
# get out of looping if all the segments are placed
if($segidx == 16) {
last CUBE;
} else {
# update next segment spin and fc if not last segment
&update_next_seg($curseg, $nexseg, $i) if($segidx <= 16);
# Copy the curseg boundaries to nexseg
©_bounds($curseg, $nexseg);
# increment segidx
$segidx++;
# go ahead to handling of next segment
next CUBE;
}
} else {
next MOVE; # if overlapping or out of bound try next move
}
}
# if none of the moves workout backtrack as follows
# set mvfound false
$curseg->{mvfound} = 0;
# Initialize mvtaken
$curseg->{mvtaken} = -1;
# Decrement segidx
$segidx--;
# segidx < 0 flag error and stop
if($segidx < 0) {
print "Oosht\n";
exit;
}
# for the previous segment:
# Previous segment
$prevseg = $seg[$segidx];
# Delete positions in matrix
&mark_pos($prevseg->{pos}, $prevseg->{taillen}, 0);
# revert bounds to their previous value
if($segidx > 0) {
# taking it from prev-1 if prev != 0
©_bounds($seg[$segidx-1], $prevseg);
} else {
# setting it to default if prev == 0
$prevseg->{bounds} = [[-2, 2], [-2, 2], [-2, 2]];
}
# Delete the top entry from moves_stack
my $x = pop(@moves_stack);
# print_move("Deleted", $x->[0], $x->[1], $x->[2], $x->[3], $x->[4]) ;
# print_bounds($segidx);
# print_pos_taken();
# go ahead to handling of previous segment
} # End of while
# Print the moves_stack in the right order
foreach $x (@moves_stack) {
print_move("Solved ", $x->[0], $x->[1], $x->[2], $x->[3], $x->[4]) ;
}
##################### Functions ####################
#
# find_moves : Find the full set of available moves
sub find_moves
{
# Choose the four possible moves, based on the spin, direction and sign
# Encoding: x+, x-, y+, y-, z+, z-
my $curseg = $_[0];
my $spin = $curseg->{spin};
($curseg->{moves} = [0, 0, 1, 1, 1, 1] ) if ($spin eq 'x');
($curseg->{moves} = [1, 1, 0, 0, 1, 1] ) if ($spin eq 'y');
($curseg->{moves} = [1, 1, 1, 1, 0, 0] ) if ($spin eq 'z');
}
# pos_needed : Find out the block positions to be taken
sub pos_needed
{
my $curseg = $_[0];
my $mvidx = $_[1];
my $fc = $curseg->{fc};
(@shft = ([1, 0, 0], [2, 0, 0])) if($mvidx == 0);
(@shft = ([-1, 0, 0], [-2, 0, 0])) if($mvidx == 1);
(@shft = ([0, 1, 0], [0, 2, 0])) if($mvidx == 2);
(@shft = ([0, -1, 0], [0, -2, 0])) if($mvidx == 3);
(@shft = ([0, 0, 1], [0, 0, 2])) if($mvidx == 4);
(@shft = ([0, 0, -1], [0, 0, -2])) if($mvidx == 5);
# Positions are found for only the tail blocks, the fulcrum/hinge's position
# is not in contention. Hence there are only two co-ordinae entries in $pos
$curseg->{pos} = [ [ $fc->[0]+$shft[0][0], $fc->[1]+$shft[0][1], $fc->[2]+$shft[0][2] ],
[ $fc->[0]+$shft[1][0], $fc->[1]+$shft[1][1], $fc->[2]+$shft[1][2] ] ];
}
# check_bounday_violation : Check if the required positions are within the boundaries
sub check_bounday_violation
{
my $curseg = $_[0];
my $pos = $curseg->{pos};
# Need to check boundary violation only for the block at the edge
my $edgeidx = $curseg->{taillen}-1;
my $x = $pos->[$edgeidx]->[0];
my $y = $pos->[$edgeidx]->[1];
my $z = $pos->[$edgeidx]->[2];
# Current boundaries
my $xl = $curseg->{bounds}->[0][0];
my $xh = $curseg->{bounds}->[0][1];
my $yl = $curseg->{bounds}->[1][0];
my $yh = $curseg->{bounds}->[1][1];
my $zl = $curseg->{bounds}->[2][0];
my $zh = $curseg->{bounds}->[2][1];
# Return 1 if there is a boundary violation
if( ($x < $xl) || ($x > $xh) || ($y < $yl) || ($y > $yh) || ($z < $zl) || ($z > $zh) ) {
return 1;
} else {
return 0;
}
}
# update_bounds : Update the boundaries, if changed over the existing
sub update_bounds
{
my $curseg = $_[0];
my $mvidx = $_[1];
my $pos = $curseg->{pos};
my $spin = $curseg->{spin};
my $direction = floor($mvidx/2); # idx 0,1 --> x; 2,3 --> y; 4,5 --> z
my $edgeidx = $curseg->{taillen}-1;
my $edge = $pos->[$edgeidx]->[$direction];
my $fc = $curseg->{fc}->[$direction];
# second index: 0 --> lower; 1 --> higher
$curseg->{bounds}->[$direction][0] = ($edge - 2)
if( ($edge > $fc) && ( ($edge - 2) > $curseg->{bounds}->[$direction][0] ) ) ;
$curseg->{bounds}->[$direction][1] = ($edge + 2)
if( ($edge < $fc) && ( ($edge + 2) < $curseg->{bounds}->[$direction][1] ) ) ;
}
# copy_bounds : Copy bound entries from one seg to other seg
sub copy_bounds
{
my $srcseg = $_[0];
my $dstseg = $_[1];
my $i = 0;
my $j = 0;
for ($i = 0; $i <= 2; $i++) {
for ($j = 0; $j <= 1; $j++) {
$dstseg->{bounds}->[$i][$j] = $srcseg->{bounds}->[$i][$j];
}
}
}
# check_overlap : Check if any of the needed positions overlaps on an existing block
sub check_overlap
{
my $pos = $_[0];
my $taillen = $_[1];
my $i;
for($i = 0; $i <= $taillen-1; $i++) {
# Return 1 if there is a overlap
return 1 if ($positions_taken[$pos->[$i]->[0]][$pos->[$i]->[1]][$pos->[$i]->[2]]);
}
return 0;
}
# mark_pos : Mark/Clear the positions taken by the current segment
sub mark_pos
{
my $pos = $_[0];
my $taillen = $_[1];
my $val = $_[2];
my $i;
for($i = 0; $i <= $taillen-1; $i++) {
$positions_taken[$pos->[$i]->[0]][$pos->[$i]->[1]][$pos->[$i]->[2]] = $val;
}
}
# update_next_seg : Update the spin and fc of the next segment based on the chosen move
sub update_next_seg
{
my $curseg = $_[0];
my $nexseg = $_[1];
my $mvidx = $_[2];
my $pos = $curseg->{pos};
my $direction = floor($mvidx/2); # idx 0,1 --> x; 2,3 --> y; 4,5 --> z
my $edgeidx = $curseg->{taillen}-1;
my $edge = $pos->[$edgeidx];
$nexseg->{spin} = 'x' if($direction == 0);
$nexseg->{spin} = 'y' if($direction == 1);
$nexseg->{spin} = 'z' if($direction == 2);
$nexseg->{fc}->[0] = @$edge[0];
$nexseg->{fc}->[1] = @$edge[1];
$nexseg->{fc}->[2] = @$edge[2];
}
# Subroutine for printing move details
sub print_move
{
my $text = $_[0];
my $segnum = $_[1];
my $mvtaken = $_[2];
my $fc = $_[3];
my $pos = $_[4];
my $taillen = $_[5];
print($text." : ".$segnum." : ".$taillen." : ".$mvtaken." : ");
print("(".$fc->[0].", ".$fc->[1].", ".$fc->[2]."), ");
for($i = 0; $i <= $taillen-1; $i++) {
print("(".$pos->[$i]->[0].", ".$pos->[$i]->[1].", ".$pos->[$i]->[2]."), ");
}
print "\n";
}
sub print_bounds
{
my $bounds = $seg[$_[0]]->{bounds};
for ($i = 0; $i <= 2; $i++) {
for ($j = 0; $j <= 1; $j++) {
print($bounds->[$i][$j].", ");
}
}
print "\n";
}
sub print_pos_taken
{
for ($i = 0; $i < 5; $i++) {
for ($j = 0; $j < 5; $j++) {
print("[");
for ($k = 0; $k < 5; $k++) {
print($positions_taken[$i][$j][$k].", ");
}
print("], ");
}
print("\n");
}
}