00001 /* BurrTools 00002 * 00003 * BurrTools is the legal property of its developers, whose 00004 * names are listed in the COPYRIGHT file, which is included 00005 * within the source distribution. 00006 * 00007 * This program is free software; you can redistribute it and/or 00008 * modify it under the terms of the GNU General Public License 00009 * as published by the Free Software Foundation; either version 2 00010 * of the License, or (at your option) any later version. 00011 00012 * This program is distributed in the hope that it will be useful, 00013 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 * GNU General Public License for more details. 00016 00017 * You should have received a copy of the GNU General Public License 00018 * along with this program; if not, write to the Free Software 00019 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 00020 */ 00021 #ifndef __DL_ASSEMBLER_H__ 00022 #define __DL_ASSEMBLER_H__ 00023 00024 #include "assembler.h" 00025 00026 #include <vector> 00027 #include <set> 00028 #include <stack> 00029 00030 class gridType_c; 00031 class mirrorInfo_c; 00032 00042 class assembler_0_c : public assembler_c { 00043 00044 protected: 00045 00046 const problem_c * puzzle; 00047 00048 private: 00049 00050 /* this are the members of the node. One array for each member. This 00051 * accelerates access. 00052 * 00053 * colCount is a shared member. It is column for normal nodes and count for 00054 * column header nodes 00055 */ 00056 std::vector<unsigned int> left; 00057 std::vector<unsigned int> right; 00058 std::vector<unsigned int> upDown; // this is special, is contains in reality 2 arrays interleaved 00059 // the even entries (0, 2, 4, ...) are up and the odd (1, 3, 5, ...) are down 00060 // I've done this to save a register for the assembly versions of the cover 00061 // and uncover functions and to speed them up by % 00062 std::vector<unsigned int> colCount; 00063 00064 //to make access to the up and down vectors easier, the following 2 macros are provided 00065 #define up(x) upDown[2*(x)] 00066 #define down(x) upDown[2*(x)+1] 00067 00068 /* used to abort the searching */ 00069 bool abbort; 00070 00071 /* used to save if the search is running */ 00072 bool running; 00073 00074 /* cover one column: 00075 * - remove the column from the column header node list, 00076 * - remove all rows where the given column is 1 00077 */ 00078 void cover(unsigned int col); 00079 00080 /* uncover the given column 00081 * this is the exact inverse operation of cover. It requires that the 00082 * matrix has the same state as after the corresponding cover. 00083 * so 00084 * 00085 * cover(i); uncover(i); 00086 * 00087 * will result in the same matrix as before 00088 */ 00089 void uncover(unsigned int col); 00090 00091 /* 2 helper functions that cover and uncover one 00092 * selected row 00093 */ 00094 void cover_row(register unsigned int r); 00095 void uncover_row(register unsigned int r); 00096 00097 /* same as cover row, but aborting 00098 * as soon as one of the columns does contain a zero 00099 * and then uncovering all that was already done 00100 */ 00101 bool try_cover_row(register unsigned int r, unsigned int * columns); 00102 00103 /* these 2 functions remove and reinsert rows from the matrix 00104 * they only remove the given row 00105 */ 00106 void remove_row(register unsigned int r); 00107 void reinsert_row(register unsigned int r); 00108 00109 void remove_column(register unsigned int c); 00110 00111 /* this function gets called whenever an assembly was found 00112 * when a callback is available it will call getAssembly to 00113 * obtain the assembly for the found solution when the 00114 * field avoidTransformedAssemblies is true then the assembly 00115 * is checked, if it has been found before. The assembly 00116 * is normalized in inserted into a set of assemblies for 00117 * later reference 00118 */ 00119 void solution(void); 00120 00121 /* used to collect the data necessary to construct and for the iterative algorithm 00122 * the assembly, it contains the indexes to the selected rows 00123 * the columns array contains the indices of the covered columns 00124 * the pos value contains the number of pieces placed 00125 */ 00126 unsigned int pos; 00127 unsigned int *rows; 00128 unsigned int *columns; 00129 00130 void iterativeMultiSearch(void); 00131 00132 /* this function checks, if the given piece can be placed 00133 * at the given position inside the result 00134 */ 00135 bool canPlace(const voxel_c * piece, int x, int y, int z) const; 00136 00137 /* this function creates the matrix for the search function 00138 * because we need to know how many nodes we need to allocate the 00139 * arrays with the right size, we add a parameter. If this is true 00140 * the function will not access the array but only count the number 00141 * of nodes used. This number is returned 00142 * 00143 * return error codes 00144 */ 00145 int prepare(void); 00146 00147 /* used by reduce to find out if the given position is a dead end 00148 * and will always lead to non solvable positions 00149 */ 00150 bool checkmatrix(void); 00151 00152 /* internal error state */ 00153 errState errorsState; 00154 int errorsParam; 00155 00156 /* number of iterations the assemble routine run */ 00157 unsigned long iterations; 00158 00159 /* the number of holes the assembles piece will have. Holes are 00160 * voxels in the variable voxel set that are not filled. The other 00161 * voxels are all filled 00162 */ 00163 int holes; 00164 00165 /* first and one after last column for the variable voxels */ 00166 unsigned int varivoxelStart; 00167 unsigned int varivoxelEnd; 00168 00169 /* now this isn't hard to guess, is it? */ 00170 unsigned int piecenumber; 00171 00172 /* the message object that gets called with the solutions as param */ 00173 assembler_cb * asm_bc; 00174 00175 /* this value contains the piecenumber that the reduce procedure is currently working on 00176 * the value is only valid, when reduce is running 00177 */ 00178 unsigned int reducePiece; 00179 00180 /* this vector contains the placement (transformation and position) for 00181 * a piece in a row 00182 */ 00183 class piecePosition { 00184 00185 public: 00186 00187 int x, y, z; 00188 unsigned char transformation; 00189 unsigned int row; // first node in this row 00190 unsigned int piece; 00191 00192 piecePosition(int x_, int y_, int z_, unsigned char transformation_, unsigned int row_, unsigned int pc) : x(x_), y(y_), z(z_), 00193 transformation(transformation_), row(row_), piece(pc) {} 00194 }; 00195 std::vector<piecePosition> piecePositions; 00196 00197 /* the members for rotations rejection 00198 */ 00199 bool avoidTransformedAssemblies; 00200 unsigned int avoidTransformedPivot; 00201 mirrorInfo_c * avoidTransformedMirror; 00202 00204 bool complete; 00205 00206 /* the variables for debugging assembling processes 00207 */ 00208 bool debug; // debugging enabled 00209 int debug_loops; // how many loops to run ? 00210 00211 unsigned int clumpify(void); 00212 00213 protected: 00214 00215 /* as this is only a back end doing the processing on the matrix, there needs to 00216 * be a front end creating the matrix and evaluating the results. These functions 00217 * are helpers for the front end 00218 */ 00219 00220 /* this function creates the first row of the matrix. As the createMatrix function 00221 * has already set up some variables you only need to specify the value res_filled that is 00222 * given to you as a parameter to the function prepare. You normally call this function 00223 * in prepare 00224 */ 00225 void GenerateFirstRow(void); 00226 00227 /* this function adds a node to the matrix that belongs to the first columns that represent 00228 * the pieces. This is normally the first thing you do, when you start a new line in the matrix 00229 * The information you provide is required to restore the exact piece in placement that this 00230 * line stands for 00231 * the return value is a number that has to be given to the voxel node creation routine 00232 * it contains the number of the node that is created with this function 00233 */ 00234 int AddPieceNode(unsigned int piece, unsigned int rot, unsigned int x, unsigned int y, unsigned int z); 00235 00236 /* this is in a way the inverse of the function above. You give a node number and get 00237 * the exact piece and placement the line this node belongs to stands for 00238 * this function is used in the solution function to restore the placement of the piece 00239 */ 00240 void getPieceInformation(unsigned int node, unsigned char *tran, int *x, int *y, int *z, unsigned int *pc) const; 00241 00242 /* this adds a normal node that represents a used voxel within the solution 00243 * piecenode is the number that you get from AddPieceNode, col is a number 00244 * that can be calculated from the x, y and z position of the voxel 00245 */ 00246 void AddVoxelNode(unsigned int col, unsigned int piecenode); 00247 00248 /* these functions provide access to the cover information for you */ 00249 unsigned int getRows(int pos) { return rows[pos]; } 00250 unsigned int getRight(int pos) { return right[pos]; } 00251 unsigned int getColCount(int pos) { return colCount[pos]; } 00252 unsigned int getVarivoxelStart(void) { return varivoxelStart; } 00253 unsigned int getPos(void) { return pos; } 00254 00255 /* finally after assembling a puzzle and creating something meaningful from the cover 00256 * information you need to call the callback of the user, use this function to get the 00257 * callback class 00258 */ 00259 assembler_cb * getCallback(void) { return asm_bc; } 00260 00261 unsigned int getPiecenumber(void) { return piecenumber; } 00262 00263 /* call this function if you think that there might be 00264 * rotated assemblies found. Here a description of how the whole aspect of 00265 * rotation avoiding is supposed to work 00266 * the front end is supposed to initialize the assembler so that as few as 00267 * possible double assemblies are found by selecting one piece and not placing 00268 * this piece in all possible positions. But this will not always work, if 00269 * the front end is are not absolutely certain that it has avoided all possible 00270 * rotations it should call this function. This will then add an additional check 00271 * for each found assembly 00272 */ 00273 void checkForTransformedAssemblies(unsigned int pivot, mirrorInfo_c * mir); 00274 00275 public: 00276 00277 assembler_0_c(void); 00278 ~assembler_0_c(void); 00279 00280 /* functions that are overloaded from assembler_c, for comments see there */ 00281 errState createMatrix(const problem_c * puz, bool keepMirror, bool keepRotations, bool complete); 00282 void assemble(assembler_cb * callback); 00283 int getErrorsParam(void) { return errorsParam; } 00284 virtual float getFinished(void) const; 00285 virtual void stop(void) { abbort = true; } 00286 virtual bool stopped(void) const { return !running; } 00287 virtual errState setPosition(const char * string, const char * version); 00288 virtual void save(xmlWriter_c & xml) const; 00289 virtual void reduce(void); 00290 virtual unsigned int getReducePiece(void) const { return reducePiece; } 00291 virtual unsigned long getIterations(void) { return iterations; } 00292 00293 /* some more special information to find out possible piece placements */ 00294 bool getPiecePlacementSupported(void) const { return true; } 00295 unsigned int getPiecePlacement(unsigned int node, int delta, unsigned int piece, unsigned char *tran, int *x, int *y, int *z) const; 00296 unsigned int getPiecePlacementCount(unsigned int piece) const; 00297 00298 void debug_step(unsigned long num = 1); 00299 assembly_c * getAssembly(void); 00300 00301 static bool canHandle(const problem_c * p); 00302 00303 private: 00304 00305 // no copying and assigning 00306 assembler_0_c(const assembler_0_c&); 00307 void operator=(const assembler_0_c&); 00308 }; 00309 00310 #endif
1.5.8