CSP Instances in XCSP 2.0 Format

Benchmarks of the Solver Competition 2009 (tar file).

General warnings, follow religiously.

In the first series of homework, you will:
  1. build the data structures for storing and manipulating a CSP instance.
  2. write code to generate a CSP instances stored in the XCSP 2.0 (or higher) file format using the parsers available online.
We will restrict ourselves to simple CSP, in opposition to weighted CSPs (WCSPs) and quantified CSPs (QCSPs).

Before attempting to solve hard CSP instances as listed in the online benchmarks, it is best to test your code, at each step, on very simple problem instances, which you can check manually at every step.

For testing purposes, we recommend using the following instances:

Id Data Problem description Constraints encoding Comments
1 XCSP 2.0 file A chain of 4 variables Extension Conflicts
2 XCSP 2.0 file Coloring K4 with 2 colors Extension Conflicts
3 XCSP 2.0 file 3 Queens Extension Conflicts
4 XCSP 2.0 file 3 Queens Intension --
5 XCSP 2.0 file Map Coloring of Australia Extension Conflicts
6 XCSP 2.0 file Map Coloring of Australia Intension --
7 XCSP 2.0 file 4 Queens Extension Conflicts
8 XCSP 2.0 file 4 Queens Extension Supports
9 XCSP 2.0 file 5 Queens Intension --
10 XCSP 2.0 file 6 Queens Extension Conflicts
11 XCSP 2.0 file 6 Queens Intension --
12 XCSP 2.0 file Zebra Puzzle Intension Nonbinary and unary
13 XCSP 2.0 file Zebra Puzzle Intension Only binary and Unary
14 XCSP 2.0 file
OLD XCSP 2.0 file
Zebra Puzzle
The difference between the OLD and NEW is in the interpretation of the "plusOne" constraint. NEW matches the definition used in Regin's paper.
OLD: 1 2|2 3|3 4|4 5
NEW: 2 1|3 2|4 3|5 4
Extension (supports+conflicts) Only binary and Unary
15 XCSP 2.0 file
OLD XCSP 2.0 file
Zebra Puzzle The difference between the OLD and NEW is in the interpretation of the "plusOne" constraint. NEW matches the definition used in Regin's paper.
OLD: 1 2|2 3|3 4|4 5
NEW: 2 1|3 2|4 3|5 4
Extension (supports only) Only binary and Unary
16 Domino, Hanoi, Knights, Latin Squares, Langford, Interesting toy problems (a.k.a. Academic Series) from the CSP Benchmark page Extension Only binary
17a XCSP 2.0 file One random instance with (n=20,a=8,e=100,tuples=20)
= (n=20,a=8,p=52%,t=31.25%);
Extension (conflicts only) Only binary, must have 15 solutions
17c TAR file with 9x50 XCSP 2.0 files 50 random instances with (n=32,a=8,density=20%,t=0.1,0.2,...,0.9)
Good for observing the phase transition. For each tightness value, you should compute the average of time/#CC/#BT/#NV.
Extension (conflicts only) Only binary.
17d TAR file with 9x30 XCSP 2.0 files 30 random instances with (n=20,a=6,density=25%,t=0.1,0.2,...,0.9)
Good for observing the phase transition. For each tightness value, you should compute the average of time/#CC/#BT/#NV.
Extension (support only) Only binary.
18 XCSP 2.0 file Random instance with (n=20,a=8,e=200,tuples=11, 20, 22, 25, 30, 33, 34, 36, 39, and 44) = (n=20,a=8,p=10.5%,t= 17.2% to 68.8%) Extension (conflicts only) Only binary, first instance has a huge number of solutions (7,722,811,690 solutions!).
Other XCSP 2.1 instances CSP instances used in solvers competitions
The goal is not to compete, but to test your code
for errors and performance.
Various --

Acknowledgment: Christophe Lecoutre, Olivier Roussel, Shant Karakashian, Ken Bayer.
Berthe Choueiry
Last modified: Thu Dec 6 12:02:48 CST 2012