Log 4 - Picross Hint Guide System

Pico² is releasing on Feb 9th 2025! Follow on itch.io for updates!

See the Pico² Design Document!

One of my favourite features of the Picross S series is the hint guide system. I thought it would be simple to design and figured I’d get it done before drawing up requirements, but it ended up being just as complicated as the solver!

Notice how the hints get greyed out. This applies to complete lines (such as the second from the bottom, where the whole row is filled), but is most useful for partially completed rows, such as circled one.

The player hasn’t filled it fully, but the algorithm finds that the 1 block is already filled with crosses around it, so just the 1 hint gets greyed out.

Also, if you fill a row incorrectly, all greyed hints suddenly become solid again. It’s a helpful system that gives you just enough guidance so as not to branch too far down a mistaken route, but it also doesn’t give away so much information to ruin the puzzle.

Through a lot of iteration, I settled on the following algorithm to implement this.

1. Input a partially (or fully) completed row and its hints.
2. Check the row against all possible permutations of these hints in a row of this size.
   • If the partial row does not exist among these permutations, the player has filled something incorrectly. Return all solid hints.
3. Find all “blocks” in the partial row.
4. For each hint, check each block. Compare it to the hint:
   • If the block has the same length…
   • and has left enough room on either side for the rest of the hints…
   • then this block may represent that hint. Note that.
5. For each block, check which hints it could represent.
   • If it could represent many hints or no hints, we cannot say for certain which hint should be greyed out for it. Skip it.
   • If it can only represent one hint, we know for certain that hint can be greyed out.

That’s the high-level overview - let’s see the implementation.

For steps 1 and 2, I used the functions I built for the last blog to generate every possible permutation of those hints in a row of the given size. I then filter that against the partial row; if nothing is returned, then the partial row is incorrect.

For example, consider the row 0010 with hints [1, 1]. 1s are filled spaces, 2s are crosses, and 0s are empty.

At least one valid option exists for the partial row, so it is accepted.

In step 3, I define a block as a contiguous string of 1 or more filled spaces, surrounded by either the puzzle edge or a cross. In reality, I padded the row at the beginning and end with crosses, so the puzzle edge is represented consistently. To find the blocks I just looped through the row, keeping track of the last value to determine when a block started and ended.

Note that even if a block is the correct size for a hint, it must be surrounded by crosses to be picked up by the algorithm. This just makes the player put in that little extra effort to have the hints grey out, so it doesn’t help you too much.

Step 4 is the important one, particularly the second bullet. I initially didn’t include this, meaning some important cases were not caught.

For example, consider the row 1200000 with hints [1, 1].

By step 4, we’ve found one block starting at index 0 and ending at index 0. Without the second bullet, I would:

• Check hint 0 (value 1) and see that it’s the same length as the block
  • This block is a candidate for hint 0.
• Check hint 1 (value 1) and see that it’s the same length as the block
  • This block is a candidate for hint 1.

This block is recorded as being able to represent either hint. But in reality, it cannot represent hint 1 because that would mean hint 0 has to come before it; we’re right at the edge of the puzzle, and there isn’t space.

To fix this, I used the following algorithm:

1. Input a partial row, its hints, the details of the block in question, and the index of the hint we’re checking if it could represent.
2. Get the section of the row to the left of the block. Get the hints before the given index.
   • Check if these hints could fit in the given index.
     • Think of this as a “sub-row”, like it’s from a smaller puzzle. Just like before, we check if the existing filled row is valid.
   • If they can’t fit, this block can’t represent the hint. Return false.
3. Get the section of the row to the right of the block. Get the hints after the given index.
   • Check if these hints could fit in the given index.
   • If they can’t, return false.
4. At this point, the remaining hints can, in at least one way, fill the rest of the row. This block could represent that hint, so return true.

Let’s see it in action. Consider a row 000212011000 with hints [1, 1, 2, 1]. The diagram below shows the process when checking if the block (the only valid one) is compared against hint 1.

With this, the previous example would now correctly reject the second hint, as there isn’t space to the left of the block to fill the other hints (hint 0).

I’m pretty sure (🤞😬) this captures all cases; I wrote two dozen test cases with everything I could think of and bother to test. The full notebook is available on GitHub, and here are the results!

I’ll probably need to do some optimisation for tokens when I port this over to Lua, but I’m super happy with it! I was really daunted by this problem when I realised how complex it could be, but it ended up being pretty manageable.

Next, I’ll actually draw up the requirements - could definitely do with a break from debugging…

Follow on Twitter @wsasaki01 Follow on Bluesky at wsasaki.bsky.social