Generating Binary Puzzles

A few years ago, I got a book called "875 Binary Puzzles". In it, there are various grids with zeros, ones, and empty spaces, and you're supposed to figure out the missing values.

The rules are simple:

1. There must be the same number of zeros and ones in a given row and column.
2. You can't have more than two consecutive values the same in a row or column.
3. You can't have duplicate rows, and you can't have duplicate columns.

Here's a trivial example:

0 1 1 x
1 x 1 0
0 1 0 1
1 x x 1        

The "x" represents the part that you're supposed to fill in. The first row is easy -- since there must be the same number of zeros and ones, and there is 1 zero and 2 ones, the top right "x" must therefore be a zero:

0 1 1 0
1 x 1 0
0 1 0 1
1 x x 1        

Similarly for the second row, that "x" must be a zero (for two reasons: we've already used up all the ones, and because you can't have more than two of the same value in a sequences, so we couldn't have three ones in a row):

0 1 1 0
1 0 1 0
0 1 0 1
1 x x 1        

The last row already has two ones, so the two "x" values must both be zero. Thus the solution is:

0 1 1 0
1 0 1 0
0 1 0 1
1 0 0 1        

All the rows are unique (0110, 1010, 0101, and 1001) and all the columns are unique (0101, 1010, 1100, 0011).

Generating

Obviously, I'd like to generate these puzzles. Perhaps I'd like to pop up an interactive game and you could move the cursor or mouse and solve the puzzle.

Generating trivial 4 x 4 puzzles is simple, and takes no time at all.

When I first started this project last week, generating 8 x 8 puzzles took a little bit of time, 12 x 12 took a lot of time, and you'd be lucky to get a 20 x 20 puzzle generated.

Today, I just generated a 60 x 60 in 14 seconds (sadly, I cannot generate arbitrary 60 x 60 puzzles in 14 seconds, this one just happened to get all the right random numbers to make it computationally feasible).

How did I achieve the speedup?

At the heart of the puzzle generator is a recursive algorithm. I start with an empty board, and choose a zero or one, at random, as the value of the next unoccupied square. If I haven't violated any rules (for example, selecting another one when I already had 2 ones in a row), I instantiate a new board and repeat the process recursively.

Simply choosing values at random, however, takes forever. An early optimization I did was to introduce what I called a "forward solver." What it does is looks at the current board, and tries to solve it. For example, if it sees two sequential ones in a row or column, it knows that the next value must be zero (assuming a zero is available).

This lead to a significant speedup, because there were fewer possibilities to investigate.

Next, I introduced "negative logic". Consider this board:

1 x Y x x x
x 0 x x x x
x x x 0 1 0
x x 1 x x x
x x 0 1 x x
1 x 0 x 0 x        

Look at the blank spot that I labelled "Y". The only way I can determine its value is by what it cannot be -- hence the term negative logic. Can it be a one? Sure, it could be a one. Ok, but can it be a zero? No, it cannot be a zero.

Why can't it be zero? Because if it was a zero, then that column would have three zeros, which means that the two "x" values under the "Y" would have to be ones, which means you'd now have:

1 x 0 x x x
x 0 1 x x x
x x 1 0 1 0
x x 1 x x x
x x 0 1 x x
1 x 0 x 0 x        

and you're not allowed having more than two consecutive values the same in a row or column; here we'd have three consecutive ones in a column.

So therefore, it can't be a zero -- and since this is a binary puzzle, that means that it must be a one (there's no other choice):

1 x 1 x x x
x 0 x x x x
x x x 0 1 0
x x 1 x x x
x x 0 1 x x
1 x 0 x 0 x        

The rest of the puzzle is readily solvable:

1 0 1 0 1 0
0 0 1 1 0 1
1 1 0 0 1 0
0 0 1 0 1 1
0 1 0 1 0 1
1 1 0 1 0 0        

Adding negative logic to the forward solver made it even faster.

Generating Symmetry

I had a feeling that there's a much simpler way to generate large boards, but just wasn't getting it. The insight I had was when I tried to generate a board "by hand" in the editor. I thought, "wouldn't it be simpler to just make it symmetrical?" That is, the values at (x, y) are the same as the values at (y, x). Turns out that was a the trick! (That, and fixing a forward resolver bug). Now I can generate 120 x 120 symmetrical boards in tens of seconds. Sometimes it goes down a rat-hole and the recursive algo has to back out and retry a bunch, so boards that can't be generated within some time period are aborted, and the operation is retried. Here's an example of a symmetrical board:

    0 1 2 3 4 5 6 7 
    - - - - - - - - 
0 | 1 1 0 1 0 1 0 0 
1 | 1 0 1 1 0 0 1 0 
2 | 0 1 0 0 1 1 0 1 
3 | 1 1 0 0 1 1 0 0 
4 | 0 0 1 1 0 0 1 1 
5 | 1 0 1 1 0 1 0 0 
6 | 0 1 0 0 1 0 1 1 
7 | 0 0 1 0 1 0 1 1 

15 steps required        

This puzzle was generated in 15 steps, where a step is a placement of a value. Whether that placement ultimately works or not doesn't matter -- placing a value increments the step count. Values placed by the forward solver do not count as steps. So, in the above, out of the possible 64 locations, the recursive algorithm placed 15 of them (which, due to symmetry, may have ended up putting values into up to 30 locations). The rest were placed by the forward solver.

Notice the symmetry -- the first row reads 11010100 as does the first column. The second row reads 10110010 as does the second column, and so on.

Perturbations

Solving symmetrical binary puzzles would be less challenging than solving asymmetrical ones, since you're really just solving (at most) half the board. For example, once you know the value at row 2 column 6, you also know the value at row 6 column 2.

The next step, therefore, is to perturb the board -- flipping an arbitrary value from a zero to a one or vice versa is the seed for the perturbation. Once that happens, though, you end up with an invalid board. Here we've flipped (2,3):

    0 1 2 3 4 5 6 7 
    - - - - - - - - 
0 | 1 1 0 1 0 1 0 0 
1 | 1 0 1 1 0 0 1 0 
2 | 0 1 0 1 1 1 0 1 
3 | 1 1 0 0 1 1 0 0 
4 | 0 0 1 1 0 0 1 1 
5 | 1 0 1 1 0 1 0 0 
6 | 0 1 0 0 1 0 1 1 
7 | 0 0 1 0 1 0 1 1         

Notice now that there are rule violations:

1. The number of ones in column 3 (and row 2) is 5 and the number of zeros is 3; they are not matched
2. There are three ones in a row in column 3 (and row 2)

The simplest way around the rule violations is to (a) only perturb values that can be perturbed (that is, you can't change 0 1 0 to 0 0 0, nor can you change 1 1 0 to 1 1 1, and so on), and (b) make the perturbations self correcting -- that is, instead of only flipping one bit, you also flip a complementary (perturbable) bit in the same row.

At this point, you have a balanced row, but the two columns involved are wrong. The fix is straightforward: flip two complementary perturbable bits in those columns (in a different row of course).

Mission Accomplished

Using the above approach, I can now generate a 200x200 in 27 seconds, and a moderately large 400x400 in 7 minutes and 17 seconds. There are probably more optimizations to be had, but ... bored now :-)

Summary

I went from barely being able to generate 16 x 16 puzzles using the "obvious" recursive approach to many orders of magnitude speedups (to say nothing of memory usage optimization along the way).