The `fcomp` linesolver

This linesolver aims to be the optimum algorithm, by being both fast and obtaining all of the logically deducable information from a line's current state.

((Adjustments necessary to make the algorithm work with multicoloured puzzles will be shown in double brackets, like this. Still working this out…))

Overview

The algorithm suposes positions for each block, attempts to find valid arrangements of them, then slides them about to find other valid arrangements. It may invalidate blocks to allow one to expose a solid, and another to cover it up.

The following values are maintained and manipulated:

mode

the current operating mode

Four modes are possible:

INVALID — finding a new valid arrangement after one or more blocks have become invalid
SLIDING — finding other valid arrangements from the current one by allowing blocks to slide within gaps
DRAWING — releasing one block covering a solid by drawing an ealier one up to cover the solid instead
RESTORING — returning invalid blocks to their last valid positions after determining that the current, tentative attempt to re-validate them would lead to absurdity

The initial mode is: INVALID

block

the number of the current block

During INVALID, blocks to the left of the current block are considered to be tentatively valid, i.e. not covering any dots, not covering each other, and not touching each other ((except when different colours)), and not exposing any solids between each one and the previous block (or the start of the line).

pos[0..n-1]

The current positions of each block

A block's position is the position of its left-most solid.

All blocks start at position 0.

solid[0..n-1]

the offset from a block's position to the left-most solid covered by that block

These are initially set to invalid values, indicating that each block is not known to cover any solid.

oldpos[0..n-1]

oldsolid[0..n-1]

last valid positions and solid offsets

When a valid arrangement is found, the positions are recorded here, so that we can return to them during RESTORING. Solid offsets are also retained to avoid the inconvenience of recomputation. The initial values are the same as for the values they shadow.

mininv

number of earliest invalid block

Initially zero, this indicates the first block whose position needs to be restored during RESTORING, and where to start looking during DRAWING.

target

the number of a solid-covering block, which we aim to release

This must be set before starting DRAWING.

((last[0..n-1]))

((a flag to indicate that a block is the right-most of its colour))

((When you have placed the last (right-most) block of a certain colour in a tentatively valid position, you must check that no cells to the right of it are already of that colour, otherwise you have an invalid arrangement. For monochrome puzzles, there is only one solid colour, and the right-most of all blocks of that colour is the right-most block of the line, so this part can be omitted.))

`INVALID` — Finding valid positions for each block

Basic checks on the current block's position are made first. Is it protruding beyond the line?

if (pos[block] + rule[block] > limit[block])
  goto RESTORING;

Alternatively, this could be done as the block is moved during other states before switching to this one.

