I am trying to solve nonograms.

Right now I am trying to solve for overlapping patterns : A 3 long bar in a 5 wide grid will always be at least on the 3rd cell a 2-6 in a 10 wide grid allow to place 1 cell for the 2 bar an 5 cells for the 6 bar

I tried to solve this through permutations, but is is way too inefficient (3M permutation for a 10 wide grid) and there is quite a few rule to reduce the result count :

• bar order can't be changed
• there is at least 1 empty cell between 2 bars (you can't merge bars)

I need to find an algorithm to find all different repartitions of empty cells between bars : 2XX2XX2, X2X2XX2, X2X2X2X, etc