main page modules namespaces classes files
Gecode home

search for 

picture-puzzle.cc

Go to the documentation of this file.

/*
 *  Main authors:
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 *
 *  Copyright:
 *     Mikael Lagerkvist, 2005
 *
 *  Last modified:
 *     $Date: 2006-08-04 16:06:52 +0200 (Fri, 04 Aug 2006) $ by $Author: schulte $
 *     $Revision: 3517 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  See the file "LICENSE" for information on usage and
 *  redistribution of this file, and for a
 *     DISCLAIMER OF ALL WARRANTIES.
 *
 */

#include "examples/support.hh"
#include "gecode/minimodel.hh"

extern const int *specs[];
extern const unsigned int n_examples;

class PicturePuzzle : public Example {
private:
  const int *spec;
  int width, height;
  BoolVarArray b;

  BoolVar pos(int h, int w) {
    return b[h*width + w];
  }

  REG get_constraint(int& spos) {
    // Useful to check that a new specification was entered correctly.
    const bool print_spec = false;
    REG r = *REG(0);
    int size = spec[spos++];
    if (print_spec) std::cout << size << "(" << spos << "): ";
    for (int i = 0; i < size; ++i, ++spos) {
      if (i) r = r + +REG(0);
      if (print_spec) std::cout << spec[spos] << " ";
      r = r + REG(1)(spec[spos],spec[spos]);
    }
    if (print_spec) std::cout << std::endl;
    r = r + *REG(0);

    return r;
  }


public:
  PicturePuzzle(const Options& o)
    : spec(specs[o.size]), width(spec[0]), height(spec[1]),
      b(this,width*height,0,1) {
    int spos = 2;
    MiniModel::Matrix<BoolVarArray> m(b, width, height);

    // Post constraints for columns
    for (int w = 0; w < width; ++w) {
      // Post constraint
      REG r = get_constraint(spos);
      DFA d = r;
      regular(this, m.col(w), d);
    }

    // Post constraints for rows
    for (int h = 0; h < height; ++h) {
      // Post constraint
      REG r = get_constraint(spos);
      DFA d = r;
      regular(this, m.row(h), d);
    }

    // Install branchings
    branch(this, b, BVAR_NONE, BVAL_MAX);
  }

  PicturePuzzle(bool share, PicturePuzzle& s) :
    Example(share,s), spec(s.spec), width(s.width), height(s.height) {
    b.update(this, share, s.b);
  }

  virtual Space*
  copy(bool share) {
    return new PicturePuzzle(share,*this);
  }

  virtual void
  print(void) {
    for (int h = 0; h < height; ++h) {
      std::cout << '\t';
      for (int w = 0; w < width; ++w) {
        if (pos(h,w).val() == 1) {
          std::cout << "#";
        } else {
          std::cout << " ";
        }
      }
      std::cout << std::endl;
    }
    std::cout << std::endl;
  }
};


int
main(int argc, char** argv) {
  Options o("PicturePuzzle");
  o.size  = 8;
  o.parse(argc,argv);
  if (o.size >= n_examples) {
    std::cerr << "Error: size must be between 0 and "
              << n_examples-1 << std::endl;
    return 1;
  }
  Example::run<PicturePuzzle,DFS>(o);
  return 0;
}



static const int heart[] =
  { 9, 9,
    // Column constraints.
    1, 3,
    2, 2, 3,
    2, 2, 2,
    2, 2, 2,
    2, 2, 2,
    2, 2, 2,
    2, 2, 2,
    2, 2, 3,
    1, 3,
    // Row constraints
    2, 2, 2,
    2, 4, 4,
    3, 1, 3, 1,
    3, 2, 1, 2,
    2, 1, 1,
    2, 2, 2,
    2, 2, 2,
    1, 3,
    1, 1
  };

static const int bear[] =
  { 13, 8,
    // Column constraints
    1, 2,
    2, 2, 1,
    2, 3, 2,
    1, 6,
    2, 1, 4,
    1, 3,
    1, 4,
    1, 4,
    1, 4,
    1, 5,
    1, 4,
    2, 1, 3,
    1, 2,
    // Row constraints
    1, 1,
    1, 2,
    2, 4, 4,
    1, 12,
    1, 8,
    1, 9,
    2, 3, 4,
    2, 2, 2
  };

static const int crocodile[] =
  { 15, 9,
    // Column constraints
    1, 3,
    1, 4,
    2, 2, 2,
    2, 3, 1,
    2, 2, 3,
    2, 3, 2,
    2, 2, 3,
    2, 4, 2,
    2, 3, 2,
    1, 6,
    2, 1, 3,
    2, 1, 3,
    2, 1, 4,
    1, 5,
    1, 5,
    // Row constraints
    1, 3,
    3, 2, 3, 2,
    2, 10, 3,
    1, 15,
    5, 1, 1, 1, 1, 6,
    2, 1, 7,
    2, 1, 4,
    2, 1, 4,
    1, 4
  };

static const int unknown[] =
  { 10, 10,
    // Column constraints
    1, 3,
    2, 2, 1,
    2, 2, 2,
    2, 2, 1,
    3, 1, 2, 1,
    2, 1, 1,
    3, 1, 4, 1,
    3, 1, 1, 2,
    2, 3, 1,
    1, 4,
    // Row constraints
    1, 3,
    2, 2, 1,
    2, 1, 1,
    2, 1, 4,
    4, 1, 1, 1, 1,
    4, 2, 1, 1, 1,
    3, 2, 1, 1,
    2, 1, 2,
    2, 2, 3,
    1, 3
  };

