pentominoes.cpp

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 *
 *  Contributing authors:
 *     Guido Tack <tack@gecode.org>
 *
 *  Copyright:
 *     Mikael Lagerkvist, 2006
 *     Guido Tack, 2006
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */

#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/minimodel.hh>

using namespace Gecode;

class TileSpec {
public:
  int width;  
  int height; 
  int amount; 
  const char *tile; 
};

extern const TileSpec *examples[];
extern const int examples_size[];
extern const unsigned int n_examples;

namespace {
  int pos(int h, int w, int h1, int w1);
  typedef void (*tsymmfunc)(const char*, int, int, char*, int&, int&);
  typedef void (*bsymmfunc)(const IntVarArgs, int, int, IntVarArgs&, int&, int&);
  template<class CArray, class Array>
  void id(CArray t1, int w1, int h1, Array t2, int& w2, int&h2);
  template<class CArray, class Array>
  void rot90(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
  template<class CArray, class Array>
  void rot180(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
  template<class CArray, class Array>
  void rot270(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
  template<class CArray, class Array>
  void flipx(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
  template<class CArray, class Array>
  void flipy(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
  template<class CArray, class Array>
  void flipd1(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
  template<class CArray, class Array>
  void flipd2(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
}

class Pentominoes : public Script {
public:
  enum {
    PROPAGATION_INT,       
    PROPAGATION_BOOLEAN,   
  };
  enum {
    SYMMETRY_NONE, 
    SYMMETRY_FULL, 
  };
private:
  const TileSpec *spec;
  int width, height;
  bool filled;
  int nspecs;
  int ntiles;

  IntVarArray board;

  int compute_number_of_tiles(const TileSpec* ts, int nspecs) {
    int res = 0;
    for (int i = nspecs; i--; ) {
      res += ts[i].amount;
    }
    return res;
  }

  REG tile_reg(int twidth, int theight, const char* tile,
               REG mark, REG other, REG eol) {
    REG oe = other | eol;
    REG res = *oe;
    REG color[] = {other, mark};
    for (int h = 0; h < theight; ++h) {
      for (int w = 0; w < twidth; ++w) {
        int which = tile[h*twidth + w] == 'X';
        res += color[which];
      }
      if (h < theight-1) {
        res += oe(width-twidth, width-twidth);
      }
    }
    res += *oe + oe;
    return res;
  }

  REG get_constraint(int t, REG mark, REG other, REG eol) {
    // This should be done for all rotations
    REG res;
    char *t2 = new char[width*height];
    int w2, h2;
    tsymmfunc syms[] = {id, flipx, flipy, flipd1, flipd2, rot90, rot180, rot270};
    int symscnt = sizeof(syms)/sizeof(tsymmfunc);
    for (int i = 0; i < symscnt; ++i) {
      syms[i](spec[t].tile, spec[t].width, spec[t].height, t2, w2, h2);
      res = res | tile_reg(w2, h2, t2, mark, other, eol);
    }
    delete [] t2;

    return res;
  }


public:
  Pentominoes(const SizeOptions& opt)
    : Script(opt), spec(examples[opt.size()]),
      width(spec[0].width+1), // Add one for extra row at end.
      height(spec[0].height),
      filled(spec[0].amount),
      nspecs(examples_size[opt.size()]-1),
      ntiles(compute_number_of_tiles(spec+1, nspecs)),
      board(*this, width*height, filled,ntiles+1) {
    spec += 1; // No need for the specification-part any longer

    // Set end-of-line markers
    for (int h = 0; h < height; ++h) {
      for (int w = 0; w < width-1; ++w)
        rel(*this, board[h*width + w], IRT_NQ, ntiles+1);
      rel(*this, board[h*width + width - 1], IRT_EQ, ntiles+1);
    }

    // Post constraints
    if (opt.propagation() == PROPAGATION_INT) {
      int tile = 0;
      for (int i = 0; i < nspecs; ++i) {
        for (int j = 0; j < spec[i].amount; ++j) {
          // Color
          int col = tile+1;
          // Expression for color col
          REG mark(col);
          // Build expression for complement to color col
          REG other;
          bool first = true;
          for (int j = filled; j <= ntiles; ++j) {
            if (j == col) continue;
            if (first) {
              other = REG(j);
              first = false;
            } else {
              other |= REG(j);
            }
          }
          // End of line marker
          REG eol(ntiles+1);
          extensional(*this, board, get_constraint(i, mark, other, eol));
          ++tile;
        }
      }
    } else { // opt.propagation() == PROPAGATION_BOOLEAN
      int ncolors = ntiles + 2;
      // Boolean variables for channeling
      BoolVarArgs p(*this,ncolors * board.size(),0,1);

      // Post channel constraints
      for (int i=board.size(); i--; ) {
        BoolVarArgs c(ncolors);
        for (int j=ncolors; j--; )
          c[j]=p[i*ncolors+j];
        channel(*this, c, board[i]);
      }

      // For placing tile i, we construct the expression over
      // 0/1-variables and apply it to the projection of
      // the board on the color for the tile.
      REG other(0), mark(1);
      int tile = 0;
      for (int i = 0; i < nspecs; ++i) {
        for (int j = 0; j < spec[i].amount; ++j) {
          int col = tile+1;
          // Projection for color col
          BoolVarArgs c(board.size());

          for (int k = board.size(); k--; ) {
            c[k] = p[k*ncolors+col];
          }

          extensional(*this, c, get_constraint(i, mark, other, other));
          ++tile;
        }
      }
    }

    if (opt.symmetry() == SYMMETRY_FULL) {
      // Remove symmetrical boards
      IntVarArgs orig(board.size()-height), symm(board.size()-height);
      int pos = 0;
      for (int i = 0; i < board.size(); ++i) {
        if ((i+1)%width==0) continue;
        orig[pos++] = board[i];
      }

      int w2, h2;
      bsymmfunc syms[] = {flipx, flipy, flipd1, flipd2, rot90, rot180, rot270};
      int symscnt = sizeof(syms)/sizeof(bsymmfunc);
      for (int i = 0; i < symscnt; ++i) {
        syms[i](orig, width-1, height, symm, w2, h2);
        if (width-1 == w2 && height == h2)
          rel(*this, orig, IRT_LQ, symm);
      }
    }

    // Install branching
    branch(*this, board, INT_VAR_NONE(), INT_VAL_MIN());
  }

  Pentominoes(Pentominoes& s) :
    Script(s), spec(s.spec), width(s.width), height(s.height),
    filled(s.filled), nspecs(s.nspecs) {
    board.update(*this, s.board);
  }

  virtual Space*
  copy(void) {
    return new Pentominoes(*this);
  }

  virtual void
  print(std::ostream& os) const {
    for (int h = 0; h < height; ++h) {
      os << "\t";
      for (int w = 0; w < width-1; ++w) {
        int val =  board[h*width + w].val();
        char c = val < 10 ? '0'+val : 'A' + (val-10);
        os << c;
      }
      os << std::endl;
    }
    os << std::endl;
  }
};


int
main(int argc, char* argv[]) {
  SizeOptions opt("Pentominoes");
  opt.size(1);
  opt.symmetry(Pentominoes::SYMMETRY_FULL);
  opt.symmetry(Pentominoes::SYMMETRY_NONE,
            "none", "do not remove symmetric solutions");
  opt.symmetry(Pentominoes::SYMMETRY_FULL,
            "full", "remove symmetric solutions");

  opt.propagation(Pentominoes::PROPAGATION_BOOLEAN);
  opt.propagation(Pentominoes::PROPAGATION_INT,
                  "int", "use integer propagators");
  opt.propagation(Pentominoes::PROPAGATION_BOOLEAN,
                  "bool", "use Boolean propagators");

  opt.parse(argc,argv);
  if (opt.size() >= n_examples) {
    std::cerr << "Error: size must be between 0 and "
              << n_examples-1 << std::endl;
    return 1;
  }
  Script::run<Pentominoes,DFS,SizeOptions>(opt);
  return 0;
}



static const TileSpec puzzle0[] =
  {
    // Width and height of board
    {4, 4, true, ""},
    {2, 3, 1,
     "XX"
     "X "
     "X "},
    {2, 1, 1,
     "XX"},
    {3, 3, 1,
     " XX"
     "  X"
     "XXX"},
    {1, 1, 1,
     "X"},
    {3, 1, 1,
     "XXX"}
  };
static const TileSpec puzzle1[] =
  {
    // Width and height of board
    {8, 8, true, ""},
    {3, 3, 1,
     "XXX"
     "XXX"
     "XX "},
    {5, 3, 1,
     "  XXX"
     "  X  "
     "XXX  "},
    {3, 4, 1,
     "XXX"
     "XXX"
     "  X"
     "  X"},
    {3, 4, 1,
     "XXX"
     "  X"
     "  X"
     "  X"},
    {2, 5, 1,
     " X"
     " X"
     " X"
     "XX"
     "XX"},
    {4, 2, 1,
     "XX  "
     "XXXX"},
    {3, 3, 1,
     "XXX"
     "  X"
     "  X"},
    {2, 3, 1,
     "XX"
     "X "
     "X "},
    {2, 4, 1,
     "XX"
     "XX"
     "XX"
     "XX"},
    {3, 2, 1,
     "XX "
     "XXX"}
  };

// Perfect square number 2 from examples/perfect-square.cc
static const TileSpec square2[] =
  {
    // Width and height of board
    {10, 10, true, ""},
    {6, 6, 1,
     "XXXXXX"
     "XXXXXX"
     "XXXXXX"
     "XXXXXX"
     "XXXXXX"
     "XXXXXX"
    },
    {4, 4, 3,
     "XXXX"
     "XXXX"
     "XXXX"
     "XXXX"},
    {2, 2, 4,
     "XX"
     "XX"}
  };

// Perfect square number 3 from examples/perfect-square.cc
static const TileSpec square3[] =
  {
    // Width and height of board
    {20, 20, true, ""},
    {9, 9, 1,
     "XXXXXXXXX"
     "XXXXXXXXX"
     "XXXXXXXXX"
     "XXXXXXXXX"
     "XXXXXXXXX"
     "XXXXXXXXX"
     "XXXXXXXXX"
     "XXXXXXXXX"
     "XXXXXXXXX"
    },
    {8, 8, 2,
     "XXXXXXXX"
     "XXXXXXXX"
     "XXXXXXXX"
     "XXXXXXXX"
     "XXXXXXXX"
     "XXXXXXXX"
     "XXXXXXXX"
     "XXXXXXXX"
    },
    {7, 7, 1,
     "XXXXXXX"
     "XXXXXXX"
     "XXXXXXX"
     "XXXXXXX"
     "XXXXXXX"
     "XXXXXXX"
     "XXXXXXX"
    },
    {5, 5, 1,
     "XXXXX"
     "XXXXX"
     "XXXXX"
     "XXXXX"
     "XXXXX"
    },
    {4, 4, 5,
     "XXXX"
     "XXXX"
     "XXXX"
     "XXXX"},
    {3, 3, 3,
     "XXX"
     "XXX"
     "XXX"},
    {2, 2, 2,
     "XX"
     "XX"},
    {1, 1, 2,
     "X"}
  };

static const TileSpec pentomino6x10[] =
  {
    // Width and height of board
    {10, 6, true, ""},
    {2, 4, 1,
     "X "
     "X "
     "X "
     "XX"},
    {3,3, 1,
     "XX "
     " XX"
     " X "},
    {3,3, 1,
     "XXX"
     " X "
     " X "},
    {3,3, 1,
     "  X"
     " XX"
     "XX "},
    {2,4, 1,
     " X"
     "XX"
     " X"
     " X"},
    {5,1, 1,
     "XXXXX"},
    {3,3, 1,
     "X  "
     "XXX"
     "  X"},
    {4,2, 1,
     " XXX"
     "XX  "},
    {2,3, 1,
     "XX"
     "XX"
     " X"},
    {3,2, 1,
     "X X"
     "XXX"},
    {3,3, 1,
     " X "
     "XXX"
     " X "},
    {3,3, 1,
     "  X"
     "  X"
     "XXX"}
  };

static const TileSpec pentomino5x12[] =
  {
    // Width and height of board
    {12, 5, true, ""},
    {2, 4, 1,
     "X "
     "X "
     "X "
     "XX"},
    {3,3, 1,
     "XX "
     " XX"
     " X "},
    {3,3, 1,
     "XXX"
     " X "
     " X "},
    {3,3, 1,
     "  X"
     " XX"
     "XX "},
    {2,4, 1,
     " X"
     "XX"
     " X"
     " X"},
    {5,1, 1,
     "XXXXX"},
    {3,3, 1,
     "X  "
     "XXX"
     "  X"},
    {4,2, 1,
     " XXX"
     "XX  "},
    {2,3, 1,
     "XX"
     "XX"
     " X"},
    {3,2, 1,
     "X X"
     "XXX"},
    {3,3, 1,
     " X "
     "XXX"
     " X "},
    {3,3, 1,
     "  X"
     "  X"
     "XXX"}
  };

static const TileSpec pentomino4x15[] =
  {
    // Width and height of board
    {15, 4, true, ""},
    {2, 4, 1,
     "X "
     "X "
     "X "
     "XX"},
    {3,3, 1,
     "XX "
     " XX"
     " X "},
    {3,3, 1,
     "XXX"
     " X "
     " X "},
    {3,3, 1,
     "  X"
     " XX"
     "XX "},
    {2,4, 1,
     " X"
     "XX"
     " X"
     " X"},
    {5,1, 1,
     "XXXXX"},
    {3,3, 1,
     "X  "
     "XXX"
     "  X"},
    {4,2, 1,
     " XXX"
     "XX  "},
    {2,3, 1,
     "XX"
     "XX"
     " X"},
    {3,2, 1,
     "X X"
     "XXX"},
    {3,3, 1,
     " X "
     "XXX"
     " X "},
    {3,3, 1,
     "  X"
     "  X"
     "XXX"}
  };

static const TileSpec pentomino3x20[] =
  {
    // Width and height of board
    {20, 3, true, ""},
    {2, 4, 1,
     "X "
     "X "
     "X "
     "XX"},
    {3,3, 1,
     "XX "
     " XX"
     " X "},
    {3,3, 1,
     "XXX"
     " X "
     " X "},
    {3,3, 1,
     "  X"
     " XX"
     "XX "},
    {2,4, 1,
     " X"
     "XX"
     " X"
     " X"},
    {5,1, 1,
     "XXXXX"},
    {3,3, 1,
     "X  "
     "XXX"
     "  X"},
    {4,2, 1,
     " XXX"
     "XX  "},
    {2,3, 1,
     "XX"
     "XX"
     " X"},
    {3,2, 1,
     "X X"
     "XXX"},
    {3,3, 1,
     " X "
     "XXX"
     " X "},
    {3,3, 1,
     "  X"
     "  X"
     "XXX"}
  };

const TileSpec *examples[] = {puzzle0, puzzle1, square2, square3,
                           pentomino6x10,pentomino5x12,
                           pentomino4x15,pentomino3x20};
const int examples_size[] = {sizeof(puzzle0)/sizeof(TileSpec),
                             sizeof(puzzle1)/sizeof(TileSpec),
                             sizeof(square2)/sizeof(TileSpec),
                             sizeof(square3)/sizeof(TileSpec),
                             sizeof(pentomino6x10)/sizeof(TileSpec),
                             sizeof(pentomino5x12)/sizeof(TileSpec),
                             sizeof(pentomino4x15)/sizeof(TileSpec),
                             sizeof(pentomino3x20)/sizeof(TileSpec)};

const unsigned n_examples = sizeof(examples)/sizeof(TileSpec*);

// Symmetry functions
namespace {
  int pos(int h, int w, int h1, int w1) {
    if (!(0 <= h && h < h1) ||
        !(0 <= w && w < w1)) {
      std::cerr << "Cannot place (" << h << "," << w
                << ") on board of size " << h1 << "x" << w1 << std::endl;
    }
    return h * w1 + w;
  }
  template<class CArray, class Array>
  void id(CArray t1, int w1, int h1, Array t2, int& w2, int&h2) {
    w2 = w1; h2 = h1;
    for (int h = 0; h < h1; ++h)
      for (int w = 0; w < w1; ++w)
        t2[pos(h, w, h2, w2)] = t1[pos(h, w, h1, w1)];
  }
  template<class CArray, class Array>
  void rot90(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
    w2 = h1; h2 = w1;
    for (int h = 0; h < h1; ++h)
      for (int w = 0; w < w1; ++w)
        t2[pos(w, w2-h-1, h2, w2)] = t1[pos(h, w, h1, w1)];
  }
  template<class CArray, class Array>
  void rot180(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
    w2 = w1; h2 = h1;
    for (int h = 0; h < h1; ++h)
      for (int w = 0; w < w1; ++w)
        t2[pos(h2-h-1, w2-w-1, h2, w2)] = t1[pos(h, w, h1, w1)];
  }
  template<class CArray, class Array>
  void rot270(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
    w2 = h1; h2 = w1;
    for (int h = 0; h < h1; ++h)
      for (int w = 0; w < w1; ++w)
        t2[pos(h2-w-1, h, h2, w2)] = t1[pos(h, w, h1, w1)];
  }
  template<class CArray, class Array>
  void flipx(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
    w2 = w1; h2 = h1;
    for (int h = 0; h < h1; ++h)
      for (int w = 0; w < w1; ++w)
        t2[pos(h, w2-w-1, h2, w2)] = t1[pos(h, w, h1, w1)];
  }
  template<class CArray, class Array>
  void flipy(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
    w2 = w1; h2 = h1;
    for (int h = 0; h < h1; ++h)
      for (int w = 0; w < w1; ++w)
        t2[pos(h2-h-1, w, h2, w2)] = t1[pos(h, w, h1, w1)];
  }
  template<class CArray, class Array>
  void flipd1(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
    w2 = h1; h2 = w1;
    for (int h = 0; h < h1; ++h)
      for (int w = 0; w < w1; ++w)
        t2[pos(w, h, h2, w2)] = t1[pos(h, w, h1, w1)];
  }
  template<class CArray, class Array>
  void flipd2(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
    w2 = h1; h2 = w1;
    for (int h = 0; h < h1; ++h)
      for (int w = 0; w < w1; ++w)
        t2[pos(h2-w-1, w2-h-1, h2, w2)] = t1[pos(h, w, h1, w1)];
  }
}

// STATISTICS: example-any