Constraint Solver Part 5: Different data structure

Series: Constraint Solver in Julia

This is part 5 of the series about: How to build a Constraint Programming solver?

Let’s do a small recap of what we have done so far.
We’ve created a julia package in the first post and implemented the most basic backtracking for solving a sudoku puzzle. We understood that this is pretty slow as we could use the information after we fixed a cell to a value to find out the values of cells which are connected by a constraint to that cell. In part 3 I described that these new fixes itself can be used further on which gave us a performance improvement again.

In the last post we tried not to make backtracking faster but instead tried to avoid it as much as possible by solving the sudoku in a more human like fashion.

We could now further try to reduce the number of steps we call the now slower alldifferent constraint or make it faster or change the ordering of the calls or fix values in a different ordering, as at the moment we only decide which cell we want to tackle next in backtracking but not on the ordering of how we fix the number in a cell i.e if it has the possible values 5,6,7 it might be reasonable to start with the 7 if we think that it’s more likely based on some heuristics.

What I want to do instead in this post is changing the data structure a bit. We are currently working on a grid which seems to be a good choice for a sudoku or even Str8ts and the 8-queen problem as well as magic squares but it’s not always the case for example it’s stupid for graph coloring so maybe we should just have linear indices internally instead of cartesian indices. Another point is that we are working with a dictionary to represent the values in our search space for each cell but adding and removing to a dictionary sometimes seems quite stupid as we set a cell in backtracking and then reset it and have to fill all the values again it had before. Maybe there is a better data structure. Besides that it seems to be reasonable to have a struct for a variable which can hold some information of that variable maybe something like a name for a country in graph coloring?

Additionally I think it’s quite weird to have a grid and a search space separately if I think about it. The variable could hold the information about being fixed or not.

I found a new idea at MiniCP Part 2 (unfortunately all sites of the website have the same url :/).
MiniCP is a constraint solver used in teaching constraint solving so you might in general be interested at that. Pascal Van Hentenryck who also is the professor of the online about Discrete optimization…