Picross solving: matching checked cells to their clues

Question

I am writing a picross solver, and I am going with the "human logic" solving, which attempts to reproduce the reasoning a human might have when confronted to such a puzzle, in an iterative manner.
Having solved a lot of those by hand, I found the human logic to be very algorithmic-ish given how the same kind of reasoning takes place in most situations (which is also what motivated me in writing a solver).
However, I am encountering problems when trying to formalize some of that logic.

What is picross

Also called nonograms, they are puzzles consisting of an empty grid with clues on the top and left borders:

The clues indicate the length of groups of consecutive cells that need to be checked, and groups must be separated by at least one empty (unchecked) cell. Clues are ordered.
For example, clues 7 2 in the first row indicate that the following must take place somewhere in that row:

• 7 consecutive cells must be checked
• at least one cell must be left empty after that 7-long sequence
• another 2 consecutive cells must be checked after the empty cell(s)

Here is what the solved grid looks like:

In order to help in the process of solving, it is also possible to cross cells to indicate that they cannot be checked, as in they must remain empty for sure.

Trivial solving

The easiest part of the solving is filling the empty grid with what you can deduce from the clues alone in each row and column. In that regard, some clues are nice, and some clues are not so nice.
For example, given that the previous grid is 10 cells wide, and that clues 7 2 fit in exactly 10 cells (7 checks + 1 space + 2 checks), there is only one possible solution for the first row.
However, by looking at the second row and its clue 6, you will only be able to find that only cells at columns 5 and 6 can be checked with certainty:

|■|■|■|■|■|■| | | | |     1. Check the 6 leftmost cells
          ↓
| | | | |■|■|■|■|■|■|     2. Slide the group all the way to the right
          ↓
| | | | |■|■| | | | |     3. Keep cells that are *always* checked during the sliding

You can generalize this reasoning to a group of several clues by calculating the minimum space in which they fit, computing the difference with the actual available space and checking cells at only certain indices depending on those two numbers.
As mentioned, this is the easy part, because it only depend on the clues. It assumes the row or column is empty and thus it doesn't take its state into account.

Further (iterative) solving

From that point onwards, several other pieces of reasoning can be performed in a loop on each row and column, and that will be sufficient to solve the entire grid in most cases. This paper, from section 2.2.2 (p. 16), identifies all such techniques. There is one problem however: these reasonings take into account the current state of a row or column, they build upon it. What that means is that in order for most of those to be carried out, they need to know which group of checked cells may correspond to which clue.

For example, considering the following row (10-wide with clues 3 4):

3 4║ | | | | |■| | |■| ║

an algorithm identifying which cell may belong to which clue would tell me the following:
both cells 6 and 9 belong to clue 4
Reason: if cell 6 belonged to clue 3, a group satisfying clue 4 would not fit in the row (at least while being properly separated by an empty cell, as required). Cell 9 cannot belong to clue 3 for the same reason, as well as because cell 6 is located before and was found to exclusively belong to clue 4, which is after clue 3.

For the following row:

3 4║ | | |■|■| |■| | | ║

the algorithm would tell me:
cells 4 and 5 belong to clue 3, and cell 7 belongs to clue 4
Reason: if cells 4 and 5 belonged to clue 4, a group satisfying clue 3 would not fit in the row. In the same way, there would not be enough space to satisfy clue 4 if cell 7 belonged to clue 3.

Finally, for the following row:

3 4║ | | | |■| |■| | | ║

the algorithm would tell me: cell 5 belongs to either clue 3 or clue 4, but cell 7 belongs to clue 4 for sure
Reason:

• if cell 5 belongs to clue 3, there is still enough space for both a group of three ending at cell 5 and a group of four beginning at cell 7. Cell 5 may belong to clue 3.
• if cell 5 belongs to clue 4, there is still enough space for both a group of three starting at cell 1 and a group of four starting at cell 5. Cell 5 may belong to clue 4.
• if cell 7 belongs to clue 4, there is plenty of space for both groups required by clues. Cell 7 may belong to clue 4.
• if cell 7, however, belonged to clue 3, there would not be enough space for a group satisfying clue 4 afterwards. Cell 7 may not belong to clue 3.

And this is exactly that algorithm which I'm having trouble writing down.
It also turns out I was able to come up with a solution while writing this question. See my (rather long) self-answer below.

Answer 1

Long answer warning!!!

So here is the approach I've taken to come up with this algorithm:

