CSP-Solver

Implementation of the solver algorithms: backtracking, forward checking, and heuristics such as MRV and LCV to solve constraint satisfaction problems (CSPs).

Defines functions to solve a CSP problem using backtracking algorithm.

Author

Ch. Demko

Author

agueguen-LR adrien.gueguen@etudiant.univ-lr.fr

Date

2025

Copyright

GNU Lesser General Public License v3.0

Functions

void reduce_domains(const CSPProblem *csp, size_t *values, const void *data, Domain **domains, CSPDataChecklist dataChecklist)

Reduce the domains of the variables based on the data provided.

Parameters:

  • csp – The CSP problem to reduce.

  • values – The values of the variables.

  • data – The data to pass to the check function.

  • domains – The domains of the variables.

  • dataChecklist – A pointer to function to get the list of constraints affected by the contents of data for the current variable.

bool csp_problem_is_consistent(const CSPProblem *csp, const size_t *values, const void *data, size_t index, FilledVariables *fv, CSPValueChecklist *checklist)

Verify if the CSP problem is consistent at the specified index.

Parameters:

  • csp – The CSP problem to verify.

  • values – The values of the variables.

  • data – The data to pass to the check function.

  • index – The index of the current variable.

  • fv – The FilledVariables structure to track filled variables.

  • checklist – A pointer to function to get the list of necessary constraints for the current variable.

Returns:

true if the CSP problem is consistent, false otherwise.

Pre:

The csp library is initialised.

bool csp_problem_solve(const CSPProblem *csp, size_t *values, const void *data, SolveType solve_type, CSPValueChecklist *checklist, CSPDataChecklist *dataChecklist, size_t *benchmark)

Solve the CSP problem using backtracking.

Parameters:

  • csp – The CSP problem to solve.

  • values – The values of the variables.

  • data – The data to pass to the check function.

  • solve_type – The type of solving to use (FC, OVARS, OVALS).

  • checklist – A pointer to function to get the list of necessary constraints for the current variable.

  • dataChecklist – A pointer to function to get the list of constraints affected by the contents of data for the current variable.

  • benchmark – pointer to Node counter for benchmarking, NULL if no benchmarking required

Returns:

true if the CSP problem is solved, false otherwise.

Pre:

The csp library is initialised.

Post:

The values are assigned to the solution.

Library CSP forward checking

Author

agueguen-LR adrien.gueguen@etudiant.univ-lr.fr

Date

2025

Copyright

GNU Lesser General Public License v3.0

Functions

bool csp_problem_forward_check(const CSPProblem *csp, size_t *values, const void *data, size_t index, FilledVariables *fv, CSPValueChecklist *checklist, Domain **domains, DomainChange *change_stack, size_t *stack_top)

Forward check the CSP problem. Updates the domains of the variables

Parameters:

  • csp – The CSP problem to check.

  • values – The values of the variables.

  • data – The data to pass to the check function.

  • index – The index of the current variable.

  • fv – The filled variables structure to track filled variables.

  • checklist – A pointer to function to get the list of necessary constraints for the current variable.

  • domains – The domains of the variables.

  • change_stack – The stack of changes made during forward checking.

  • stack_top – The top of the change stack.

Returns:

true if the CSP problem is consistent, false otherwise.

Pre:

The csp library is initialised.

Library CSP variable heuristics

Author

agueguen-LR adrien.gueguen@etudiant.univ-lr.fr

Date

2025

Copyright

GNU Lesser General Public License v3.0

Functions

size_t csp_problem_choose_min_domain(const CSPProblem *csp, const FilledVariables *fv, Domain **domains)

Choose the next variable to assign in the CSP problem. This function selects the variable with the smallest domain size (Minimum Remaining Values heuristic).

Parameters:

  • csp – The CSP problem instance.

  • fv – The structure tracking filled variables.

  • domains – The array of domains for each variable.

Returns:

The index of the chosen variable.

size_t csp_problem_choose_max_domain(const CSPProblem *csp, const FilledVariables *fv, Domain **domains)

Choose the next variable to assign in the CSP problem. This function selects the variable with the largest domain size (Maximum Remaining Values heuristic).

Parameters:

  • csp –

  • fv –

  • domains –

Returns:

File containing the definition of the types and structures used in the CSP And the functions to manipulate them.

Author

agueguen-LR adrien.gueguen@etudiant.univ-lr.fr

Date

2025

Copyright

GNU Lesser General Public License v3.0

Typedefs

typedef void CSPValueChecklist(const CSPProblem *csp, CSPConstraint **checklist, size_t *amount, size_t index, FilledVariables *fv)

Get the list of value constraints to verify for the current variable to know if the CSPProblem is consistent.

Note

This function is used by csp_problem_is_consistent.

Param csp:

The CSP problem.

Param checklist:

Array to store the list of constraints to verify.

