Nonogram puzzle solution space
There are no docstrings. What do these functions do? Lack of docstrings make the code hard to review, because we don't know what the functions are supposed to do.
The call indices(n) generates the Cartesian product of range(n) × range(n) in a particular order. A natural question is, does the order matter, or could we use itertools.product instead:

itertools.product(range(width), repeat=2)


The post explains why you've chosen the order. But how is someone reading the code supposed to know that? There needs to be a comment.
encode could be simplified to avoid the if:

sum(bit&lt;&lt;i for i, bit in enumerate(...))

This code:

for matrix in product((False, True), repeat=width**2):
    candidate = list(zip(*[iter(matrix)]*width))


is effectively the same as:

sol_matrices = (list(zip(*[iter(matrix)]*width)) for matrix
                in product((False, True), repeat=width**2))


and so would benefit from having its own function (which would have a name and docstring that would explain what it does).
The algorithm takes every nonogram puzzle, and then compares the run counts with the run counts for every nonogram puzzle of the same size. If width is \$ n \$, there are \$ 2^{n^2} \$ nonogram puzzles, and it takes \$ Ω(n^2) \$ to compute the run counts for a single puzzle, so the overall runtime is the ludicrous \$ Ω(n^24^{n^2}) \$.

This could be brought down to \$ Ω(n^22^{n^2}) \$ if you prepared a dictionary mapping run counts to sets of encoded nonogram solutions, and down to \$ Ω(n2^{n^2}) \$ if you prepared the list of all rows, prepared a dictionary mapping each row to its run counts, and then generated the puzzles and their run counts simultaneously using the Cartesian product of the rows.