• We are trying to pair checked cells with potential clues they may belong to, so iterating on both of those would be a good start.
• Given a cell at index i and a clue at index n, cell i may only belong to clue n iff:
  • there is enough space before cell i for groups which satisfy all clues at index < n; and
  • there is enough space after cell i for groups which satisfy all clues at index > n
  • Note: a group of checked cells satisfying clue n will always fit without overlapping with the spaces needed by other clues. Otherwise, it means the clues are ill-formed, which is out of the question here.

---

• Problem: this doesn't take into account the fact that a cell may be part of a group of checked consecutive cells. In such a case, with just the above, it is possible that checked cell i is detected as belonging to clue n, but checked cell i+1 is detected as not belonging to clue n, which doesn't make sense. Consider the following row:
  2 3║ | | | | |■|■| | | ║
  Here, cell 6 will be detected as possibly belonging to both clues 2 and 3, but cell 7 will be detected as belonging exclusively to clue 3. It is obvious that such a case doesn't make sense, and the answer is that both cells cannot belong to clue 2, only to clue 3.
  • Solution: let "group i" be the group of checked consecutive cells that cell i is part of. Cell i may belong to clue n iff the left and right boundaries of group i do not overlap with the spaces needed by other clues, as computed above.

---

• Problem: this fails to take into account crossed cells (telling this cell cannot be checked), which could "break up" the space available for a group statisfying clue n, potentially making cell i an invalid match for clue n. Consider the following row:
  4 3║ | | |■|×|■| | | | ║
  Here, both checked cells will be detected as belonging to clue 4. Indeed, if there weren't a cross inbetween them, those two cells could form a group of 4 and there would still be enough space left for a group of 3 afterwards. However, there is a crossed cell between them, telling us this is not possible.
  • Solution: find the position of the closest crosses both left and right of cell i (if any). Cell i belongs to clue n iff, given a group of checked cells which satisfies clue n and includes cell i:
    • that group can fit between the two bounding crossed cells that were found (if any); and
    • that group can still not overlap the spaces needed by other clues, as computed above.
  • Note: the last condition above is now a required check because, as seen above, a crossed cell may restrict the possible positions for the entire group, which as a result could inevitably overlap with the spaces needed by other clues, thus making cell i an invalid match for clue n. Continuing the example given above: cell 6 cannot belong to clue 4, as it would need to form a group of 4 that would overlap with the space needed by a group of 3 placed afterwards (as required by clue 3).

---

• Problem: this fails to detect the presence of some discriminative checked cells. Consider the following row:
  3 3║ | |■| |■|■| | | | ║
  With just the above, the output will be that all three checked cells may belong to both clues. While the "may" part of the statement makes it not wrong, it would be naive to come to such a conclusion. It is obviously apparent that if the empty space in cell 4 was checked, there would be a group of 4, which by the clues of the row is invalid. Therefore it can be crossed, and cell 3 belongs to the first clue, while cells 5 and 6 belong to the second clue.
  • Solution: This requirement is out of scope for the algorithm currently being designed. In order for this specific requirement to be fulfilled, we basically insert an imaginary cross in cell 4 and ask the algorithm to behave as if it was there. However, if we inferred its presence, then it is not imaginary anymore, it must be there! This is part of solving the grid, adding information to the row, not extracting already existing information. See section 2.2.5 (p. 17) of the linked paper, "Joining and splitting".
    So this is basically a non-issue, but I thought I'd include it here as it was part of my thought process at some point, and it also constitutes a valid point to raise.

---

• A free improvement: the algorithm we've got so far does an okay job. It assumes that any checked cell can belong to any clue, and performs a series of simple checks on each cell and each clue to validate whether this can actually hold true. If a checked cell is marked as belonging to several clues, we can't tell which of these clues the cell actually belongs to.
  However, if one cell is marked as belonging to one clue, then we can be sure that it belongs exclusively to that clue. This means the following: any other cell which might have been detected as belonging to the same clue and which is "out of range" for a group stemming from the original cell can be seen as a false positive and removed from the belonging entries accordingly.
  Consider the following result, where a figure above a cell means that cell was marked as potentially belonging to the clue that corresponds to the figure:
  ---║ 1 ║
---║ 2 2 ║
1 2║ | |■| | | | | |■| ║
  Because cell 9 belongs exclusively to clue 2, and because cell 3 is out of range for a group of 2 stemming from cell 9, cell 3 cannot be part of clue 2: it is a false positive. We get the following result after removing it:
  ---║ 1 2 ║
1 2║ | |■| | | | | |■| ║

---

