The Pseudotron

Practical Applications

This is a very general description that fits many problems, especially many real life situations can be expressed in this form.

Many puzzles and riddles are constraint satisfaction problems. I first learned about constraint propagation when I was interested in sudoku solving, but also many other logic puzzles can be cast into the same form. For example the 8 queens problem is very popular in the CSP literature and is often used as a test case for algorithms and heuristics.

But also scheduling and allocation problems are constraint satisfaction problems. Suppose you run a school and have to make a timetable. You have a number of classes taking a number of courses and you have a number of teachers teaching those courses. Now you need to assign classes, courses and teachers in such a way that no teacher teaches more than the maximum possible workload, that every teacher teaches at most one course simultaneously and that every class only takes at most one course simultaneously. This is a constraint satisfaction problem.

Plans for CSP in BOLTS

My next goal is to treat parameter assignment in BOLTS as a CSP. A part in BOLTS has a number of parameters that describe dimensions or other properties of the part. But these parameters are not independent, for example the diameter of a screw often determines the dimensions of its head. These dependencies are encoded usually encoded in tables (e.g here at the bottom). The user selects a few of the parameters (e.g. the diameter and the length of a screw) and the remaining ones are looked up using these tables.

The datastructures that are currently used in BOLTS to store tables and to perform the parameter lookup are ugly and cumbersome and fragile, as they grew organically, and were adapted to more and more requirements and use cases.

Recently I realized that this parameter lookup is actually a CSP. The parameters correspond to variables, and the tables and user selected values can be realized as constraints. This structure makes it much easier to write a flexible and robust implementation, and opens up more possibilities:

• Global tables that allow to share data between several parts (e.g. for thread properties) are very easy to do. The CSP just grows by a few variables and constraints, but doesn't change fundamentally. I had tried several times to implement this with the old data structures, but things like range checking turned out to be very difficult to get. As a CSP, this is covered very elegantly by a standard algorithm.
• Reverse Lookup or Search are often requested features that allow the user to filter the possible variations or sizes of a part based on criteria on one or several parameters. For example, the user might need a screw with a head smaller than some length for a design where there is not much space available. This can also be treated as a constraint satisfaction problem, with the difference, that the constraints for the user entered parameters would be replaced by constraints for the search criteria, and that the solution is not necessarily unique in this case.

Theoretical considerations

From an algorithmic standpoint CSPs are a bit curious. A CSP problem can be solved by a very simple algorithm (backtracking), that can be implemented in a few lines, but has an exponential worst case complexity. And for the general problem there is nothing that can be done about it. So the largest part of the CSP literature deals with variations and specialisations of backtracking, heuristics and problem specific optimisation. But in the end everything is quite similar to backtracking. So in a nutshell: "use backtracking, and if that doesn't work for your problem, try to find optimisations and heuristics that make backtracking work for your problem."

That is maybe a bit unfair. If your job is to find something in a tree-like search space, you will just have to walk a tree-like search space. And unless the problem has structure, you can not really be clever about that.

I actually enjoyed reading about methods and algorithms for CSPs, there are some nice ideas (like local consistency), many applications of other fields (like graph theory) and lots of cool applications (AI, scheduling, puzzles, ...).

Constraining Order

Of course I got nerd sniped and wrote my own constraint satisfaction library for python. It is called Constraining Order, it is available through pypi

https://pypi.python.org/pypi/constrainingorder

and you can read more about it in the documentation.

Of course, there already exist better, faster and more powerful alternatives like

• gecode
• or-tools
• choco

Especially gecode looks great and is very well documented. But its python bindings were outdated, and the machinery for updating them was basically undocumented, so I tried for a few hours to get them updated, but then gave up. For python or-tools is probably the best choice, but there the documentation is scattered and pretty sparse for python. Then there are a few pure python implementations, but they are also pretty badly documented, and I enjoy writing code more than fighting through undocumented, rough code trying to figure out what is going on.

So yes, I am guilty of NIH, so to punish me for releasing another half-baked, slow and buggy CSP framework into the wild, I made me write proper documentation. Joking aside, as CSPs are very problem-specific, and one needs to have a bit of background to understand the advantages and disadvantages of the different approaches, so black-box solutions are not so helpful. In this case delegation just doesn't work, as the library can not relieve you from knowing about the theory. And I believe the best way of learning something is to work on it yourself.