Information

Deadline Geen deadline
Submission limit No limitation

Sign in

[Module4 Theory] Table Constraint


Question 1: Element3D

Consider a 3D Element constraint \(T[W][X][Y] = Z\) where \(T\) is 3D array of integers with dimensions \(4 \times 5 \times 10\) and \(D(W)=\{0..3\}, D(X)=\{0..4\}, D(Y)=\{0..9\}, D(Z)=\{100..200\}\). We would like to model this constraint using a Table constraint. What are the dimensions of the table (number of rows = number of tuples, number of columns = arity of tuples = number of variables)? Write your answer as "nRows,nColumns". For instance: 12,3

Question 2: Eternity2 (number of tuples)

For the Eternity2 edge-matching problem, assume a 10x10 board and a set of 100 pieces (assumed to be all different and without rotation symmetries). How many tuples does the Table constraint contain?

Question 3: Eternity2 (number of constraints)

For the Eternity2 edge-matching problem, assume a 10x10 board and a set of 100 pieces (assumed to be all different and without rotation symmetries). How many Table constraints are posted in the model?

Question 4: Eternity2 (table arity)

For the Eternity2 edge-matching problem, assume a 10x10 board and a set of 100 pieces (assumed to be all different and without rotation symmetries). What is the arity (number of variables in the scope) of each Table constraint?

Question 5: Regular

A Regular constraint has the form \(regular([x_1,...,x_n],D)\) where \(D\) is a deterministic finite-state automaton \((S,\Sigma,\delta,s_{0},A)\) where:

  • \(S\) is the set of states
  • \(\Sigma\) is the input alphabet (a finite, non-empty set of symbols)
  • \(\delta\) is the state-transition function: \(\delta :S \times \Sigma \rightarrow S\)
  • \(s_{0}\) is the initial state (an element of \(S\))
  • \(A\) is the set of accepting states (a subset of \(S\))

We have seen that this constraint can be modeled with a Table constraint.

Select all the true statements.

Question 6: STR2 Algo

In the STR2 filtering algorithm for the Table constraint, how many StateInt are necessary to maintain in a reversible way (on backtrack) the set of valid tuples?

Question 7: Reversible Sparse BitSet

Let us assume an implementation of Reversible Sparse BitSets on a machine where the word length is 4 bits (instead of 64 when long are used).

Consider the following current state of a Reversible Sparse BitSet rsbs:

  • nWords: 4
  • words: 1111|1111|1111|1111
  • nonZeroIdx: {0,1,2,3}
  • nNonZero: 4

and the following bitsets:

  • bitset1: 0001|0100|0110|0011
  • bitset2: 1000|1110|0101|1010
  • bitset3: 1110|0001|1001|1110

What is the resulting state of rsbs after the following lines:

sm.saveState();
rsbs.and(bitset2);
rsbs.and(bitset3);
sm.saveState();
rsbs.and(bitset1);
sm.restoreState();
Question 8: General Table Constraint

Select all the true statements: