Skip to main content

Indie game storeFree gamesFun gamesHorror games
Game developmentAssetsComics
SalesBundles
Jobs
TagsGame Engines

Glad my findings helped. To get more specific and show a minimal proof, here is an example of a nonogram that generates ambiguous hints:

x o
o x


When the hints are rendered out, you'll have 1 and 1 in the columns and 1 and 1 on the rows. Now look at this alternate solution:

o x
x o


The same hints would be generated, which makes this a valid solution. Yet if the checker is only checking that the solution matches the first pattern, this will be rejected even though it doesn't contradict any of the hints.

This kind of checkerboard happens most often in pixel art that uses dithering for shading, which is why you want to avoid having too much detail. You can start to see why having a puzzle that is 30x30 can get frustrating, not only because it is so large that it takes forever to check the rows and columns, but also because the artist is then tempted to cram in as much detail as they can, which leads to dithering, which leads to a puzzle with multiple solutions.

I noticed that you don't want to implement a hint checker, and I'm curious why that is, as checking that the hints are satisfied isn't overly complicated or bad for performance. You're already doing most of the work if you're marking the row and column hints complete while the player is playing. 

Here's an example a simple algorithm for how that could be done without solution-checking the entire puzzle on every frame/re-paint: imagine you have two arrays, one that contains "companion numbers" for each row, one for each column. These "companion numbers" would actually be bit flag sets (so you're not having to use a JSON-like object or array just to store some booleans). More on that later. Now that we have the data structure defined, I'll go over the algorithm. After the player makes a move, run a check on only the row and column the move was made on, and compare the hints with the state of the row/column. If the hints are satisfied (e.g. if the row hint says 1 5 1 and the row contains "oxooxxxxxoooxoo" where x is a filled square, then the hint can be considered satisfied), or there is a contradiction (say the row instead contains "oxxoxxxxxoxoxoo", that would be incorrect), set a flag saying so for the relevant row/column. When drawing/repainting the row and column hints, consult the flags to decide whether to color-code it as normal, complete, or in-error. Complete does not mean correct, it just means the hint is locally satisfied, but the only way for the puzzle to be solved is if every row and column is simultaneously complete. This is where the next phase comes in. After doing the post-move row and column check, simply check the flag arrays to see if they are all flagged as complete. If so, the puzzle is solved. Checking 2 small arrays of length N and M (N + M = O(n) time) is exponentially faster than checking the whole puzzle (N x M = O(n^2) time).

Bit flags: Most programming languages have bitwise operations such as AND (&), OR (|), XOR (^) and NOT (~), which work on all of the bits of an integer in parallel, you can use these operators to pack multiple booleans in a single integer (up to 32 on an unsigned 32-bit int), taking advantage of the way it's stored in memory. So if you imagine you've defined some constants like FLAG_COMPLETE = 0x1, FLAG_ERROR = 0x2, and more (0x4, 0x8, 0x10, 0x20, 0x40, 0x80, etc), and you also have a number called flags, you can do the following operations with bitwise operators (note that I am presenting this in pseudo-code, you can translate to your language of choice):

combining multiple flags: mask := (FLAG1 BITOR FLAG2)

setting a flag: flags := flags BITOR mask

un-setting a flag: flags := flags BITAND (BITNOT mask)

checking if a flag is set: if ((flags BITAND mask) = mask) then ...

toggling a flag: flags := flags BITXOR mask

clearing all flags: flags := 0

If you haven't already, this is definitely something you want to store in your programmer's toolbox in general, right next to modular arithmetic and lookup tables.

If it's not the math that gives you pause, but concern over how the final product will look after alternate solutions are used, you can just fudge it. That's what most implementations do, fade in the image, which often uses multiple colors and hardly resembles the nonogram at all. It's a bit hard to interpret what your objection is, honestly.

you can just fudge it. That’s what most implementations do, fade in the image, which often uses multiple colors and hardly resembles the nonogram at all. It’s a bit hard to interpret what your objection is, honestly.

Valid point, but my knee-jerk reaction to that statement is that I don’t want to fudge it and don’t want to swap out what they’ve solved for the larger collage I have them building.

A puzzle having more than one solution can end up just being a constraint that I apply to myself while making puzzles: every puzzle I make must have one solution. Then solving by solution or solving by not breaking contract with hints doesn’t matter.

I noticed that you don’t want to implement a hint checker, and I’m curious why that is, as checking that the hints are satisfied isn’t overly complicated or bad for performance. You’re already doing most of the work if you’re marking the row and column hints complete while the player is playing.

I’m actually not marking hints complete as they are playing, either.

These aren’t choices aren’t due to implementation complexity or performance, either. This whole game is written in C with no libraries outside the bare minimum needed on the playdate side to get the current frame buffer, get input state, handle files, and pushing audio to the device. Everything else is done on my own, so I’ve already crossed more complex tasks and everything is very performant.

Really, the main concern is just getting the game to a good playable state, then worrying about working through the Quality of Life features in the backlog. I’ve gotta make more puzzles, prize art and blurbs, and do the audio.

It could also be due to the fact that, as a player, I don’t really care much about the hints being crossed off. I think what I like more, which will cause it to bubble up the backlog, is when the current run of marked cells are tallied up and shown.

To get more specific and show a minimal proof, here is an example of a nonogram that generates ambiguous hints:

x o o x

When the hints are rendered out, you’ll have 1 and 1 in the columns and 1 and 1 on the rows. Now look at this alternate solution: o x x o

Yeah! That’s exactly what is described here.

I hope you'll at least implement manual flagging, so the player can flag hints themselves.