1 
  2 #include <boost/assign/std/vector.hpp>
  3 #include <iostream>
  4 #include <iterator>
  5 #include <iomanip>
  6 #include <algorithm>
  7 
  8 #include "SnakeCube.h"
  9 
 10 
 11 SnakeCubeTracker::SnakeCubeTracker(const SnakeCubeConstraint_t& constraint, SnakeCubeSolutionCallback_t callback)
 12     : constraint_(constraint)
 13     , snakeAlignment_(SnakeCubeConstraint_t(0))
 14     , partialSolution_( SnakeCubeSolution_t(boost::extents[3][3][3]) )
 15     , callback_(callback)
 16 {}
 17 
 18 SnakeCubeTracker::SnakeCubeTracker(SnakeCubeSolutionCallback_t callback)
 19     : constraint_(SnakeCubeConstraint_t(0))
 20     , snakeAlignment_(SnakeCubeConstraint_t(0))
 21     , partialSolution_( SnakeCubeSolution_t(boost::extents[3][3][3]) )
 22     , callback_(callback)
 23 {}
 24 
 25 void SnakeCubeTracker::tryAllStartingPositions()
 26 {
 27     for(int i = 0; i < 2; ++i)
 28         for(int j = 0; j < 2; ++j)
 29             for(int k = 0; k < 2; ++k)
 30                 startSearchFromLocation(i,j,k);
 31 }
 32 
 33 void SnakeCubeTracker::startSearchFromLocation(int x, int y, int z)
 34 {
 35     using namespace boost::assign;
 36 
 37     directions_.clear();
 38 
 39     partialSolution_[x][y][z] = 1;
 40 
 41     SnakeCubePosition_t position;
 42     position += x,y,z;
 43     firstPosition_ = position;
 44     moveOneStepForwardWithSolution(0, position, 1, 1);
 45 
 46     partialSolution_[x][y][z] = 0;
 47 }
 48 
 49 void SnakeCubeTracker::examinePartialSolution(unsigned int n, const SnakeCubePosition_t& position, int direction, int usedDims)
 50 {
 51     partialSolution_[position[0]][position[1]][position[2]] = n + 1;
 52     directions_.push_back(direction);
 53 
 54     if( isSolutionComplete(n) )
 55     {
 56         if( isForOutput(position) )
 57             callback_(partialSolution_, snakeAlignment_);
 58     }
 59     else
 60     {
 61         if( constraint_.size() < n || constraint_[n - 1] == 0 )
 62         {
 63             snakeAlignment_.push_back(0);
 64             moveOneStepForwardWithSolution(n, position, direction, usedDims);
 65             snakeAlignment_.pop_back();
 66         }
 67         if( constraint_.size() < n || constraint_[n - 1] == 1 )
 68         {
 69             snakeAlignment_.push_back(1);
 70             turn(n, position, direction, usedDims);
 71             snakeAlignment_.pop_back();
 72         }
 73     }
 74 
 75     directions_.pop_back();
 76     partialSolution_[position[0]][position[1]][position[2]] = 0;
 77 }
 78 
 79 bool SnakeCubeTracker::isSolutionComplete(int solutionLength) const
 80 {
 81     return solutionLength == 26;
 82 }
 83 
 84 void SnakeCubeTracker::moveOneStepForwardWithSolution(unsigned int n, SnakeCubePosition_t position, int direction, int usedDims)
 85 {
 86     int sign = (direction < 0) ? -1 : 1;
 87     position[abs(direction)-1] += sign;
 88     if(isLegalMove(position))
 89     {
 90         examinePartialSolution(n+1, position, direction, usedDims);
 91     }
 92 }
 93 
 94 void SnakeCubeTracker::turn(unsigned int n, const SnakeCubePosition_t& position, int direction, int usedDims)
 95 {
 96     for(int i = 1; i <= std::min(usedDims,3); ++i)
 97     {
 98         if( i != abs(direction) )
 99         {
100             moveOneStepForwardWithSolution(n, position, i, usedDims);
101             moveOneStepForwardWithSolution(n, position, -i, usedDims);
102         }
103     }
104     if(usedDims < 3)
105     {
106         moveOneStepForwardWithSolution(n, position, usedDims + 1, usedDims + 1);
107     }
108 }
109 
110 bool SnakeCubeTracker::isLegalMove(const SnakeCubePosition_t& position) const
111 {
112     return fallsWithinCube(position) && !isPositionOccupied(position);
113 }
114 
115 bool SnakeCubeTracker::isPositionOccupied(const SnakeCubePosition_t& position) const
116 {
117     return partialSolution_[position[0]][position[1]][position[2]] > 0;
118 }
119 
120 bool SnakeCubeTracker::fallsWithinCube(const SnakeCubePosition_t& position) const
121 {
122     return !(position[0] < 0 || position[0] > 2 ||
123              position[1] < 0 || position[1] > 2 ||
124              position[2] < 0 || position[2] > 2 );
125 }
126 
127 bool SnakeCubeTracker::isForOutput(SnakeCubePosition_t position) const
128 {
129     return !isSnakePalindromic() || !isLexicographicallyLargerThenReversed();
130 }
131 
132 bool SnakeCubeTracker::isSnakePalindromic() const
133 {
134     for(unsigned int i = 0; 2*i < snakeAlignment_.size(); ++i)
135     {
136         if(snakeAlignment_[i] != snakeAlignment_[snakeAlignment_.size() - i - 1]) return false;
137     }
138     return true;
139 }
140 
141 bool SnakeCubeTracker::isLexicographicallyLargerThenReversed() const
142 {
143     return directions_ > generateReverseDirections();
144 }
145 
146 std::vector<int> SnakeCubeTracker::generateReverseDirections() const
147 {
148     std::map<int,int> dirMap = findReverseDirectionMappingForStandardOrientation();
149     std::vector<int> reverseDirections;
150     for(unsigned int i = 0; i < directions_.size(); ++i)
151     {
152         reverseDirections.push_back(dirMap[directions_[directions_.size() - i - 1]]);
153     }
154     return reverseDirections;
155 }
156 
157 std::map<int,int> SnakeCubeTracker::findReverseDirectionMappingForStandardOrientation() const
158 {
159     std::map<int,int> dirMap;
160     std::vector<int> usedCoordinate(3, 0);
161     int i = directions_.size()-1;
162     int j = 0;
163     while(j < 3)
164     {
165         int dir = abs(directions_[i]) - 1;
166         if(usedCoordinate[dir] == 0)
167         {
168             ++j;
169             dirMap[directions_[i]]      = j;
170             dirMap[directions_[i] * -1] = j * -1;
171             usedCoordinate[dir] = 1;
172         }
173         --i;
174     }
175     return dirMap;
176 }
177 
178 void solveSnakeCube(const SnakeCubePosition_t& constraint, SnakeCubeSolutionCallback_t callback)
179 {
180     SnakeCubeTracker tracker(constraint, callback);
181     tracker.tryAllStartingPositions();
182 }
183 
184 void solveSnakeCube(SnakeCubeSolutionCallback_t callback)
185 {
186     SnakeCubeTracker tracker(callback);
187     tracker.tryAllStartingPositions();
188 }
189 
190 void displaySolution(std::ostream& out, SnakeCubeSolution_t solution)
191 {
192     out << std::endl;
193     for(SnakeCubeSolution_t::index i = 0; i < 3; ++i)
194     {
195         for(SnakeCubeSolution_t::index j = 0; j < 3; ++j)
196         {
197             for(SnakeCubeSolution_t::index k = 0; k < 3; ++k)
198             {
199                 out << std::setw(2) << std::setfill('0') << std::right;
200                 out << solution[i][j][k] << " ";
201             }
202             out << "   ";
203         }
204         out << std::endl;
205     }
206 }