Efficient Nonogram Solver

Question

So I recently saw this puzzle posted by the British GCHQ:

It involves solving a 25x25 nonogram:

A nonogram is picture logic puzzles in which cells in a grid must be colored or left blank according to numbers at the side of the grid to reveal a hidden picture. In this puzzle type, the numbers are a form of discrete tomography that measures how many unbroken lines of filled-in squares there are in any given row or column. For example, a clue of "4 8 3" would mean there are sets of four, eight, and three filled squares, in that order, with at least one blank square between successive groups."

Naturally I had the inclination to try and write a program that would solve it for me. I was thinking of a recursive backtracking algorithm that starts at row 0, and for each possible arrangement of that row given the information from the row clue, it places a possible combination of the next row and verifies whether it is a valid placement given the column clues. If it is, it continues, if not it backtracks, until all the rows are placed in a valid configuration, or all possible row combinations have been exhausted.

I tested it on a few 5x5 puzzles and it works perfectly. The issue is that it takes too long to compute the 25x25 GCHQ puzzle. I need ways to make this algorithm more efficient - enough so that it can solve the puzzle linked above. Any ideas?

Here is my code for generating a set of the row possibilities for each row as well as the code for the solver (Note* it uses some non standard libraries but this shouldn't detract from the point):

// The Vector<int> input is a list of the row clues eg. for row 1, input = {7,3,1,1,7}. The 
// int currentElemIndex keeps track of what block of the input clue we are dealing with i.e 
// it starts at input[0] which is the 7 sized block and for all possible places it can be 
// placed, places the next block from the clue recursively.

// The Vector<bool> rowState is the state of the row at the current time. True indicates a 
// colored in square, false indicates empty.

// The Set< Vector<bool> >& result is just the set that stores all the possible valid row 
// configurations. 

// The int startIndex and endIndex are the bounds on the start point and end point between 
// which the function will try to place the current block. The endIndex is calculated by 
// subtracting the width of the board from the sum of the remaining block sizes + number 
// of blocks remaining. Ie. if for row 1 with the input {7,3,1,1,7} we were placing the 
// first block, the endIndex would be (3+1+1+7)+4=16 because if the first block was placed
// further than this, it would be impossible for the other blocks to fit. 

// BOARD_WIDTH = 25;

// The containsPresets funtion makes sure that the row configuration is only added to the 
// result set if it contains the preset values of the puzzle (the given squares
// at the start of the puzzle).



void Nonogram::rowPossibilitiesHelper(int currentElemIndex, Vector<bool>& rowState, 
                                         Vector<int>& input, Set< Vector<bool> >& result, 
                                            int startIndex, int rowIndex) {
    if(currentElemIndex == input.size()) {         
        if(containsPresets(rowState, rowIndex)) {
            result += rowState;
        }
    } else {
        int endIndex = BOARD_WIDTH - rowSum(currentElemIndex+1, input);
        int blockSize = input[currentElemIndex];
        for(int i=startIndex; i<=endIndex-blockSize; i++) {
            for(int j=0; j<blockSize; j++) {
                rowState[i+j] = true;                                                                       // set block
            }
            rowPossibilitiesHelper(currentElemIndex+1, rowState, input, result, i+blockSize+1, rowIndex);   // explore
            for(int j=0; j<blockSize; j++) {
                rowState[i+j] = false;                                                                      // unchoose
            }
        }
    }
}


// The function is initally passed in 0 for the rowIndex. It gets a set of all possible 
// valid arrangements of the board and for each one of them, sets the board row at rowIndex
// to the current rowConfig. Is then checks if the current configuration so far is valid in 
// regards to the column clues. If it is, it solves the next row, if not, it unmarks the 
// current configuration from the board row at rowIndex.

void Nonogram::solveHelper(int rowIndex) {
    if(rowIndex == BOARD_HEIGHT) {
        printBoard();
    } else {
        for(Vector<bool> rowConfig : rowPossisbilities(rowIndex)) {
            setBoardRow(rowConfig, rowIndex);
            if(isValidConfig(rowIndex)) {                           // set row
                solveHelper(rowIndex+1);                            // explore
            }
            unsetBoardRow(rowIndex);                                // unset row
        }
    }
}

Answer 1

I've made a solution in Java, that for your example puzzle (25x25) solves it in about 50ms.

Full code and input examples: Github

---

Prerequisites

• Notions of Java (understanding the samples)
• Bitwise operations: I depend a lot on them, so read about it if you are not very familiar with it.
• Graph traversal algorithms: DFS

Given:

R, C // number of rows, columns
int[][] rows; // for each row the block size from left to right (ex: rows[2][0] = first blocksize of 3 row)
int[][] cols; // for each column the block size from top to bottom
long[] grid; // bitwise representation of the board with the initially given painted blocks

Precalculate all permutations per row.

A permutation is also stored in a bitwise representation. Where the first bit is set to true if it fill the first column etc.. This is both time and space efficient. For the calculation we first count the number of extra spaces that can be added.

This is number_of_columns - sum_of_blocksize - (number_of_blocks-1)

Dfs over all possible permutations of placing extra spaces. See calcPerms and add them to the list of possible permutations if it's a match with the initially given painted blocks.

rowPerms = new long[R][];
for(int r=0;r<R;r++){
    LinkedList<Long> res = new LinkedList<Long>();
    int spaces = C - (rows[r].length-1);
    for(int i=0;i<rows[r].length;i++){
        spaces -= rows[r][i];
    }
    calcPerms(r, 0, spaces, 0, 0,res);
    rowPerms[r] = new long[res.size()];
    while(!res.isEmpty()){
        rowPerms[r][res.size()-1]=res.pollLast();
    }
}
...

// row, current block in row, extra spaces left to add, current permutation, current number of bits to shift
static void calcPerms(int r, int cur, int spaces, long perm, int shift, LinkedList<Long> res){
    if(cur == rows[r].length){
        if((grid[r]&perm)==grid[r]){
            res.add(perm);                
        }
        return;
    }
    while(spaces>=0){
        calcPerms(r, cur+1, spaces, perm|(bits(rows[r][cur])<<shift), shift+rows[r][cur]+1,res);
        shift++;
        spaces--;
    }
}
static long bits(int b){
    return (1L<<b)-1; // 1 => 1, 2 => 11, 3 => 111, ...
}

Implement validations per row

• Validating the rows:

[Trivial:] We are going to use precalculated permutations so we don't need any extra validation per row.

• Validating the columns:

Herefor I'm keeping for each row and column the index of the current blocksize colIx, and the position in that size colVal.

This is calculated by the value and index of the previous row:

• The value increased by 1 if the column is painted in the current row.
• the value reset to 0 and index increased by 1 if the column was painted in the previous row and is not in the current row.

Sample:

static void updateCols(int row){
    long ixc = 1L;
    for(int c=0;c<C;c++,ixc<<=1){
        // copy from previous
        colVal[row][c]=row==0 ? 0 : colVal[row-1][c];
        colIx[row][c]=row==0 ? 0 : colIx[row-1][c];
        if((grid[row]&ixc)==0){
            if(row > 0 && colVal[row-1][c] > 0){ 
                // bit not set and col is not empty at previous row => close blocksize
                colVal[row][c]=0;
                colIx[row][c]++;
            }
        }else{
            colVal[row][c]++; // increase value for set bit
        }
    }
}

Now we can use these index/values to determine which bits are expected to be false/true in the next row.

Used datastructure for validation:

static long[] mask; // per row bitmask, bit is set to true if the bit has to be validated by the val bitmask
static long[] val; // per row bitmask with bit set to false/true for as expected for the current row

When bit in previous row is set, we expect the bit in current row to be set to true if and only if the current size is still smaller than the expected size for the current index. Else it has to be 0 because you want to cut it off at the current row.

Or when the last blocksize is already used for the column we can not start a new block. Hence bit has to be 0.

static void rowMask(int row){
    mask[row]=val[row]=0;
    if(row==0){
        return;
    }
    long ixc=1L;
    for(int c=0;c<C;c++,ixc<<=1){
        if(colVal[row-1][c] > 0){
            // when column at previous row is set, we know for sure what has to be the next bit according to the current size and the expected size
            mask[row] |= ixc; 
            if(cols[c][colIx[row-1][c]] > colVal[row-1][c]){
                val[row] |= ixc; // must set
            }
        }else if(colVal[row-1][c] == 0 && colIx[row-1][c]==cols[c].length){
            // can not add anymore since out of indices
            mask[row] |= ixc;
        }
    }
}

Dfs all rows and check if still valid

This makes the actual dfs part as easy as your own. If the rowmask fits with the current configuration we can update the column indices/values and traverse to the next row and eventually end up at row R.

static boolean dfs(int row){
    if(row==R){
        return true;
    }
    rowMask(row); // calculate mask to stay valid in the next row
    for(int i=0;i<rowPerms[row].length;i++){
        if((rowPerms[row][i]&mask[row])!=val[row]){
            continue;
        }
        grid[row] = rowPerms[row][i];
        updateCols(row);
        if(dfs(row+1)){
            return true;
        }
    }
    return false;
}