3

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().

Cart #23323 | 2016-06-20 | Code ▽ | License: CC4-BY-NC-SA
3

Algorithm (full code in cartridge)

 ```function block_char(block_id) local chars = "abcdefghij" return sub(chars, block_id, block_id) end function can_shift(line) return sub(line, #line, #line) == "-" end -- shifts all blocks of the given id or higher rightwards one cell, -- leaving all blocks left of that id unchanged function shift(line, block_id) local char = block_char(block_id) local pos = 1 for i = 1, #line do if sub(line, i, i) == char then pos = i break end end local pre = sub(line, 1, pos-1) local post = sub(line, pos, #line-1) return pre.."-"..post end function find_solutions(blocks, length, min_spaces) -- build and store the leftmost solution local line = "" for block_id = 1, #blocks do for i = 1, blocks[block_id] do line = line..block_char(block_id) end if block_id ~= #blocks then for i = 1, min_spaces do line = line.."-" end end end if (#line > length) return {} -- no solutions, can't fit while #line < length do line = line.."-" end local solutions = {line} find_spreads(solutions, line, 1, #blocks) return solutions end function find_spreads(solutions, line, block_id, num_blocks) local my_line = line while can_shift(my_line) do if block_id < num_blocks then find_spreads(solutions, my_line, block_id + 1, num_blocks) end my_line = shift(my_line, block_id) solutions[#solutions + 1] = my_line end end blocks = {2, 2, 2} length = 8 min_spaces = 0 solutions = find_solutions(blocks, length, min_spaces) ```

P#23324 2016-06-20 18:40 ( Edited 2016-06-21 20:28)

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

P#23339 2016-06-20 22:24 ( Edited 2016-06-21 02:24)

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

P#23357 2016-06-21 05:12 ( Edited 2016-06-21 09:12)

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?

P#23389 2016-06-21 12:06 ( Edited 2016-06-21 16:06)

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.

P#23407 2016-06-21 16:28 ( Edited 2016-06-21 20:28)