Examples

NUCS comes with several examples.

Most of these examples can be run from the command line and support the following options:

  • --consistency: set the consistency algorithm (0 is for BC), defaults to BC

  • --cp-max-height: set the maximal height of the choice points stack, defaults to 512

  • --dataset: the dataset to use

  • --display-solutions: display the solution(s), defaults to true

  • --display-stats: display the statistics, defaults to true

  • --find-all: find all solutions, defaults to false

  • --help: show the help

  • --log-level: set the log level, can take the values DEBUG, INFO, WARNING, ERROR, CRITICAL, defaults to INFO

  • --n: define the size of the problem

  • --optimization-mode: set the optimizer mode (RESET or PRUNE), defaults to RESET

  • --processors: define the number of processors to use

  • --symmetry-breaking/--no-symmetry-breaking: leverage symmetries in the problem, defaults to true

class nucs.examples.all_interval_series.all_interval_series_problem.AllIntervalSeriesProblem[source]

This is CSPLIB problem #7 (https://www.csplib.org/Problems/prob007/).

This problem can be run with the command:

NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.all_interval_series

This problem leverages the propagators:

  • nucs.propagators.abs_eq_propagator,

  • nucs.propagators.alldifferent_propagator,

  • nucs.propagators.leq_propagator,

  • nucs.propagators.sum_eq_propagator.

class nucs.examples.alphanumeric.alphanumeric_problem.AlphanumericProblem[source]

A general alphanumeric problem where letters represent unique values.

The sum of each letter’s value in a word equals a target: e.g. ALPHA puzzle: BALLET=45, CELLO=43, …

This problem can be run with the command:

NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.alphanumeric

This problem leverages the propagators:

  • nucs.propagators.linear_eq_c_propagator,

  • nucs.propagators.alldifferent_propagator.

class nucs.examples.bibd.bibd_problem.BIBDProblem[source]

CSPLIB problem #28 - https://www.csplib.org/Problems/prob028/

This problem can be run with the command:

NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.bibd -v 8 -b 14 -r 7 -k 4 -l 3

This problem leverages the propagators:

  • nucs.propagators.exactly_true_propagator,

  • nucs.propagators.and_propagator,

  • nucs.propagators.lexleq_propagator.

class nucs.examples.cryptarithmetic.cryptarithmetic_problem.CryptarithmeticProblem[source]

A general cryptarithmetic problem where letters represent unique values.

Supports addition constraints, multi-digit column arithmetic where letter values are digits: e.g. DONALD + GERALD = ROBERT

This problem can be run with the command:

NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.cryptarithmetic

This problem leverages the propagators:

  • nucs.propagators.linear_eq_c_propagator,

  • nucs.propagators.alldifferent_propagator.

class nucs.examples.employee_scheduling.employee_scheduling_problem.EmployeeSchedulingProblem[source]

See https://developers.google.com/optimization/scheduling/employee_scheduling.

This problem can be run with the command:

NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.employee_scheduling

This problem leverages the propagators:

  • nucs.propagators.count_eq_c_propagator,

  • nucs.propagators.count_eq_propagator,

  • nucs.propagators.count_leq_c_propagator.

class nucs.examples.golomb.golomb_problem.GolombProblem[source]

This is the famous Golomb ruler problem.

It consists in finding n integers mark_i such that: - mark_0 = 0, - mark_0 <…< mark_n-1, - for all i < j, mark_j - mark_i are different, - mark_n-1 is minimal.

CSPLIB problem #6 - https://www.csplib.org/Problems/prob006/

This problem can be run with the command:

NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.golomb

This problem leverages the propagators:

  • nucs.propagators.alldifferent_propagator,

  • nucs.propagators.leq_propagator,

  • nucs.propagators.sum_eq_propagator.

class nucs.examples.knapsack.knapsack_problem.KnapsackProblem[source]

CSPLIB problem #133 - https://www.csplib.org/Problems/prob133/

