[add frontend for cube puzzles
Andreas Röver <roever@users.sourceforge.net>**20050101113923] {
addfile ./src/lib/assm_0_frontend_0.cpp
hunk ./src/lib/assm_0_frontend_0.cpp 1
+/* Burr Solver
+ * Copyright (C) 2003-2005  Andreas Röver
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ */
+
+
+#include "assm_0_frontend_0.h"
+
+/* helper function to check if a piece an go at a position */
+static bool pieceFits(const pieceVoxel_c * piece, const pieceVoxel_c * result, int x, int y, int z) {
+
+  for (int pz = 0; pz < piece->getZ(); pz++)
+    for (int py = 0; py < piece->getY(); py++)
+      for (int px = 0; px < piece->getX(); px++)
+        if ((piece->getState(px, py, pz) != pieceVoxel_c::VX_EMPTY) &&
+            (result->getState(x+px, y+py, z+pz) == pieceVoxel_c::VX_EMPTY))
+          return false;
+
+  return true;
+}
+
+/* add a piece to the cache, but only if it is not already there. If it is added return the
+ * piece pointer otherwise return null
+ */
+static pieceVoxel_c * addToCache(pieceVoxel_c * cache[24], int * fill, pieceVoxel_c * piece) {
+
+  for (int i = 0; i < *fill; i++)
+    if (*cache[i] == *piece) {
+      delete piece;
+      return 0;
+    }
+
+  cache[*fill] = piece;
+  (*fill)++;
+  return piece;
+}
+
+/**
+ * this function counts the number of nodes required to acommodate all pieces
+ * the title line is missing from the returned number
+ */
+unsigned long assm_0_frontend_0_c::countNodes(puzzle_c * puz) {
+
+  unsigned long nodes = 0;
+
+  const pieceVoxel_c * result = puz->getResult();
+
+  /* now we insert one shape after another */
+  for (int pc = 0; pc < puz->getShapeNumber(); pc++) {
+
+    int placements = 0;
+
+    /* this array contains all the pieces found so far, this will help us
+     * to not add two times the same piece to the structur */
+    pieceVoxel_c * cache[24];
+    int cachefill = 0;
+
+    /* go through all possible rotations of the piece */
+    /* didn't find piece, so it's new shape, add to cache and add to
+     * node structure */
+    /* find all possible translations of piece and add them, if they fit */
+    for (int rot = 0; rot < 24; rot++)
+      if (pieceVoxel_c * rotation = addToCache(cache, &cachefill, new pieceVoxel_c(puz->getShape(pc), rot)))
+        for (int x = 0; x < result->getX() - rotation->getX() + 1; x++)
+          for (int y = 0; y < result->getY() - rotation->getY() + 1; y++)
+            for (int z = 0; z < result->getZ() - rotation->getZ() + 1; z++)
+              if (pieceFits(rotation, result, x, y, z))
+                placements++;
+
+    nodes += placements * (puz->getShape(pc)->countState(pieceVoxel_c::VX_FILLED) + 1) * puz->getShapeCount(pc);
+
+    for (int i = 0; i < cachefill; i++) delete cache[i];
+
+    // if one piece has no possible position in the result shape return error
+    if (placements == 0)
+      return -pc;
+  }
+
+  return nodes;
+}
+
+/**
+ * this function prepares the matrix of nodes for the recursive function
+ * I've done some additions to knuths algorithm to implement variable
+ * voxels (empty spaces in the solution) and multiple instances of the
+ * same piece. Empty voxels in the result are done by removing columns
+ * from the matrix. This will prevent the algorithm from filling the
+ * corresponding voxels. But we need to have the constraints that these
+ * columns place on the solution. This is done by adding these columns
+ * to the matrix but behind the normal columns. These additional columns
+ * wont be searched by the alg if it looks for the next task to achive.
+ *
+ * Multiple instances of the same piece is handles in a similar way. To
+ * prevent finding the same solution again and again with just the
+ * pieces swapping places we enumber the pieces and their possible
+ * placements and disallow that the position number of piece n is lower
+ * than the position number of piece n-1. This can be achived by adding
+ * more constraint columns. There need to be one column for each
+ *
+ * negative result show there is something wrong: the place -result has not
+ * possible position inside the result
+ */
+void assm_0_frontend_0_c::prepare(puzzle_c * puz, int res_filled, int res_vari) {
+
+  pieceVoxel_c * result = puz->getResult();
+
+  /* this array contains the column in our matrix that corresponds with
+   * the voxel position inside the result. We use this matrix because
+   * the calculation of the exact column depends on the number of FILLED
+   * and VARIABLE voxels and is relatively expensive to calculate
+   * with this lookup I was able to reduce the preparation time
+   * from 5 to 0.5 seconds for TheLostDay puzzle
+   */
+  unsigned int * columns = new unsigned int[result->getXYZ()];
+  unsigned int piecenumber = puz->getPieces();
+  voxelindex = new int[puz->getResult()->getXYZ() + piecenumber + 1];
+
+  for (int i = 0; i < puz->getResult()->getXYZ() + piecenumber + 1; i++)
+    voxelindex[i] = -1;
+
+  {
+    int v = 0;
+    int c = 0;
+  
+    for (int i = 0; i < result->getXYZ(); i++) {
+      switch(result->getState(i)) {
+      case pieceVoxel_c::VX_VARIABLE:
+        voxelindex[getVarivoxelStart() + v] = i;
+        columns[i] = getVarivoxelStart() + v++;
+        break;
+      case pieceVoxel_c::VX_FILLED:
+        voxelindex[1 + piecenumber + c] = i;
+        columns[i] = 1 + piecenumber + c++;
+        break;
+      default:
+        columns[i] = 0;
+      }
+    }
+  }
+
+  /* find the symmetry breaker */
+  symmetries_t resultSym = result->selfSymmetries();
+  int symBreakerPiece = -1;
+
+  // we only need to do this, if the result shape has some symmetries */
+  if (resultSym != 1) {
+
+    unsigned int bestFound = 25;
+
+    for (int i = 0; i < puz->getShapeNumber(); i++) {
+
+      symmetries_t multSym = resultSym & puz->getShape(i)->selfSymmetries();
+
+      if ((numSymmetries(multSym) < bestFound) ||
+          (numSymmetries(multSym) == bestFound) && (puz->getShapeCount(i) < puz->getShapeCount(symBreakerPiece))) {
+        bestFound = numSymmetries(multSym);
+        symBreakerPiece = i;
+      }
+    }
+
+    symmetries_t tmp = resultSym & puz->getShape(symBreakerPiece)->selfSymmetries() & ~((symmetries_t)1);
+
+    if (tmp || (puz->getShapeCount(symBreakerPiece) > 1))
+      printf("oops I wont be able to avoid all sorts of symmetries (%llx)\n", tmp);
+
+    resultSym = multiplySymmetries(resultSym, puz->getShape(symBreakerPiece)->selfSymmetries());
+  }
+
+  /* node 0 is the start node for everything */
+
+  /* even thou the matrix has a column for each result voxel and each piece we leave out
+   * the VARIABLE voxels in the ring list of the header. This is to avoid selecting these
+   * columns for filling. The columns for the VARIABLE voxels are only there to make sure
+   * these voxels are only used once
+   */
+
+  /* nodes 1..n are the columns nodes */
+  GenerateFirstRow(res_filled);
+
+  int piece = 0;
+
+  /* now we insert one shape after another */
+  for (int pc = 0; pc < puz->getShapeNumber(); pc++)
+    for (int piececount = 0; piececount < puz->getShapeCount(pc); piececount++, piece++) {
+
+      nextPiece(piece, puz->getShapeCount(pc), piececount);
+
+      /* this array contains all the pieces found so far, this will help us
+       * to not add two times the same piece to the structur */
+      pieceVoxel_c * cache[24];
+      int cachefill = 0;
+  
+      /* go through all possible rotations of the piece
+       * if shape is new to cache, add it to the cache and also
+       * add the shape to the matrix, in all positions that it fits
+       */
+      for (int rot = 0; rot < 24; rot++) {
+        bool skipRotation = ((pc == symBreakerPiece) && (piececount == 0) && symmetrieContainsTransformation(resultSym, rot));
+        if (pieceVoxel_c * rotation = addToCache(cache, &cachefill, new pieceVoxel_c(puz->getShape(pc), rot))) {
+          for (int x = 0; x < result->getX() - rotation->getX() + 1; x++)
+            for (int y = 0; y < result->getY() - rotation->getY() + 1; y++)
+              for (int z = 0; z < result->getZ() - rotation->getZ() + 1; z++)
+                if (pieceFits(rotation, result, x, y, z)) {
+
+                  int piecenode;
+
+                  if (!skipRotation)
+                    piecenode = AddPieceNode(piece);
+                  else
+                    AddFillerNode();
+
+                  /* now add the used cubes of the piece */
+                  for (int pz = 0; pz < rotation->getZ(); pz++)
+                    for (int py = 0; py < rotation->getY(); py++)
+                      for (int px = 0; px < rotation->getX(); px++)
+                        if (rotation->getState(px, py, pz) != pieceVoxel_c::VX_EMPTY) {
+  
+                          if (!skipRotation)
+                            AddVoxelNode(columns[result->getIndex(x+px, y+py, z+pz)], piecenode);
+                          else
+                            AddFillerNode();
+                        }
+                }
+        }
+      }
+      for (int i = 0; i < cachefill; i++)  delete cache[i];
+    }
+
+  delete [] columns;
+
+  assm = new assemblyVoxel_c(puz->getResult()->getX(), puz->getResult()->getY(), puz->getResult()->getZ(), assemblyVoxel_c::VX_EMPTY);
+}
+
+assm_0_frontend_0_c::~assm_0_frontend_0_c() {
+  if (voxelindex) delete [] voxelindex;
+  if (assm) delete assm;
+}
+
+bool assm_0_frontend_0_c::solution(void) {
+
+  if (getCallback()) {
+    /* clean voxel space */
+    assm->setAll(assemblyVoxel_c::VX_EMPTY);
+
+    /* put all the pieces at their places
+     * be going through all the selected rows and finding out
+     * where there is a one in that row and then find the corresponding
+     * voxel space index and place the piece number in there
+     */
+    for (int i = 0; i < getPos(); i++) {
+      int r = getRows(i);
+
+      // go over all columns and that columns that
+      // are for result shape will be set inside the result
+      do {
+
+        int vi = voxelindex[getColCount(r)];
+
+        if (vi >= 0)
+          assm->set(vi, getPiece(i) + 1);
+
+        r = getRight(r);
+
+      } while (r != getRows(i));
+    }
+
+    return getCallback()->assembly(assm);
+  }
+
+  return true;
+}
+
addfile ./src/lib/assm_0_frontend_0.h
hunk ./src/lib/assm_0_frontend_0.h 1
+/* Burr Solver
+ * Copyright (C) 2003-2005  Andreas Röver
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ */
+
+
+#ifndef __ASSEMBLER_0_FRONTENT_0_H__
+#define __ASSEMBLER_0_FRONTENT_0_H__
+
+#include "assembler_0.h"
+
+#include "voxel.h"
+#include "puzzle.h"
+
+class assm_0_frontend_0_c : public assembler_0_c {
+
+private:
+
+  /* voxelindex is the invers of the function column. it returns
+   * the index (not x, y, z) of a given column in the matrix
+   */
+  int * voxelindex;
+
+  /* assm is used to contain the assembled puzzle
+   * once an assembly has been found
+   */
+  assemblyVoxel_c * assm;
+
+  /* get's called when a solution is found. this function
+   * then assembles the solution inside assm and calles the
+   * callback function with assm as parameter
+   */
+  bool solution(void);
+
+  /* this function creates the matrix for the search function
+   * because we need to know how many nodes we need to allocate the
+   * arrays with the right size, we add a parameter. if this is true
+   * the function will not access the array but only count the number
+   * of nodes used. this number is returned
+   */
+  unsigned long countNodes(puzzle_c * puz);
+  void prepare(puzzle_c * puz, int res_filles, int res_vari);
+
+public:
+
+  assm_0_frontend_0_c() : assembler_0_c() {}
+  ~assm_0_frontend_0_c();
+};
+
+#endif
}
