Method Nonogram

examples/nonogram.cpp:107–167

Construction of the model.

  /// Construction of the model.
  Nonogram(const SizeOptions& opt)
    : Script(opt), spec(specs[opt.size()]), b(*this,width()*height(),0,1) {
    Matrix<BoolVarArray> m(b, width(), height());

    {
      int spos = 2;
      // Post constraints for columns
      for (int w=0; w<width(); w++)
        extensional(*this, m.col(w), line(spos));
      // Post constraints for rows
      for (int h=0; h<height(); h++)
        extensional(*this, m.row(h), line(spos));
    }



    switch (opt.branching()) {
    case BRANCH_NONE:
      {
        /*
         * The following branches either by columns or rows, depending on
         * whether there are more hints relative to the height or width
         * for columns or rows.
         *
         * This idea is due to Pascal Van Hentenryck and has been suggested
         * to us by Hakan Kjellerstrand.
         */

        // Number of hints for columns
        int cols = 0;
        // Number of hints for rows
        int rows = 0;
        int spos = 2;
        for (int w=0; w<width(); w++) {
          int hint = spec[spos++];
          cols += hint; spos += hint;
        }
        for (int h=0; h<height(); h++) {
          int hint = spec[spos++];
          rows += hint; spos += hint;
        }

        if (rows*width() > cols*height()) {
          for (int w=0; w<width(); w++)
            branch(*this, m.col(w), BOOL_VAR_NONE(), BOOL_VAL_MAX());
        } else {
          for (int h=0; h<height(); h++)
            branch(*this, m.row(h), BOOL_VAR_NONE(), BOOL_VAL_MAX());
        }
      }
      break;
    case BRANCH_AFC:
      /*
       * The following just uses the AFC for branching. This is
       * equivalent to SIZE/AFC in this case since the variables are
       * binary.
       */
      branch(*this, b, BOOL_VAR_AFC_MAX(opt.decay()), BOOL_VAL_MAX());