1
$\begingroup$

I'll readily admit that this likely isn't the right place to put this, but I figured it'd be most interesting to this community in particular. I noticed this pattern because of my background in Computer Eng, oddly enough, though it treats nonogram puzzles entirely mathematically.

I've been doing nonogram puzzles for quite some time now, and over that time I've learned how to solve each puzzle using only logic and reasoning. And while this is the point of the puzzle, I think most people tend to simply take the "freebies" and then solve the rest of the puzzle case-by-case. Below I'm going to use a line of reasoning argument to suggest that every nonogram puzzle with an equal number of rows & columns can be solved, or at least started, using an all-inclusive algorithm.


Here is my argument:

Consider a nonogram puzzle of size n, where n is the unit-length of each side. For each row and for each column, there is a sequence of numbers that dictate (1) the size of each group within the row or column and (2) the total number of groups in the row or column (e.g. '1, 1, 1' would mean that there exist 3 groups of size 1 in the row or column). 'Group' in this context refers to a continuous sequence of filled unit-squares separated from each other by at least one blank unit-square. Note that the sequence is ordered such that each group within the row or column must appear in the order it's listed in the sequence given (e.g. '2, 1, 1' would mean that the leftmost group in that row or column would need to be a '2'). This is the definition of 'nonogram puzzle' I will be using from this point forward.

If we consider each numeric sequence as an array of numbers, then the minimum total amount of space that each array will fill within its row or column can be calculated as such:

m = sum(ar) + size(ar) - 1

where m is the minimum total space it occupies, ar is the array of numbers denoting groups in this row or column, sum is a function that adds each number in the array & returns the result, and size is a function that returns the length of the array. We know this to be true since each number represents a group and each group must be ordered and separated by at least one blank unit-square.

Side note: You may have noticed already, but this formalizes when you get "freebies" just a little better; if you find m = n, then there is exactly 1 way that the groups can fill the row or column.

This identity will be used for the remainder of my explanation. At this point I will move to explaining by example since it will make more sense that way.

It is fairly obvious to see that, if it is ever the case that m > n/2 & the size of our array is exactly 1, there must be at least one guaranteed unit-square we can fill. This is because, even if the group was moved all the way to one direction or another, there would always be an overlap in the dead center of the row or column. For example, if the sequence is '6' and n = 10, we can guarantee that the middle 2 unit-squares must be filled even if the other 8 are left uncertain. You can prove this experimentally pretty quickly on your own if you like. But, if you've ever done a nonogram, you'll know this is rarely case, so this isn't really very useful except in the very specific case stated above. Or is it?

If we can generalize this principle to arrays of all sizes greater than 1, this would generalize a method of at least starting the row or column with almost no other information given. And as it turns out, we can.

Consider another example, this time where n = 5 and its sequence of groups is '2, 2'. We'll go about the same method solving it, but this time we'll attempt to generalize it by manipulating n instead of the array itself. For this case, m = 5, allowing us to use our special case rule and complete the row or column immediately. As an illustration, I'll put the solution to this row or column below. Since there are a finite number of states that each unit-square can have, I'll use 1 symbol for each state that can occur: '1' for a filled unit-square, '0' for a blank unit-square, and '?' if we don't know yet.

The solution to this example is:

1 1 0 1 1

Notice that there are no question marks; we know for certain exactly what everything is since our rule states that there can only be one solution. But what would happen if we increased n from 5 to 6? Our array hasn't changed, so m hasn't changed either. But what about our solution? What can we guarantee is true in every case? We can figure this out pretty easily using brute-force if we want.

1 1 0 1 1 0
1 1 0 0 1 1
0 1 1 0 1 1

In normal binary probabilities, there would be 64 possible outcomes if we had no information about the row or column at all; each unit-square has 2 finite possibilities. But we do have information about the row or column. We know that there must be exactly 2 groups of 2; the only thing we don't know is the size of the gap between them. Because of this, there are exactly 3 possibilities we can consider here.

If we analyze our possible solutions like a Karnaugh map, we come up with only 2 certainties: that the second and second-to-last squares are filled in every case. This makes the identities of these positions in the row or column tautologically filled, like so:

? 1 ? ? 1 ?

Another way of thinking of this is to understand that, if we were to AND the three binary results together, each position where a '1' lies would be a '1' in every case, meaning that no matter what solution is actually correct, you know for certain that those two unit-squares will be filled. Similarly, if you were to NOT each line before applying the AND operator, any position containing a '1' would be blank in every possible outcome. That didn't happen here, but you can see how we'd come to that conclusion if all the solutions had a zero in a particular position.

So what did we actually do here? Well, another way of thinking about the process we went through is that we split the row or column into 2 regions of length 3 and then looked at every possibility of where each group could go as if it were isolated into its own row or column of size n / 2. Do you see the connection? Since each grouping needed an individual substrata of size n / 2, we had 2 new rows or columns of size 3 instead of one big row or column of length 6. From there, we simply applied our not-so-special case where n / 2 > m for each individual sequence (ar = '2' for n = 3 & ar = '2' for n = 3) to find that the middle square in each substrata must be filled for each subset of the total row or column.

As you can probably imagine, this line of reasoning works for any row or column with any sequence, as long as the sequence is homogeneous. That is, as long as it's made up entirely of the same number. But what happens if the sequence given is heterogeneous? What do we do then? Let's look together.

Consider another example, this time where the sequence is '1, 2' for n = 4. Using the same notation as before, most people would be pretty quick to see that the solution comes out to:

1 0 1 1

