Nonolog, Prolog Solver

◷ 15 min read

✏ published 2021-06-28

Jack Leightcap

Contents

- Background

- Abstract

- Prolog Motivation: Relations and Queries

- Run-Length Encoding, Decoding Relations

- Combining Encodings

- Combined Encodings, Resulting Encoding and Decoding

- Nonogram Relations

- Leveraging Constraints for Free Features

- Reflection on Prolog

Background

Previously, I had written a program to solve Nonograms (more commonly known in the US as Picross) by leveraging a SAT solver. This lead to a functional, but fairly uninspiring, algorithm that converts a description of a Nonogram puzzle into an equivalent SAT problem.

In this post I'll walk through a much more elegant (and insightful) solution using the logic programming language Prolog, which is a much more natural environment to frame this problem. In doing so, I'll also walk through a more general approach to incrementally writing Prolog programs.

Abstract

To not bury the lead, what will the end result actually look like? Take for example the reasonably complex 5×5 puzzle

     11 3
     22112
    +-----+
  2 |     |
2 2 |     |
  1 |     |
  3 |     |
2 1 |     |
    +-----+

loading the final program into a prolog repl, and inputting the row and column restrictions, respectively:

; swipl
?- [nono].
true.
?- picross([[2], [2, 2], [1], [3], [2, 1]], [[1, 2], [1, 2], [1], [3, 1], [2]], 5, X).
00011
11011
00010
11100
11010
X = [[0, 0, 0, 1, 1], [1, 1, 0, 1, 1], [0, 0, 0, 1, 0], [1, 1, 1, 0, 0], [1, 1, 0, 1|...]] .

this is the solution,

     11 3
     22112
    +-----+
  2 |   XX|
2 2 |XX XX|
  1 |   X |
  3 |XXX  |
2 1 |XX X |
    +-----+

Prolog Motivation: Relations and Queries

The first consideration in order to effectively represent the puzzle is to convert the idea of these individual restrictions. Consider the last row, "(2 1) with length 5" — there are multiple ways this could be satisfied on its own, "(2,1) in the space of 5" could generate |XX-X-| or |-XX-X| or |XX--X|.

an encoding f for this input would produce the set

f([2 1], 5) -> { |XX-X-|, |-XX-X|, |XX--X| }

using Prolog, there's not the usual notion of a function, but instead a relation. We can declare this example as relations,

decode(5, [2, 1], [1, 1, 0, 1, 0]).
decode(5, [2, 1], [1, 1, 0, 0, 1]).
decode(5, [2, 1], [0, 1, 1, 0, 1]).

here, a relation without a body is more specifically called a fact. A query over these facts, effectively asking "what state X satisfies the constraints of restriction (2, 1) in length 5?"

?- decode(5, [2, 1], X).
X = [1, 1, 0, 1, 0] ;
X = [1, 1, 0, 0, 1] ;
X = [0, 1, 1, 0, 1] ;
false.

The ; after each answer requests another satisfying X, and the final false. indicates that all X within the given constraints were generated. However, as you might notice from the syntax of these queries, queries don't have a defined notion of an input or output. We could have just as reasonably asked "what restriction R satisfies the state (1,1,0,1,0) for length 5?"

?- decode(5, R, [1,1,0,1,0]).
R = [2, 1] ;
false.

or "what size N satisfies the constraints of restriction (2, 1) with state (1,0,1,1,0)?"

?- decode(N, [2, 1], [1,1,0,1,0]).
N = 5 ;
false.

This higher-order notion of a query, even coming from some background in functional programming, totally blew my mind. Because of these "free features", we can just as effectively express the constraints required for encoding as we can for decoding — inverses come along for the ride.

Run-Length Encoding, Decoding Relations

We'll now write some relations that define how puzzles treat run-length encodings. Using the Prolog repl means that a final solution can iteratively be built out of simpler examples, then abstracted into a very elegant final expression. With the above examples for decoding, an encoding fact might look like

encode([0,1,1,0,1,0,0,1,0], [2,1,1]).

with this, there's some fairly intuitive base cases, here with a body, known as a clause:

encode([], X) :- X = [].
encode([0], X) :- X = [].
encode([1], X) :- X = [1].

let's iteratively build up to a recursive solution that can use these base cases to bottom out. What information is needed from the list to be encoded? Well, the given base cases are exhaustive over lists of length at most 1. And there needs to be one element of look-ahead for determining if there is a gap in between blocks. So the list to be encoded needs to broken down into its first, second, and rest; which is easy enough with pattern matching:

% run-length encoding of a 1's in a given binary list.
%   input list :: list[{0,1}],
%   resulting encoding
encode([F,S|R], X) :-
    encode([S|R], X2),
    add_encode(F, S, X2, X).

Effectively, recursively encode all but the first element of the list (the second element, and the rest which may be empty, [S|R]) with encoding X2. Then, constrain that resulting encoding X2 based on the first element of the list F. We're totally punting on a lot of complexity here by just declaring add_encode out of nowhere, but this is the general structure I'm going for.

Assuming encode works, decoding can be written as a relation on encodings,

% decode, inverse of encoding with constrained length.
%   length :: Nat,
%   restriction list :: list[Nat],
%   possible decodings of length
decode(N, E, X) :-
    length(X, N),
    encode(X, E).

Combining Encodings

So now the problem is deferred to combining encodings with a new value. Examining the base cases demonstrates the need for one element of lookahead,

