Course list Register Sign in

Information

Deadline No deadline
Submission limit No limitation

Sign in

Sign in

[Part4 Exercise] Table Constraints

During the course, you have seen the Table constraint and some of its possible application. We will now dive into its implementation and use it to model the Eternity problem

1. Table constraint

a. Implementing the residues

Fill in all the gaps of the StateSparseBitSet data structure in order to add the concept of residue (idea of caching the word with non-empty intersection) to have an efficient algorithm.

Your task is to finish the implementation in StateSparseBitSet.java:

  1. Implement the check of the intersection for the word remembered by the residue (TODO 1).
  2. Implement the update of the residue (TODO 2).

Check that your implementation passes the tests StateSparseBitSetTest.java.

b. Compact-Table

Fill in all the gaps of the Compact-Table algorithm. This implementation uses StateSparseBitSet and maintains the state (the set of valid tuples) from one propagation to another. You will need to have completed the previous question before beginning this implementation.

Your task is to finish the implementation in TableCT.java:

  1. Add the filling of the supports StateSparseBitSets (TODO 1). You can test that your filling is correct by running the tests testInitSupports1 and testInitSupports2 from TableCTTest.java.
  2. Implement the hasChanged method (TODO 2). It is the heart of the incremental updates: it must return true if the domain size of a variable has changed since the last propagation.
  3. Within the propagation function, implement the computation of the set of supported tuples (TODO 3). You can test that the computation is done correctly by running the tests testSetSupportedTuples1 and testSetSupportedTuples2.
  4. Within the propagation function, implement the condition for removing a given value (TODO 4)

For the filling of the supports (TODO 1), look at the following table, composed of one column:

Table
Index \(X\)
0 5
1 2
2 4
3 1
4 0
5 2

Assume that \(D(X)={0,2,4}\). Then the supports of \(X\) when initializing the Table constraint are the following (only the last 6 bits are shown):

  • support(X, 0): 010000 - row 4 is valid
  • support(X, 1): 000000 - no valid row
  • support(X, 2): 100010 - rows 1 and 5 are both valid
  • support(X, 3): 000000 - no valid row
  • support(X, 4): 000100 - row 2 is valid

Your fully implemented class should pass all the tests from TableCTTest.java.

2. Eternity

Fill in all the gaps in order to solve the Eternity II problem.

Your task is to finish the implementation in Eternity.java:

  1. Implement the filling of the table containing all the pieces and their rotations (TODO 1). You can check that your table is correctly constructed by running the test testTableContent from EternityTest.java.

  2. Implement the constraints of the model (TODO 2)

    • place all the pieces
    • allow only valid pieces
    • place the gray sides on the edges of the board

  3. Continue the implementation of the search. Currently, it uses the and combinator to branch on some of the variables from the problem. You need to continue its implementation to be sure that it branches on all of them (TODO 3).

Check that your implementation passes all the tests from EternityTest.java.