static const int pinwheel[] =
  { 6, 6,
    // Column constraints
    2, 1, 2,
    1, 1,
    1, 2,
    1, 2,
    1, 1,
    2, 2, 1,
    // Row constraints
    2, 2, 1,
    1, 1,
    1, 2,
    1, 2,
    1, 1,
    2, 1, 2
  };

static const int difficult[] =
  { 15, 15,
    // Column constraints
    1, 3,
    1, 2,
    1, 2,
    1, 1,
    1, 2,
    1, 3,
    1, 2,
    1, 4,
    1, 3,
    1, 4,
    2, 2, 1,
    2, 1, 1,
    2, 1, 1,
    2, 1, 1,
    1, 3,
    // Row constraints
    1, 3,
    2, 1, 1,
    2, 1, 1,
    2, 1, 1,
    2, 1, 2,
    1, 5,
    1, 1,
    1, 2,
    1, 1,
    1, 1,
    2, 1, 2,
    2, 1, 2,
    2, 2, 1,
    2, 2, 2,
    1, 3
  };

static const int non_unique[] =
  { 11, 15,
    // Column constraints
    1, 5,
    3, 1, 2, 4,
    3, 2, 1, 3,
    4, 2, 2, 1, 1,
    4, 1, 1, 1, 1,
    2, 1, 5,
    5, 2, 1, 1, 3, 2,
    5, 2, 1, 1, 1, 1,
    3, 1, 4, 1,
    2, 1, 1,
    1, 1,
    // Row constraints
    2, 2, 2,
    2, 2, 2,
    1, 4,
    2, 1, 1,
    2, 1, 1,
    4, 1, 1, 1, 1,
    2, 1, 1,
    2, 1, 4,
    3, 1, 1, 1,
    3, 1, 1, 4,
    2, 1, 3,
    2, 1, 2,
    1, 5,
    2, 2, 2,
    2, 3, 3
  };

static const int dragonfly[] =
  { 20, 20,
    // Column constraints.
    4, 1, 1, 1, 2,
    5, 3, 1, 2, 1, 1,
    5, 1, 4, 2, 1, 1,
    4, 1, 3, 2, 4,
    4, 1, 4, 6, 1,
    3, 1, 11, 1,
    4, 5, 1, 6, 2,
    1, 14,
    2, 7, 2,
    2, 7, 2,
    3, 6, 1, 1,
    2, 9, 2,
    4, 3, 1, 1, 1,
    3, 3, 1, 3,
    3, 2, 1, 3,
    3, 2, 1, 5,
    3, 3, 2, 2,
    3, 3, 3, 2,
    3, 2, 3, 2,
    2, 2, 6,
    // Row constraints
    2, 7, 1,
    3, 1, 1, 2,
    3, 2, 1, 2,
    3, 1, 2, 2,
    3, 4, 2, 3,
    3, 3, 1, 4,
    3, 3, 1, 3,
    3, 2, 1, 4,
    2, 2, 9,
    3, 2, 1, 5,
    2, 2, 7,
    1, 14,
    2, 8, 2,
    3, 6, 2, 2,
    4, 2, 8, 1, 3,
    4, 1, 5, 5, 2,
    5, 1, 3, 2, 4, 1,
    5, 3, 1, 2, 4, 1,
    5, 1, 1, 3, 1, 3,
    4, 2, 1, 1, 2
  };

static const int p200[] =
  { 25, 25,
    // Column constraints
    4, 1,1,2,2,
    3, 5,5,7,
    4, 5,2,2,9,
    4, 3,2,3,9,
    5, 1,1,3,2,7,
    3, 3,1,5,
    5, 7,1,1,1,3,
    6, 1,2,1,1,2,1,
    3, 4,2,4,
    4, 1,2,2,2,
    3, 4,6,2,
    4, 1,2,2,1,
    4, 3,3,2,1,
    3, 4,1,15,
    6, 1,1,1,3,1,1,
    6, 2,1,1,2,2,3,
    4, 1,4,4,1,
    4, 1,4,3,2,
    4, 1,1,2,2,
    5, 7,2,3,1,1,
    5, 2,1,1,1,5,
    3, 1,2,5,
    4, 1,1,1,3,
    3, 4,2,1,
    1, 3,
    // Row constraints
    3, 2,2,3,
    5, 4,1,1,1,4,
    5, 4,1,2,1,1,
    7, 4,1,1,1,1,1,1,
    6, 2,1,1,2,3,5,
    6, 1,1,1,1,2,1,
    5, 3,1,5,1,2,
    6, 3,2,2,1,2,2,
    7, 2,1,4,1,1,1,1,
    6, 2,2,1,2,1,2,
    6, 1,1,1,3,2,3,
    5, 1,1,2,7,3,
    5, 1,2,2,1,5,
    5, 3,2,2,1,2,
    4, 3,2,1,2,
    3, 5,1,2,
    4, 2,2,1,2,
    4, 4,2,1,2,
    4, 6,2,3,2,
    4, 7,4,3,2,
    3, 7,4,4,
    3, 7,1,4,
    3, 6,1,4,
    3, 4,2,2,
    2, 2,1
  };

const int *specs[] = {heart, bear, crocodile, unknown,
                      pinwheel, difficult, non_unique, dragonfly, p200};
const unsigned n_examples = sizeof(specs)/sizeof(int*);

// STATISTICS: example-any