% resulting encoding from previous encoding, with one element of lookahead
%   cell :: {0,1},
%   previous :: {0,1},
%   accumulator encoding :: list[Nat],
%   effective encoding
add_encode(1, 1, [], X) :- X = [2]. % two adjacent 1s combine to an encoding of 2
add_encode(1, 0, [], X) :- X = [1]. % lone 1 encodes as 1
add_encode(0, _, S, X) :- X = S.    % if the new element is 0, the accumulated encoding is unchanged.

the more involved cases when combining any new value based on an arbitrary accumulated encoding,

% new element 1, previous element 0. prepend 1 to accumulated encoding
add_encode(1, 0, S, X) :- X = [1|S].

% new element 1, previous element 1. increment the head of the accumulated encoding
add_encode(1, 1, S, X) :-
    X = [A|R], % new binding first value of X,
    [F|R] = S, % bind 'F' to head of X,
    A is F+1.  % increment value of head

testing with a few examples confirms this works as expected,

% new element is 1, previous element was 1, the restriction so far is [1, 2, 3].
?- add_encode(1, 1, [1, 2, 3], X).
X = [2, 2, 3].

% same case, but the previous element was 0.
?- add_encode(1, 0, [1, 2, 3], X).
X = [1, 1, 2, 3].

% if the new element is 0, encoding is effecitvely the same
?- add_encode(0, 1, [1, 3, 4], X).
X = [1, 3, 4].

note that while there is no type annotations to provide type-safety, the relations only pattern match over elements {0,1}, which provides some sanity checking.

Combined Encodings, Resulting Encoding and Decoding

Now all the pieces are in place, and we can test the overall pipeline. Recall that the primary goal that kicked off this sequence was to take a restriction (like [1 2]) and a length (like 5) and generate (decode) all possible encodings that satisfy those constraints. Using Prolog's notion of a relation, we expressed decoding in terms of encoding, then wrote a helper relation that allowed for a recursive definition of encoding.

In total now, we can test everything out:

?- decode(5, [1, 2], X).
X = [1, 0, 1, 1, 0] ;
X = [1, 0, 0, 1, 1] ;
X = [0, 1, 0, 1, 1] ;
false.

which confirms the example given earlier.

Nonogram Relations

Nearly there. Lastly, we want a way of constraining multiple restrictions — for both rows and columns — to an entire board state. For simplicity, we'll be assuming square puzzles as that is by far the most common variant and significantly reduces complexity here. Starting with a relation just encoding invariants on the arguments,

% constrain a picross puzzle.
%   row restraints :: list[list[Nat]],
%   column restraints :: list[list[Nat]],
%   length :: Nat,
%   solved picross
picross(Rc, Cc, N, X) :-
    length(Rc, N),
    length(Cc, N),
    % ... TODO

this will just bail out if there is not a restriction for every row and column, or if there is not the same number of rows as columns. Next, we map the decode relation over the list of restraints for the given length, which should feel familiar to any functional programmer;

    % ...
    maplist(decode(N), Rc, X),
    maplist(decode(N), Rc, X2),
    % ... TODO

note the partial evaluation of the 3-input decode(N,E,X) where decode(N) evaluates to anonymous function of the 2 variables.

X and X2 now are constrained to be valid states of each row, and each slice, respectively. Last but not least, the enforcement of a square puzzle just means to relate these to constraints:

    % ...
    transpose(X2, X).

that's... actually it! Testing it out,

?- picross([[2], [2, 2], [1], [3], [2, 1]], [[1, 2], [1, 2], [1], [3, 1], [2]], 5, X).
00011
11011
00010
11100
11010

     11 3
     22112
    +-----+
  2 |   XX|
2 2 |XX XX|
  1 |   X |
  3 |XXX  |
2 1 |XX X |
    +-----+

just like stated at the beginning.

Leveraging Constraints for Free Features

Picross puzzles do not have to have a unique solution.

   221
  +---+
1 |   |
2 |   |
2 |   |
  +---+

this puzzles does not uniquely constrain the board to one state; do you think this Prolog implementation will handle that?

?- picross([[1], [2], [2]], [[2], [2], [1]], 3, X).
100
110
011
X = [[1, 0, 0], [1, 1, 0], [0, 1, 1]] ;
001
110
110
X = [[0, 0, 1], [1, 1, 0], [1, 1, 0]] ;

like when querying over a set of facts, when querying over the relations that define a puzzle, here Prolog exhaustively finds every state that is bounded by the given constraints;

   221       221
  +---+     +---+
1 |X  |   1 |  X|
2 |XX |   2 |XX |
2 | XX|   2 |XX |
  +---+     +---+

Similarly, what if we ask Prolog to search in the opposite direction, generating restraints for a given state? If we had a puzzle but were too lazy to count,

+---+
|XXX|
| X |
|X X|
+---+

?- picross(X, Y, 3, [[1, 1, 1], [0, 1, 0], [1, 0, 1]]).
111
010
101
X = [[3], [1], [1, 1]],
Y = [[1, 1], [2], [1, 1]] ;

which are indeed the constraints to encode this puzzle.

Reflection on Prolog

This was my first expose to Prolog. Prolog rocks; previously I thought of programming as purely "additive" form, that is you take some base materials and compose them up to a more complex result. In contrast, Prolog feels "subtractive"; where you chisel your problem out of a blank slate of "everything" down to the final result.

The final implementation can be found here.