Param amount:

Pointer to size_t to store the number of constraints to verify.

Param index:

The index of the current variable.

Param fv:

The FilledVariables structure to track filled variables.

typedef void CSPDataChecklist(const CSPProblem *csp, CSPConstraint **checklist, size_t *amount, size_t index)

Get the list of data constraints to verify for the current variable to know if the CSPProblem is consistent.

Param csp:

The CSP problem.

Param checklist:

Array to store the list of constraints to verify.

Param amount:

Pointer to size_t to store the number of constraints to verify.

Param index:

The index of the current variable.

Enums

enum SolveType

Values:

enumerator FC
enumerator OVARS_MIN
enumerator OVARS_MAX
enumerator OVALS

Functions

void filled_variables_mark_filled(FilledVariables *fv, size_t index)

Mark a variable as filled.

Parameters:

  • fv – The FilledVariables structure.

  • index – The index of the variable to mark as filled.

bool filled_variables_is_filled(const FilledVariables *fv, size_t index)

Check if a variable is filled.

Parameters:

  • fv – The FilledVariables structure.

  • index – The index of the variable to check.

Returns:

true if the variable is filled, false otherwise.

void filled_variables_mark_unfilled(FilledVariables *fv, size_t index)

Mark a variable as unfilled.

Parameters:

  • fv – The FilledVariables structure.

  • index – The index of the variable to mark as unfilled.

bool filled_variables_all_filled(const FilledVariables *fv)

Check if all variables are filled.

Parameters:

fv – The FilledVariables structure.

Returns:

true if all variables are filled, false otherwise.

size_t filled_variables_next_unfilled(const FilledVariables *fv, size_t index)

Get the next unfilled variable.

Parameters:

  • fv – The FilledVariables structure.

  • index – The index to start searching from.

Returns:

The index of the next unfilled variable, or SIZE_MAX if all are filled.

size_t filled_variables_next_filled(const FilledVariables *fv, size_t index)

Get the next filled variable.

Parameters:

  • fv – The FilledVariables structure.

  • index – The index to start searching from.

Returns:

The index of the next filled variable, or SIZE_MAX if all are unfilled.

FilledVariables *filled_variables_create(size_t num_variables)

Create a new FilledVariables structure.

Parameters:

num_variables – The number of variables to track.

Returns:

A pointer to the new FilledVariables structure, or NULL on failure.

void filled_variables_destroy(FilledVariables *fv)

Free the memory allocated for a FilledVariables structure.

Parameters:

fv – The FilledVariables structure to free.

Domain *domain_create(size_t size)

Create a new Domain structure.

Parameters:

size – The size of the domain.

Returns:

A pointer to the new Domain structure, or NULL on failure.

void domain_destroy(Domain *domain)

Free the memory allocated for a Domain structure.

Parameters:

domain – The Domain structure to free.

void print_domain(const Domain *domain)

Print the values in a Domain structure.

Parameters:

domain – The Domain structure to print.

void print_domains(const Domain **domains, const size_t num_domains)

Print the values in an array of Domain structures.

Parameters:

  • domains – The array of Domain structures to print.

  • num_domains – The number of Domain structures in the array.

DomainChange *domain_change_stack_create(size_t size)

Create a new DomainChange structure.

Parameters:

size – The size of the change stack.

Returns:

A pointer to the new DomainChange structure, or NULL on failure.

void domain_change_stack_destroy(DomainChange *stack)

Free the memory allocated for a DomainChange structure.

Parameters:

stack – The DomainChange structure to free.

void domain_change_stack_restore(const DomainChange *stack, size_t *stack_top, const size_t *stop_point, Domain **domains)

Restore the domains from the change stack up to the specified stop point.

Parameters:

  • stack – The DomainChange structure.

  • stack_top – Pointer to the top of the stack.

  • stop_point – Pointer to the point to restore up to.

  • domains – The array of domains to restore.

void domain_change_stack_add(DomainChange *stack, size_t *stack_top, size_t domain_index, size_t value)

Add a change to the change stack.

Parameters:

  • stack – The DomainChange structure.

  • stack_top – Pointer to the top of the stack.

  • domain_index – The index of the domain that changed.

  • value – The value that was removed from the domain.

struct Domain
#include <types-and-structs.h>

Structure to represent the domain of a variable in a CSP problem. It contains the number of values in the domain and an array of values.

Public Members

size_t amount
size_t values[]
struct DomainChange
#include <types-and-structs.h>

Structure to track changes in the domain of a variable during forward checking. Use as a stack to store the changes. It stores the index of the domain and the value that was removed.

Public Members

size_t domain_index
size_t value
struct FilledVariables
#include <types-and-structs.h>

Structure to track filled variables in a CSP problem. It uses a bitset to efficiently track which variables are filled.

Public Members

size_t size
uint8_t *bitset