I decided to do a write-up of a little recursive algorithm I made for finding every configuration of a set of blocks in a line. While I was doing that I figured I might as well make a PICO-8 cartridge and do a little rendering.

Left and right to change the rendering size, up and down to scroll. To change the number and size of the blocks, the size of the line and the minimum number of spaces between blocks just change the appropriate values in _init().

Algorithm (full code in cartridge)

Thank you very much, I just recently had this problem for nonograms.

That's where I encountered the problem too! I originally had to solve this as part of my university honours project, which was about generating and solving 3D nonograms

Very interesting! Your approach with a recursive function looks very conceptually similar to an approach I used for checking rows and ticking off hint numbers in a picross/nonogram game I'm working on, though your use of strings and sub() is a *lot* more elegant than my spaghetti code that uses tables.

How easy/difficult do you think it would be to modify your algorithm to take an already partially marked row into account, as well as considering "forbidden" (x-marked) cells?

One thing I should point out is that I'm only dealing with one line at a time, but in an actual puzzle you have overlap between rows and columns. If a solid cell is part of the first block of a row it would be 'A' but if that same cell is part of the second block of the corresponding column then it should be 'B'. It's not '-' so you know it's solid, but you can't use the letter to know which block it's from. This isn't a problem so long as you're aware of it.

To answer your question ** @qbicfeet**, it would be fairly straightforward. Currently the can_shift function just checks if there's a '-' at the end of the line. If you want to make certain cells inaccessible then you would just modify this function to check that blocks aren't being placed in disallowed cells. You'd also need to make it more like the shift function, where you give it a block_id and it only cares about the part of the line from that block onwards.

As I've said, taking into account marked-as-empty cells is fairly straightforward. The difficult part is taking into account marked-as-solid cells. Here's a diagram illustrating both the problem and my solution:

I'd like to do a separate write-up of this algorithm too, but I'm going to be quite busy for the next few weeks. If you'd like to see how it works you can check section 3.4 of my dissertation: *Building the leftmost and rightmost possible solutions* (pp. 19-22).

Alternatively, you could use the above algorithm to build all possible line configurations then just remove the ones which contradict the known state. This was my original approach and for small 2D puzzles it works fine.

[Please log in to post a comment]