Combining all of the above together, we get the following algorithm:
(using 0-indexing for cells, as opposed to 1-indexing used throughout the question and this answer)
(using # to indicate comments)

Input:  
- a row (array of cells of length rowWidth)
- corresponding clues (array of integers of length cluesLength)

Initialize belongEntries, a 2D array of dimensions (rowWidth, cluesLength), to false.

For each checked cell (index i) in the row:
    leftCross ← index of the first crossed cell left of cell i, or -1
    rightCross ← index of the first crossed cell right of cell i, or rowWidth

    For each clue (index n):
        spaceLeft ← minimum space required for all clues before clue n
        If spaceLeft > 0:                   # If there are clues before clue n
            spaceLeft ← spaceLeft + 1       # Account for an extra space

        spaceRight ← minimum space required for all clues after clue n
        If spaceRight > 0:                  # If there are clues after clue n
            spaceRight ← spaceRight + 1     # Account for an extra space

        # maxLeft and maxRight are the maximum coordinates group i can span over (inclusive)
        maxLeft ← spaceLeft
        maxRight ← rowWidth - spaceRight - 1   # -1 to account for 0-indexing

        # Restrict both max coordinates to the coordinate of a potentially closer crossed cell
        # Add or remove 1 from the cross coordinate to get the coordinate of the cell *next* to it
        maxLeft ← max(maxLeft, leftCross + 1)
        maxRight ← min(maxRight, rightCross - 1)

        # Check that cell i is within allowed coordinates for clue n
        If maxLeft <= i <= maxRight:
            boundLeft ← index of the left boundary of group i
            boundRight ← index of the right boundary of group i 

            clueVal ← (value of clue n)
            groupLength ← (boundRight - boundLeft) + 1

            # Not mentioned above, but don't forget to check that group i is not larger than the clue we're trying to match it to
            If groupLength <= clueVal:

                # Check that the boundaries of group i do not overlap with other     clue spaces
                If maxLeft <= boundLeft <= boundRight <= maxRight:

                    # Check that a group satisfying clue n would fit between max coordinates
                    If (maxRight - maxLeft) + 1 >= clueVal:
                        belongEntries[i, n] ← true

# Detect and eliminate false positives
# Using a lot of shortcuts here not to expand on irrelevant array indexing gymnastics

exclusiveCells ← list of indices of cells which belong to only one clue
For each indice i in exclusiveCells:
    clueIndex ← index of the only clue associated with cell i
    clueVal ← value of the only clue associated with cell i
    otherCells ← list of indices of cells which also belong to clue clueIndex

    # In case i is part of a group
    boundLeft ← index of the left boundary of group i
    boundRight ← index of the right boundary of group i
    groupSize ← (boundRight - boundLeft) + 1

    # Max additional distance the group can cover to reach an outer cell
    extent ← clueVal - groupSize

    # For each cell sharing the same clue with cell i
    For each indice j in otherCells:
        # Ignore if cells i and j are part of the same group
        If not (boundLeft <= j <= boundRight):
            # We're going to compute a distance to cell j,
            # but that distance calculation should start at different points
            # depending on whether cell j is left or right of group i
            If j < i:
                startCell ← boundLeft
            Else: # if j > i
                startCell ← boundRight

            distance ← abs(startCell - j)

            # If a spanning group would overextend its available space, remove cell j from the entries for that clue
            If distance > extent:
                belongEntries[j, clueIndex] ← false

---

Results for a 20-long row (clues marked above cells are indicated by their 0-index in the list of clues):
---------║ 3 3 ║
---------║ 0 1 1 1 2 2 4 4 ║
1 3 4 2 1║ |■| |×| |■|■|■| |×│■| | |■| | |■| |■| ║

After removal of false positives (1st pass):
---------║ 3 ║
---------║ 0 1 1 1 2 2 3 4 ║
1 3 4 2 1║ |■| |×| |■|■|■| |×│■| | |■| | |■| |■| ║

After removal of false positives (2nd pass):
---------║ 0 1 1 1 2 2 3 4 ║
1 3 4 2 1║ |■| |×| |■|■|■| |×│■| | |■| | |■| |■| ║

To account for cases like this one, in which several passes of elimination are needed, we can simply loop over the elimination part of the algorithm until no more changes are brought:

oldBelongEntries ← Same array as belongEntries, initialized to false everywhere

While belongEntries != oldBelongEntries:
    oldBelongEntries ← belongEntries

    # Detect and eliminate false positives
    ...

Nice !