Griddlers Solver

You know these griddlers puzzles? Every day there is a new 2D 20x20 puzzle in the newspaper we were getting at work. So I decided to implement a solver for those problems.
Before I start talking, you can take a look at the Griddler Solver page. I have prepared some examples.

I chose client-side JavaScript as the runtime environment. Why? just because it's easy to use for coding the solver and it also integrates smoothly with a well known UI - HTML... Oh, and because I wanted to practice my JavaScript skills...
My first attempt with implementing the solver was using kind of DFS (Depth-First-Search). The algorithm was (roughly):

1. Calculate possible solutions for each column
2. Iterate recursively over the columns:
1. Get the current column
2. Iterate recursively over the possible solutions of the column:
1. Get the current possible solution
2. If this is the last column:
1. If the problem is solved (the rows constraints are matched) - stop

This worked great for small problems (about 5x5), but for bigger problems the performance was horrible.
The next step I tried was to add some heuristics. For example, I added some heuristics for pruning branches which are not feasible. Some of the rules I used:

• If the sum of colored cells in a row of the solution is higher than the some of colored cells in the constraint - this branch is not feasible
• If the length of the current block is higher than its expected length - this branch is not feasible

With those rules the performance improved tremendously, but still not enough for the average problem (20x20). 

Then I decided to change direction and instead of implementing based on a generic algorithm (i.e. DFS), I decided to implement an algorithm which is based on the way a human will solve it. So, how do you solve these puzzles? I usually use an iterative solution:

1. Find the large blocks and find overlaps - color them.
2. Check for other constraints which are now easier to match, according to the new colored cells.
3. If there is no single solution - find the minimal possible solutions, select one and try to move forward. If this fails, go back and select a different possible solution. (This step usually does not happen - you usually just need to look harder in steps #1 & #2).

What I have decided to implement was some variation of it. I decided to calculate all the possible solutions for all rows and columns and then do cross-checks for each cell and calculate its probability to be colored. In each step some possible solutions can be discarded since they do not match the decisions that were made during that step.

So the algorithm is basically:

1. Initialize:
1. Calculate all possible solutions for each row & column
2. Initialize the grid so that each cell has an undefined value
2. Solve - while the solution changes:
1. Update probabilities:
   For each cell, calculate the probability for it to be colored by cross checking the possible solutions for both row and column - count the number of solutions where the cell is colored and not colored.
2. Remove false solutions:
   For each cell, if the cell's value is known (i.e. 100% colored or empty) - remove all possible solution (columns and rows) where the cell's value is different from its expected value.

You can see above that I don't yet handle the case when there are multiple possible solutions which none of them can be removed - i.e. need to choose one of them and try to move forward. This is because I did not have such a case yet in any of the puzzles I tried. It's not that difficult to create such example, nor implement it, I just didn't... (for example: 2x2 puzzle with rows - [ [1], [1] ] , and columns - [ [1], [1] ]. Try it...).

In my implementation I implemented the solver as an Iterator which enabled me to add animation to the UI. Since in each step the grid has probabilities for each cell (for whether it is colored), it can make quite nice animations.

You can find the code in my GitHub project yinonavraham/GriddlerSolverJS.