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

Block placement algorithm

Cart File | Forum Post |

	More cartridges by RhythmLynx

More Cartridges [View All]

 

Block placement algorithm

by RhythmLynx

Cart #23323 | 2016-06-20 | Code ▽ | Embed ▽ | 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)

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.