Skip to content
Snippets Groups Projects
CP.java 2.85 KiB
Newer Older
Paul A. Rubin's avatar
Paul A. Rubin committed
package setgame;

import ilog.concert.IloAnd;
import ilog.concert.IloConstraint;
import ilog.concert.IloException;
import ilog.concert.IloIntVar;
import ilog.cp.IloCP;

/**
 * CP implements a constraint programming model to find all set.
 * @author Paul A. Rubin (rubin@msu.edu)
 */
public final class CP implements AutoCloseable {
  private final IloCP model;           // the CP model
  private final IloIntVar[] cards;     // the index of the card in each slot
  private final IloIntVar[][] values;  // the value of each feature (row) in
                                       // each slot (column)

  /**
   * Constructs the CP model.
   * @param game the game to solve
   * @throws IloException if CPO objects to something
   */
  public CP(final Set game) throws IloException {
    model = new IloCP();
    cards = new IloIntVar[Set.SETSIZE];
    values = new IloIntVar[Set.NFEATURES][Set.SETSIZE];
    // Define the variables.
    for (int slot = 0; slot < Set.SETSIZE; slot++) {
      cards[slot] = model.intVar(0, Set.NCARDS - 1, "card_in_slot_" + slot);
      for (int feature = 0; feature < Set.NFEATURES; feature++) {
        values[feature][slot] =
          model.intVar(0, Set.NVALUES, "slot_" + slot + "_feature_" + feature);
      }
    }
    // Constraint: No card can be used twice.
    model.add(model.allDiff(cards));
    // Constraint: To avoid finding all possible permutations of all possible
    // hands, the slots must be filled in ascending card order.
    for (int slot = 1; slot < Set.SETSIZE; slot++) {
      model.add(model.lt(cards[slot - 1], cards[slot]));
    }
    // Constraint: The value of a feature in a slot is inherited from the
    // card in that slot.
    for (int feature = 0; feature < Set.NFEATURES; feature++) {
      int[] v = game.getValues(feature);
      for (int slot = 0; slot < Set.SETSIZE; slot++) {
        model.add(model.eq(values[feature][slot],
                           model.element(v, cards[slot])));
      }
    }
    // Constraint: For each feature, either all slots have the same value or
    // all slots are different.
    for (int feature = 0; feature < Set.NFEATURES; feature++) {
      IloConstraint different = model.allDiff(values[feature]);
      IloAnd same = model.and();
      for (int slot = 0; slot < Set.SETSIZE - 1; slot++) {
        same.add(model.eq(values[feature][slot], values[feature][slot + 1]));
      }
      model.add(model.or(different, same));
    }
    // Suppress output.
    model.setOut(null);
  }

  /**
   * Solves the model and returns the number of solutions found.
   * @return the solution count
   * @throws IloException if CPO pitches a fit
   */
  public int solve() throws IloException {
    int found = 0;
    model.startNewSearch();
    while (model.next()) {
      found += 1;
    }
    return found;
  }

  /**
   * Closes the model.
   */
  @Override
  public void close() {
    model.end();
  }

}