This linesolver aims to deduce everything that is logically deducable from a line. It does this very rigorously, and therefore guarantees not to miss anything, but it is actually too rigorous, and will take an unnecessarily long time over it.

The approach is to determine the possible states of each unknown cell. The algorithm records these as it runs, and initially assumes that there are no possible states. Then it recursively finds arrangements of blocks that match the line's clue, and each arrangement determines a possible state for each cell; these states are merged into the recorded states. When all arrangements have been found, any cells whose recorded states show only one possibility can be determined.

The algorithm starts by considering the ‘left-most’ solid block, and places it in the ‘left-most’ position. (We arbitrarily regard one end of the line as the ‘left’, even if the line is vertical. All linesolvers are agnostic about the actual orientation.) If necessary, it moves the block further right until it is not covering any dots, and does not abutt any solids. It will either find such a place, run out of space, or reveal a solid to its left as it slides right.

If it finds a suitable place, it then considers the next block by placing it just to the right of the previous block. Again, it may have to slide the block rightwards to find a suitable place for it. Having found one, it moves to the next block, and so on…

Positioning of the last block has an additional constraint that there must be no more solids in any cell after it. If there is such a solid, the last block must continue further, until either that solid and all subsequent solids are covered, the block runs out of space, or a solid is revealed on its left as it moves.

When all blocks are in suitable positions, the state of the line derived from these positions is merged with the recorded state. Then the algorithm goes back to the right-most block, and tries to move it further, and so on…

Note that whenever the positioning of a block fails (i.e., a solid is revealed as the block moves, or the block runs out of space), the algorithm switches to the previous block and tries moving it again under the same constraints as before. If positioning of the left block fails, there are no more arrangements to consider, and the results in the recorded states can be analysed.

Length: 29 Rule: 9,1,1,1 Original: >-----#########--------#-#-#--< Broken: > --#########------- #- - < >######### < covers dot, so move on > ######### < covers dot, so move on > ######### < covers dot, so move on > ######### < covers dot, so move on > ######### < covers dot, so move on > ######### < fits, so next block > ######### # < covers dot, so move on > ######### # < covers dot, so move on > ######### # < covers dot, so move on > ######### # < covers dot, so move on > ######### # < covers dot, so move on > ######### # < covers dot, so move on > ######### # < fits, so next block > ######### # # < abutts solid, so move on > ######### # # < fits, so next block > ######### # # # < fits, so merge, and move on > ######### # # # < covers dot, so move on > ######### # # #< fits, so merge, and move on > ######### # # < reveals solid, so previous block > ######### # < fits, so next block > ######### # # < fits, so next block > ######### # # # < fits, so merge, and move on > ######### # # # < covers dot, so move on > ######### # # #< fits, so merge, and move on > ######### # # < reveals solid, so previous block > ######### # < abutts solid, so move on > ######### # < fits, so next block > ######### # # < fits, so next block > ######### # # #< fits, so merge, and move on > ######### # # < covers dot, so move on > ######### # #< no space, so previous block > ######### # < reveals solid, so previous block > ######### < reveals solid, so previous block suitable arrangements: >-----#########-------#--#-#--< >-----#########-------#--#---#< >-----#########--------#-#-#--< >-----#########--------#-#---#< >-----#########----------#-#-#< result: >-----#########-------++-#-+-+<

You can see that, while this algorithm will consider every
possible arrangement of blocks, not all arrangements need to
be — after one block has found a new position, information
learned about blocks to its right from previous arrangements
will end up being redetermined, which is a waste of effort.
Consider how the fast-complete linesolver
(`fcomp`) tries to take safe shortcuts to
avoid this waste.

One optimisation is to keep track of how many unknown cells in the recorded state still have only one possibility (or fewer than what was known before the algorithm stated, for colour puzzles). If this reaches zero at any time, the algorithm knows already that it can determine nothing from this line at this time.