17. Nonogram

This chapter shows how to use regular expressions and extensional constraints for solving nonogram puzzles.

17.1. Problem

Nonograms ( CSPLib problem 12 ) are popular puzzles in which the puzzler shades squares in a matrix. Each instance of the puzzle has constraints on the rows and columns of the matrix, specifying the number and length of the groups of consecutive marks in that row or column. For example, a row that in the solution has the marks

\[\square\square\blacksquare\blacksquare\square\square\blacksquare\blacksquare\blacksquare\square\blacksquare\square\square\square \]

has the hint 2 3 1, indicating that there are three separate groups of marks, with lengths 2, 3, and 1. Given two groups of marks, there must be at least one empty square in between. An example nonogram is given in Figure 17.1 and its solution is shown in Figure 17.2 . The general nonogram problem is NP-complete, as shown in [61] .

Example nonogram puzzle

Figure 17.1 Example nonogram puzzle

Solution to the example puzzle

Figure 17.2 Solution to the example puzzle

17.2. Model

The model follows naturally from the constraints of the problem. The variables needed are a matrix \(x_{ij}\) of 0-1 variables, representing the squares to shade. For the hint 2 3 1 on row \(i\), we post the following extensional constraint (see Extensional constraints ):

\[\mathtt{extensional}(x_{i\bullet}, 0^*1^20^+1^30^+10^*) \]

The regular expression starts and ends with zero or more zeroes. Each group is represented by as many ones as the group length. In between the groups, one or more zeroes are placed. Using this construction, we get one constraint per row and column of the matrix. The outline of the script is shown in A script for solving nonogram puzzles .

Program 17.1 A script for solving nonogram puzzles
...
// [nonogram:puzzle]
class Nonogram : public Script {
  int width, height;
  BoolVarArray b;

  DFA line(const int*& p) {
    // [nonogram:line function]
  }
public:
  Nonogram(const Options& opt)
    : Script(opt), width(spec[0]), height(spec[1]),
      b(*this,width*height,0,1) {
    Matrix<BoolVarArray> m(b, width, height);
    // [nonogram:intialize hint pointer]
    // [nonogram:column constraints]
    // [nonogram:row constraints]
    // [nonogram:branching]
  }
  ...
};

int main(int argc, char* argv[]) {
  ...
}

Download: nonogram.cpp

17.2.1. Puzzle specification.

The puzzle is specified by an array of integers. The first two integers specify the width and the height of the grid. These are followed first by the column and then the row hints. Each hint specifies the number of groups and the length of each group. For example, the hint used as an example above is specified as 3, 2, 3, 1. The puzzle from Figure 17.1 is written as follows.

const int spec[] =
  { 9, 9,
    // Column hints
    1, 3,
    2, 2, 3,
    ...
    // Row hints
    2, 2, 2,
    ...
  };

17.2.2. Line function.

For the hint that starts at p (that is, p points to a position in the array of integers spec[] where a hint starts), the following code constructs a regular expression (see Regular expressions for extensional constraints ) that matches that hint.

    int nhints = *p++;
    REG r0(0), r1(1);
    REG border = *r0;
    REG separator = +r0;
    REG result = border;
    if (nhints > 0) {
      result += r1(*p,*p);
      p++;
      for (int i=nhints-1; i--; p++)
        result += separator + r1(*p,*p);
    }
    return result + border;

The variables r0 and r1 represent the constants 0 and 1 (this is a slight optimization to construct a regular expression for the constants 0 and 1 just once). The variables border and separator represent sequences of zeroes at the borders and between marks. The loop adds all hints (as repeated r1s) to the result expression with separators in between. Note that if the hint is just 0 (representing an empty line with no mark), then the result will be just the same as a border+border, which is \(\mathtt{0}^*\mathtt{0}^*=\mathtt{0}^*\).

17.2.3. Constraints.

Given the line() function, posting the appropriate constraints is as follows. The pointer p is initialized to point to the first hint:

    const int* p = spec+2;

Two loops go through all the hints, get the regular expression for the line, and post the constraints for the appropriate variables. First, the column constraints are posted:

    for (int w=0; w<width; w++)
      extensional(*this, m.col(w), line(p));

followed by the row constraints:

    for (int h=0; h<height; h++)
      extensional(*this, m.row(h), line(p));

17.2.4. Branching.

Choosing a branching for nonograms is not obvious. For many nonogram puzzles, using an AFC-based branching (see Branching on integer and Boolean variables ) is a good idea:

    branch(*this, b, BOOL_VAR_AFC_MAX(), BOOL_VAL_MAX());

The choice to use INT_VAL_MAX() is because most puzzles will have fewer marks than empty spaces. For the example puzzle from Figure 17.1 , propagation alone solves the puzzle. To solve really hard puzzles, a custom branching may be needed.

17.3. More information

The nonogram puzzle is also included as a Gecode example, see nonogram . The example in particular features several grids to try the model on.

Despite its simplicity, the program for solving nonograms works amazingly well. Extensive information on nonogram puzzles and a comparison of different nonogram solvers (including the model described in this chapter) is Survey of Paint-by-Number Puzzle Solvers .