The cells covered by the current block in its current position are tested to see if they are dots ((or, more generally, to see if any cannot be of the block's colour, i.e. incompatible)). Also, the offset of the first encountered solid ((of the same colour)) is recorded in offset.

solid[block] = invalid;
for (int i = 0; i < rule[block]; i++) {
  if (cell[pos[block] + i] is incompatible with col[block]) {
    // I2...
  }
  if (solid[block] == invalid && cell[pos[block] + i] is col[block])
    solid[block] = i;
}

If a dot ((an incompatible cell)) is encountered, the block cannot stay where it is. If no solid is encountered before the dot, the block jumps just beyond the dot, and INVALID continues afresh from there. But if a solid ((of the same colour)) is also encountered before the dot, it cannot jump the dot without exposing the solid – target is set to block before changing to DRAWING.

// I2
if (cell[pos[block] + i] is incompatible with col[block]) {
  if (solid[block] != invalid) {
    target = block;
    goto DRAWING;
  }

  pos[block] = i + 1;
  goto INVALID;
}

If no dot ((incompatible cell)) is encountered, the cell after the block is checked for a solid ((of the same colour)). If found, the solid offset is set to the length of the block unless it is already a valid offset. Then the block must move right one cell at a time, adjusting the solid offset, until a non-solid is found. But if the solid offset is zero at any time, the block is trying to span too many solids, so an earlier block must be drawn up to release it – target is set to block before changing to DRAWING.

if (solid[block] != invalid &&
    cell[pos[block] + rule[block]] is col[block])
  solid[block] = rule[block];

while (pos[block] + rule[block] < limit[block] &&
       cell[pos[block] + rule[block]] is col[block]) {
  if (solid[block] == 0) {
    target = block;
    goto DRAWING;
  }

  pos[block]++;
  solid[block]--;
}

Otherwise, the block is in a tentatively valid position. block is incremented, and the next block is positioned just after its previous, then INVALID is started afresh.

But when the last block becomes valid, a check is made of subsequent cells to ensure there are no more solids. If there are none, all positions are recorded in the results, pos and solid are recorded in oldpos and oldsolid for all blocks, and then SLIDING begins on the last block. If there are trailing solids, and the last block already covers a solid which prevents it from reaching the trailing solid, target is set to block before changing to DRAWING. Otherwise, the block is moved so it just covers the trailing solid, and we stay in INVALID.

((It is additionally necessary to check for trailing solids of the same colour as the current block whenever it becomes valid if it is the last block of that colour, i.e. its last flag is true. If okay, move onto the next block; if no more blocks, go to SLIDING.))

`SLIDING` — Sliding a block from one valid position to another without uncovering solids

The current block tries to move one cell to the right at a time, recording the possible states of the cell just vacated and the cell newly occupied, and recording pos and solid in oldpos and oldsolid. The block may have to stop for any of these reasons:

It would exceed the line.
It would touch the next block ((which happens to be of the same colour, or it plainly exceeds the start of the next block)).
It would expose a solid.
It would cover a dot. In this case, it may be able to jump it, provided none of the other problems would then arise.

In these cases, block is decremented. Dots otherwise are jumped (still recording the possible states of the affected cells, and still recording pos and solid in oldpos and oldsolid).

When there are no more blocks, the right-most block covering a solid is set as target and block, mininv is set invalid, and DRAWING begins.

if (block == last)
  lim = line_length;
else if (col[block] == col[block + 1])
  lim = pos[block] - 1;
else
  lim = pos[block];

while (pos[block] + rule[block] < lim &&
       cell[pos[block] + rule[block]] is not dot) {
  if (solid[block] == 0)
    solid[block] = invalid;
  else if (solid[block] != invalid)
    solid[block]--;
  record dot at pos[block];
  pos[block]++;
  record col[block] at pos[block];
}

oldpos[block] = pos[block];
oldsolid[block] = solid[block];

`DRAWING` — Drawing earlier blocks forward to cover solids and so release later blocks

The aim of this mode is to find a pair of blocks such that the later one covers a solid, and the earlier one can be made to cover that solid without exposing any of its own. This will allow the later block to move elsewhere without exposing its solid.

The current block is checked to see if it covers a solid. If so, it becomes target.

Then block is decremented, and the new block is checked to see if it can be moved to cover block target's solid without uncovering its own. If not, DRAWING begins again from this state.

Otherwise, the current block is moved to just cover the target's solid. Also, if mininv is greater than the current block, it is set to the current block.

Then we switch to INVALID.

((The pair of blocks chosen must be of the same solour.))

do {
  if (block < base)
    stop;
  if (mininv != invalid) {
    if (block == mininv) {
      block = max - 1;
      goto RESTORING;
    }
  }

  if (solid[block] != invalid)
    target = block;
  block--;
} while (col[block] != col[target] ||
         (solid[block] != invalid &&
          pos[target] + solid[target] - rule[block] + 1 >
            pos[block] + solid[block]));

if (mininv == invalid || block < mininv)
  mininv = block;

pos[block] = pos[target] + solid[target] - rule[block] + 1;

goto INVALID;

`RESTORING` — Putting blocks back after detecting absurdity

Blocks from mininv upto block inclusive are restored to their positions retained in oldpos and oldsolid. The earliest of these that covers a solid is chosen as target, and block is set to mininv, before switching to DRAWING.

for (i = block + 1; i > mininv; i--) {
  pos[i - 1] = oldpos[i - 1];
  solid[i - 1] = oldsolid[i - 1];
  if (solid[i - 1] != invalid)
    target = i - 1;
}
block = mininv;
goto DRAWING;

Optimisations

We can record how many cells are unknown before work begins. Each time we determine that a cell can be both solid and dot, we decrement this count. If it reaches zero at any time, no information can be obtained from the line, and we stop without trying further arrangements.
base — We can maintain a base block number, initially zero. All blocks to the left of this are at their final positions because their solid offsets are zero – which can be detected during SLIDING.
max — We can maintain a maximum block number, initially the total number of blocks. This block, and all to its right are at their final positions because it would touch or overlap the next block if it moved further (e.g. by jumping over a dot). This can also be detected during SLIDING.

Example

Below is a trace of the algorithm acting on a line and its clue, which are displayed in the first few lines. Each subsequent section shows the current mode, the current block (and its length and position), a recapitulation of the initial state of the line, a scale, and graphically the positions of all blocks. mininv is shown as the trailing mN number.

The graphical block positions occupy more than one line when blocks occupy overlapping positions. # and ! show cells belonging to the current block. X and ! show the offset of the first solid covered by the block.

X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
rule: 1,5,1,1,1

We start with all blocks on the left, waiting to find valid positions.

INVALID
Block 0 of 1 at 0
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B0        >#
           +++++
           +
           +
           +                                   < [0-5) m0
Dot at offset 0
Skipped to 1

We have detected that block 0 covers a dot, so it cannot stay here. We move it past the dot, and try again… several times.

INVALID
Block 0 of 1 at 1
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B0        > #
           +++++
           +
           +
           +                                   < [0-5) m0
Dot at offset 0
Skipped to 2

INVALID
Block 0 of 1 at 2
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B0        >  #
           +++++
           +
           +
           +                                   < [0-5) m0
Dot at offset 0
Skipped to 3

INVALID
Block 0 of 1 at 3
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B0        >   #
           +++++
           +
           +
           +                                   < [0-5) m0
Dot at offset 0
Skipped to 4

INVALID
Block 0 of 1 at 4
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B0        >    #
           +++++
           +
           +
           +                                   < [0-5) m0
Dot at offset 0
Skipped to 5

INVALID
Block 0 of 1 at 5
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B0        >     #
           +++++
           +
           +
           +                                   < [0-5) m0
Valid at 5

At last, there is room for block 0. Consider the next block, ensuring that it starts after the current one.

INVALID
Block 1 of 5 at 7
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B1        >     + #####
           +
           +
           +                                   < [0-5) m0
Valid at 7

INVALID
Block 2 of 1 at 13
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B2        >     + +++++ #
           +
           +                                   < [0-5) m0
Valid at 13

INVALID
Block 3 of 1 at 15
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B3        >     + +++++ + #
           +                                   < [0-5) m0
Valid at 15

INVALID
Block 4 of 1 at 17
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B4        >     + +++++ + + #                  < [0-5) m0
Valid at 17
  Solid at offset 0

(Additionally, we notice that block 4 covers a solid at position 17 + 0.)

INVALID
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B5        >     + +++++ + + X                  < [0-5) m0
Trailing solid at 22

We've placed all the blocks, but still some trailing solids remain exposed. We'll have to draw up earlier blocks to release the later blocks to let them cover the later solids.

DRAWING
Block 4 of 1 at 17
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B4        >     + +++++ + + #                  < [0-5) m0
Target is 4
New target is 4
Block 3 brought to 17

We have chosen to draw up block 3 to cover the solid currently covered by block 4.

INVALID
Block 3 of 1 at 17
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B3        >     + +++++ +   #
                            +                  < [0-5) m0
Valid at 17
  Solid at offset 0

INVALID
Block 4 of 1 at 19
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B4        >     + +++++ +   X #                < [0-5) m0
Dot at offset 0
Skipped to 20

INVALID
Block 4 of 1 at 20
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B4        >     + +++++ +   X  #               < [0-5) m0
Dot at offset 0
Skipped to 21

INVALID
Block 4 of 1 at 21
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B4        >     + +++++ +   X   #              < [0-5) m0
Dot at offset 0
Skipped to 22

INVALID
Block 4 of 1 at 22
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B4        >     + +++++ +   X    #             < [0-5) m0
Valid at 22
  Solid at offset 0

INVALID
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B5        >     + +++++ +   X    X             < [0-5) m0
Trailing solid at 35

Still we have trailing solids, so we must draw up block 2 to release 3 to release 4 to cover the final solid.

DRAWING
Block 4 of 1 at 22
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B4        >     + +++++ +   X    #             < [0-5) m0
Target is 4
New target is 3
Block 2 brought to 17

The target was 4 which covers a solid. The current block was also 4, so we looked at 3, and found it unsuitable because it already had a solid. It became the new target, then we looked at 2. It was suitable to cover 3's solid, because it does not cover one itself.

INVALID
Block 2 of 1 at 17
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B2        >     + +++++     #
                            +    +             < [0-5) m0
Valid at 17
  Solid at offset 0

INVALID
Block 3 of 1 at 19
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B3        >     + +++++     X #  +             < [0-5) m0
Dot at offset 0
Skipped to 20

INVALID
Block 3 of 1 at 20
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B3        >     + +++++     X  # +             < [0-5) m0
Dot at offset 0
Skipped to 21

INVALID
Block 3 of 1 at 21
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B3        >     + +++++     X   #
                                 +             < [0-5) m0
Dot at offset 0
Skipped to 22

INVALID
Block 3 of 1 at 22
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B3        >     + +++++     X    #
                                 +             < [0-5) m0
Valid at 22
  Solid at offset 0

INVALID
Block 4 of 1 at 24
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B4        >     + +++++     X    X #           < [0-5) m0
Valid at 24

INVALID
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B5        >     + +++++     X    X +           < [0-5) m0
Trailing solid at 35

INVALID
Block 4 of 1 at 35
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B4        >     + +++++     X    X            #< [0-5) m0
Valid at 35
  Solid at offset 0

We eventually have all the blocks in valid positions with no trailing solids. This arrangement must be merged into the (so far empty) results, before SLIDING.

(This should be the same as the left-most arrangement, as computed by the fast algorithm.)

INVALID
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B5        >     + +++++     X    X            X< [0-5) m0
New valid state found
Accumulate>-----...............................<
Accumulate>.....#..............................<
Accumulate>......-.............................<
Accumulate>.......#####........................<
Accumulate>............-----...................<
Accumulate>.................#..................<
Accumulate>..................----..............<
Accumulate>......................#.............<
Accumulate>.......................------------.<
Accumulate>...................................#<
Accumulate>....................................<

SLIDING
Block 4 of 1 at 35
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B4        >     + +++++     X    X            !< [0-5) m5
Limit is 36
Right block is right-most
Limit reached; 4 blocks left

SLIDING
Block 3 of 1 at 22
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B3        >     + +++++     X    !            X< [0-4) m5
Limit is 34
Limit reached; 3 blocks left

SLIDING
Block 2 of 1 at 17
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B2        >     + +++++     !    X            X< [0-4) m5
Limit is 21
Dot obstructs at 18
No space past dot
Limit reached; 2 blocks left

SLIDING
Block 1 of 5 at 7
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B1        >     + #####     X    X            X< [0-4) m5
Limit is 16
Merging block 1 from 7 to 11
Accumulate>.......++++.........................<
Accumulate>............++++....................<
Limit reached; 1 blocks left

SLIDING
Block 0 of 1 at 5
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B0        >     #     +++++ X    X            X< [0-4) m5
Limit is 10
Merging block 0 from 5 to 9
Accumulate>.....+-++...........................<
Accumulate>......++++..........................<
Limit reached; 0 blocks left

All blocks have slid as far right as they can for the moment. From the right, we have to seek a block to draw up.

DRAWING
Block 3 of 1 at 22
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B3        >         + +++++ X    #            +< [0-4) m5
Target is 3
New target is 2
Block 1 brought to 13

INVALID
Block 1 of 5 at 13
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B1        >         +   #####
                            +    +            +< [0-4) m1
Dot at offset 3
Skipped to 17

INVALID
Block 1 of 5 at 17
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B1        >         +       #####
                            +    +            +< [0-4) m1
Dot at offset 1
Earlier solid at offset 0

DRAWING
Block 1 of 5 at 17
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B1        >         +       #####
                            +    +            +< [0-4) m1
Target is 1
Can't draw any more without restoring

We have drawn a block up which cannot fit. We'll put everything back, and find an earlier block.

RESTORING
Block 3 of 1 at 22
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B3        >         +       X++++
                            X    #            +< [0-4) m1
Restoring 3 from 22 to 22
Restoring 2 from 17 to 17
Restoring 1 from 17 to 11
Returned to block 1

DRAWING
Block 1 of 5 at 11
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B1        >         + ##### +    +            +< [0-4) m5
Target is 2
New target is 2
Block 0 brought to 17

INVALID
Block 0 of 1 at 17
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B0        >                 #
                      +++++ +    +            +< [0-4) m0
Valid at 17
  Solid at offset 0

INVALID
Block 1 of 5 at 19
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B1        >                 X #####
                            +    +            +< [0-4) m0
Dot at offset 0
Skipped to 20

INVALID
Block 1 of 5 at 20
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B1        >                 X  #####
                            +    +            +< [0-4) m0
Dot at offset 0
Skipped to 21

INVALID
Block 1 of 5 at 21
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B1        >                 X   #####
                            +    +            +< [0-4) m0
Dot at offset 0
Skipped to 22

INVALID
Block 1 of 5 at 22
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B1        >                 X    #####
                            +    +            +< [0-4) m0
Valid at 22
  Solid at offset 0

INVALID
Block 2 of 1 at 28
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B2        >                 X    X++++ #
                                 +            +< [0-4) m0
Valid at 28

INVALID
Block 3 of 1 at 30
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B3        >                 X    X++++ + #    +< [0-4) m0
Valid at 30

This gives us a new valid arrangement, which must be recorded.

INVALID
Block 4 of 1 at 35
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B4        >                 X    X++++ + +    #< [0-4) m0
New valid state found
Accumulate>-----+++++++++++-...................<
Accumulate>.................#..................<
Accumulate>..................----..............<
Accumulate>......................#++++.........<
Accumulate>...........................-........<
Accumulate>............................+.......<
Accumulate>.............................-......<
Accumulate>..............................+.....<
Accumulate>...............................----.<

SLIDING
Block 3 of 1 at 30
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B3        >                 X    X++++ + #    X< [0-4) m4
Limit is 34
Dot obstructs at 31
Jumpable
Accumulate>..............................+.....<
Accumulate>.................................+..<

SLIDING
Block 3 of 1 at 33
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B3        >                 X    X++++ +    # X< [0-4) m4
Limit is 34
Right block is right-most
Limit reached; 3 blocks left

SLIDING
Block 2 of 1 at 28
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B2        >                 X    X++++ #    + X< [0-3) m4
Limit is 32
Merging block 2 from 28 to 30
Accumulate>............................+-......<
Accumulate>.............................++.....<
Dot obstructs at 31
No space past dot
Right block is right-most for dot
Limit reached; 2 blocks left

SLIDING
Block 1 of 5 at 22
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B1        >                 X    !####   +  + X< [0-2) m4
Limit is 29
Limit reached; 1 blocks left

SLIDING
Block 0 of 1 at 17
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B0        >                 !    X++++   +  + X< [0-2) m4
Limit is 21
Dot obstructs at 18
No space past dot
Limit reached; 0 blocks left

We have determined that blocks 2, 3 and 4 have reached their right-most positions, while 0 and 1 are stuck on solids. There can be no more valid arrangements.

DRAWING
Block 1 of 5 at 22
X:      36>-----           -#----#        --  #<
          >012345678901234567890123456789012345<
B1        >                 X    #####   +  + +< [0-2) m4
Target is 1
Length:   36
Rule:     1,5,1,1,1
Original: >-----------------#----#####--#---#-#<
Broken:   >-----           -#----#        --  #<
  complete>-----+++++++++++-#----#++++-+++--+-#< ( 19) 0.006ms
      fast>-----+++++++++++-#----#++++++++--+-#< (  1) 0.006ms
     fcomp>-----+++++++++++-#----#++++-+++--+-#< ( 28) 0.006ms

Nonogram Solver

The fcomp linesolver

Overview

INVALID — Finding valid positions for each block

SLIDING — Sliding a block from one valid position to another without uncovering solids

DRAWING — Drawing earlier blocks forward to cover solids and so release later blocks