Description

Python-CPSolver is a flexible and simple tool that leverages constraint technologies to search for solutions over large data spaces. It provides all the necessary components to effectively tackle complex constraint-based problem

Python-CPSolver is designed to implement and understand various algorithms for solving combinatorial problems, as described in the literature and adapted to constraint-solving techniques. Rather than focusing on creating a competitive tool, Python-CPSolver aims to provide a user-friendly environment for validating
and developing new methods.

Keeping our core purpose in mind, Python-CPSolver [See GitHub] comprises four essential modules: Searching, Variables, Branching, and Propagators. Each of these modules was crafted with a minimalist approach, prioritising simplicity over efficiency. For a clearer grasp of our intent, consider our overuse of Python Lists, chosen for their versatility and utility over creating specialised data structures for similar tasks.

Figure 1 provides a comprehensive overview of the inner workings of Python-CPSolver. It is implemented using Object-Oriented Programming, drawing inspiration from the structures of Gecode and Chuffed. Some identifiers of classes, attributes, and methods are borrowed from these two solvers, while other segments of
the code are based on the CPFloat-Gecode project [See].

Figure 1. General class diagram

Figure 1. General class diagram

Example 1: Let S, E, N, D, M, O, R, and Y represent distinct digits from 0 to 9. Find a digit substitution for each letter such that the equation SEND + MORE = MONEY holds true. No two letters represent the same digit.

Figure 2 illustrates the implementation of Example 1, tackling the puzzle SEND+MORE=MONEY.

Figure 2. Implementation of the CSP for Example 1.

References

[1] Araya, I., Neveu, B., and Trombettoni, G. Exploiting common subexpressions in numerical csps. pp. 342–357.

The complete source code can be found in :

Source Code

https://github.com/GonzaloHernandez/python-cpsolver

Documentation

https://drive.google.com/file/d/1gRh-pOGc-uszRlNpsD0_x2uHuYQN9rTa/view?usp=drive_link