[Part1 Theory] TinyCSP

Paste this command into your terminal:

The password to connect is

Please answer to all the questions. Internal error {} has not a valid extension. {} is too heavy.

Question 1: N-Queens model

For solving the N-Queens problem, which decision model would you recommend?

An array of bitsets of size N.

A set of 2D coordinates where each queen is positioned.

A decision vector of integers of size N.

A NxN boolean decision matrix.

Question 2: CP - complete approach

Constraint Programming is a complete approach, it means that:

It can model any type of problems with a rich modeling language.

It has the potential to discover all the feasible solutions to a combinatorial problem or to prove that no solution exists

It can solve efficiently NP-complete problems.

It can be extended by adding new functionality such as new constraints to make it more complete for the users.

Question 3: CP - declarative

Constraint Programming is declarative, it means that:

The user is not limited to linear constraints or closes as it is the case for linear programming or SAT.

The user expresses the properties (constraints) that need to be satisfied using an API or dedicated domain specific language.

The user declares and describes loudly the problem he wants to solve using a microphone.

The user has to implement all the steps of how to find a solution in his favorite programming language.

Question 4: TinyCSP - Fix point

In TinyCSP.java, the fix-point computation:

Executes all the propagate method of all the constraints exactly once.

Executes the propagate method of all the constraints in each round, even if the domains of the variables in the scope of the constraints were not modified between successive executions.

Is randomized, choosing randomly one constraint to propagate and stopping whenever the chosen constraint declares it didn’t remove any value.

Uses a propagation Queue that only contains the constraints involving a variable with a recently modified domain.

Question 5: TinyCSP - domain implementation

In TinyCSP, the implementation of the domains uses a

TreeSet data structure.

A list of integer data-structure.

BitSet data structure.

HashSet data structure.

Question 6: TinyCSP - Backtracking

In TinyCSP, the domains are restored on backtracking using:

A clone mechanism, making a copy of all the domains before modification by the branching and restoring it on backtrack.

The set of removed values is stored at each node and reinserted on backtrack to that node.

A clone mechanism, making a copy of only of the domain of the variable chosen for branching and restoring the domain of that specific variable on backtrack.

There is no need to restore domains on backtrack, the call stack of the DFS recursion will deal with it automatically.

Deadline	No deadline
Submission limit	2 submissions every 1 hour(s)

Information

Sign in