This problem can be run with the command:

NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.knapsack

This problem leverages the propagators:

  • nucs.propagators.linear_eq_c_propagator,

  • nucs.propagators.linear_leq_c_propagator.

class nucs.examples.langford.langford_problem.LangfordProblem[source]

CSPLIB problem #24 - https://www.csplib.org/Problems/prob024/

This problem can be run with the command:

NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.langford

This problem leverages the propagators:

  • nucs.propagators.linear_eq_c_propagator,

  • nucs.propagators.alldifferent_propagator.

class nucs.examples.magic_sequence.magic_sequence_problem.MagicSequenceProblem[source]

Find a sequence x_0, … x_n-1 such that each x_i is the number of occurrences of i in the sequence.

CSPLIB problem #19 - https://www.csplib.org/Problems/prob019/

This problem can be run with the command:

NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.magic_sequence

This problem leverages the propagators:

  • nucs.propagators.linear_eq_c_propagator,

  • nucs.propagators.count_eq_propagator,

  • nucs.propagators.sum_eq_propagator.

class nucs.examples.magic_square.magic_square_problem.MagicSquareProblem[source]

A simple model for magic squares.

CSPLIB problem #19 - https://www.csplib.org/Problems/prob019/

This problem can be run with the command:

NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.magic_square

This problem leverages the propagators:

  • nucs.propagators.alldifferent_propagator,

  • nucs.propagators.leq_propagator,

  • nucs.propagators.sum_eq_propagator.

class nucs.examples.quasigroup.quasigroup_problem.QuasigroupProblem[source]

CSPLIB problem #3 - https://www.csplib.org/Problems/prob003/

This problem can be run with the command:

NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.quasigroup

This quasigroup problem leverages the problem nucs.problems.latin_square_problem and the propagators:

  • nucs.propagators.element_liv_alldifferent_propagator.

class nucs.examples.queens.queens_problem.QueensProblem[source]

A simple model for the n-queens problem.

CSPLIB problem #54 - https://www.csplib.org/Problems/prob054/

The problem can be run with the command:

NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.queens

This problem leverages the propagators:

  • nucs.propagators.alldifferent_propagator.

class nucs.examples.schur_lemma.schur_lemma_problem.SchurLemmaProblem[source]

CSPLIB problem #15 - https://www.csplib.org/Problems/prob015/

The problem can be run with the command:

NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.schur_lemma

This problem leverages the propagators:

  • nucs.propagators.exactly_true_propagator,

  • nucs.propagators.linear_leq_c_propagator,

  • nucs.propagators.lexleq_propagator.

class nucs.examples.sports_tournament_scheduling.sports_tournament_scheduling_problem.SportsTournamentSchedulingProblem[source]

The problem is to schedule a tournament of n teams over n−1 weeks, with each week divided into n/2 periods, and each period divided into two slots.

The first team in each slot plays at home, whilst the second plays the first team away.

A tournament must satisfy the following three constraints: - every team plays once a week; - every team plays at most twice in the same period over the tournament; - every team plays every other team.

CSPLIB problem #26 - https://www.csplib.org/Problems/prob026/

The problem can be run with the command:

NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.sports_tournament_scheduling

This problem leverages the propagators:

  • nucs.propagators.alldifferent_propagator,

  • nucs.propagators.exactly_eq_propagator,

  • nucs.propagators.gcc_propagator,

  • nucs.propagators.relation_propagator.

class nucs.examples.sudoku.sudoku_problem.SudokuProblem[source]

A simple model for the sudoku problem.

This problem leverages the nucs.problems.latin_square_problem and the propagators:

  • nucs.propagators.alldifferent_propagator.

class nucs.examples.tsp.tsp_problem.TSPProblem[source]

The problem can be run with the command:

NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.tsp

This problem leverages the nucs.problems.circuit_problem and the propagators:

  • nucs.propagators.element_iv_propagator,

  • nucs.propagators.sum_eq_propagator.