Using our same reasoning as before, let's increase n by 1 and see what happens. Now our possibilities are:

1 0 1 1 0
0 1 0 1 1
1 0 0 1 1

The only common filled square here is the '1' second to the end of the row or column, so our guaranteed squares come out to:

? ? ? 1 ?

Obviously not very helpful, but it's better than nothing. But how else could we have gotten here? We can't split n down the middle; it's odd. And besides, who's to say where the line should go?

Just like we've been doing all along here, lets just choose somewhere and try to justify it from the end of the maze backwards again. We know that neither group can be of size 0 or 5, since neither group can fit inside a strata of length 0. We already know the result we should arrive at, so of the 4 remaining possibilities, we need only rule out what can and cannot happen. 1 & 4 and 2 & 3 could happen, but 3 & 2 would mean that the latter strata would be entirely filled (which isn't the case) and 4 & 1 would mean that a group of 2 must fit into a stretch of length 1, which is impossible. 1 & 4 would guarantee that the first unit-square would be filled, which we know not to be the case, so the only thing that can be true is the grouping of 2 & 3.

Here is where the rigorousness of my line of reasoning ends, and where my own theory begins. I have never been proven wrong on this, but I wholeheartedly understand and empathize with the fact that that doesn't mean my theory isn't wrong. What I'm about to present to you is simply an unproven method with 0% error, experimentally (but anecdotally, mind you). If you can find a contradiction, please tell me so.

A third way of looking at all the examples we've looked at so far is to look at the guaranteed answers as the result of a skip-code. Not a skip-code like the traditional cipher, but well... you'll see why I call it that.

The code I've come up with is this:

n = size of row or column
m = sum(ar) + size(ar) - 1
s = n - m

where n, m & ar are defined as they are above, and s is the length of the skip for each number along the sequence for the row or column.

If we consider a single possible solution where every group is as far in one direction as possible, then the unit-squares we know to be filled are located s units from the start of each group. So, for our example of '2, 2' with n = 6, s would be 1 and therefore the guaranteed filled squares would be 1 unit from the farthest left part of the leftmost possible solution, within each group.

That may be a little confusing in words; allow me to demonstrate.

1 1 0 1 1 0

is the farthest-left solution of the three total possible solutions to the above example. Counting from the first '1' of each sub-sequence, we know that, after skipping 1 filled unit-square, the rest of the unit-squares marked '1' are guaranteed to be filled. Similarly, if we chose to examine the sample solution:

0 1 1 0 1 1

we would come to the same conclusion given that we counted right to left instead of left to right.


While I know I can't prove this with a catch-all proof of how I know this works, I have never seen it fail and am confident it's true (until I see a contradiction, obviously). The only limitation I know of for this is that the possible solution you're looking at has to be as far over left, right, up or down (depending on whether it's a row or column) as possible.

Has anyone else come to this conclusion, or has everyone else done so and I'm simply the first I know of to write it down?

$\endgroup$
4
  • $\begingroup$ I suspect your method boils down to the following: for each group, figure out its leftmost and rightmost possible placements (by packing the groups as closely as allowed), and color in the region where those two placements overlap (if any). It's pretty clear that this is valid, and also that any square not colored in this way has a possibility of being blank. $\endgroup$
    – Karl
    May 22, 2023 at 4:14
  • 2
    $\begingroup$ according to wikipedia the problem is NP complete $\endgroup$
    – user619894
    May 22, 2023 at 4:20
  • $\begingroup$ What's a nonogram? $\endgroup$ May 22, 2023 at 6:53
  • 1
    $\begingroup$ @Gerry Myerson It's a puzzle where you're given a grid and are asked to fill in squares either black or white, with the default being white. It's kind of like a mix between a sudoku and a crossword, but with no numbers or letters (there are 2 finite states each cell can be instead of 9 or 26). $\endgroup$ May 23, 2023 at 12:44

1 Answer 1

1
$\begingroup$

What you describe is pretty much one of the basic strategy for solving nonogram. As shown by @Karl, this is indeed valid, because it correspond to the overlap of the leftmost and rightmost solutions. This is optimal, because for each cell not colored by this method, you can find one solution with this cell black, and one with this cell white, with one exception though. A solution with this cell white can be obtained by stacking the most groups on the left of the cell (by putting them leftmost) then the remaining groups on the right (by putting them rightmost). We can find a solution with this cell black by moving the closer group on the cell. This is possible only if there is not two groups immediately adjacent to the cell. This happen only if the line is fully covered by the groups (with a single space between each). In this case, we know where all the black cells are, and we also know where all the white cells are.

This can be generalized by line analysis, where you maintain the total consistency on the constraints of a single line (even if there is already some cells that are determined). This can be solved in polynomial time, with a dynamic programming approach, see: https://ir.nctu.edu.tw/bitstream/11536/22772/1/000324586300005.pdf

$\endgroup$
2
  • $\begingroup$ I had no idea that was a thing; I'll check that link out for sure. The only reason I phrased it as counting down is because it's not necessarily true that just because the two most extreme configurations overlap that you've found guaranteed filled squares. A square is only guaranteed to be filled if there's overlap in the same group. As an example, if we had '7, 1, 1, 1' with n = 20, there would be overlap on the 3 single-square groups, but we couldn't guarantee those to be filled because, as you said, there's at least one scenario where those are unfilled as well. $\endgroup$ May 23, 2023 at 12:39
  • $\begingroup$ With your example, there is no overlap between the leftmost and rightmost solutions, but there will one for the group 7 if n is 19 $\endgroup$
    – caduk
    May 23, 2023 at 13:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .