The puzzle consists of a square grid of cells, which can be red or blue. Some of the cells are set to either colour at the begining, while most are blank. The task is to assign red or blue to all cells so that:
- each row and column has the same number of red and blue cells
- there are no more than two adjacent cells of the same colour in the same direction (horizontal or vertical)
The rules are deceptively simple; a good measure of reasoning goes into finding the solution, though. As you go through a few of them, patterns emerge. But can the solution be automated?
The large puzzle is a ten by ten grid; with about 20 pre-set, about 80 cells need to be decided. In a brute force fashion, that means about 2^80 combinations, or somewhat over 10^24. Clearly brute force is not going to cut it.
Exploiting the conditions that the solution must meet can add some intelligence. This limits the actual number of combinations, but it forces the algorithm to be a lot more clever when selecting which assignments to make. Enter constraint propagation.
In constraint propagation, the two constraints defined above limit the values that some of the cells can take, wiping out large swaths of combinations at once. Once the constraint propagation gets stuck, the next step is just trying out one or the other colour in one of the remaining cells, and see how it goes from there.
Let's look at the search space as a binary tree, with each level corresponding to one cell, and the two branches are each of the two colours. The procedure becomes:
- set the known cells to their colours
- propagate the constraints to set as many cells as possible
- if all cells get filled or the problem reaches inconsistency (there is no way to meet the constraints), the algorithm is done
- otherwise, select one of the remaining cells and arbitrarily assign one colour, and try to solve that (going back to 2, starting a recursion); if this solves the problem, success
- otherwise, try the other color (again, going back to 2, starting a recursion); if this solves the problem, again, success
- otherwise, the procedure ends, but reporting that the problem is unsolvable
This process recursively explores the binary tree, using constraint propagation as a shortcut whereever possible. In practice, I still have to find a puzzle where more than 10 branching operations are needed, as constraint propagation does most of the heavy lifting.
The solution procedure can be summarized in pseudocode as:
solve(problem): propagate_constraints(problem) if solved(problem) or infeasible(problem) return problem cell = get_unset_cell(problem) new_problem = problem + set(cell, red) candidate_solution = solve(new_problem) if solved(candidate_solution) return candidate solution new_problem = problem + set(cell, blue) candidate_solution = solve(new_problem) return candidate solution
The recursion is seen clearly in this pseudocode. If the constraint propagation does not directly solve the puzzle, a new problem is created by setting one cell to red, and passed over to the recursive call. If that returns with infeasibility, there is still the option of making it blue. After that, there is nothing else to be done: the cell can only be red or blue.
Up to now I have glossed over the actual constraint propagation. Each of the two constraints will have its own constraint propagation function.
For the first constraint, it is quite simple: cycle through each row and column; if the number of red cells is half the puzzle size, mark all unset cells in the row or column blue, and vice versa. That's all there is to it.
For the second one, a little more care is needed. Cycle through all cells, and for each one (that is not yet set) check:
Up to now I have glossed over the actual constraint propagation. Each of the two constraints will have its own constraint propagation function.
For the first constraint, it is quite simple: cycle through each row and column; if the number of red cells is half the puzzle size, mark all unset cells in the row or column blue, and vice versa. That's all there is to it.
For the second one, a little more care is needed. Cycle through all cells, and for each one (that is not yet set) check:
- the cells one and two positions above
- the cells one and two positions below
- the cell immediately above and the cell immediately below
- the cells one and two positions to the right
- the cells one and two positions to the left
- the cell immediately to the right and the cell immediately to the left
If any of these sets has both cells set to the same colour, the current cell must be assigned the other colour. In practice a little more care is needed, as the cells close to the boundaries will not have all of the sets.
If you are wondering how to put all of this together and make it work, I have built a short Python program that implements this concept. Check it out at GitHub.
If you are looking for a way to solve the puzzles by hand, this is not your best option. Computers are terribly good at the laborious tasks of checking over and over every rule while propagating the constraints, keeping a list of the steps they take and backtracking when they reach a dead end to try a different path down the tree. We humans soon lose track of this even at small depths.
Instead, we can solve puzzles like this by latching onto more complex patterns, and thinking through the combinations that might succeed. It also works, but is much harder to automate.
Next time you want to sautomate the solution of a combinatorial problem where success is defined in terms of the rules that the solution must follow, give constraint propagation a chance. It goes much easier on your CPU than a brute force approach.
