3
$\begingroup$

A Nonogram intro (Credit to Wikipedia for quote)

Nonograms, also known as Hanjie, Paint by Numbers, Picross, Griddlers, and Pic-a-Pix, and by various other names, are picture logic puzzles in which cells in a grid must be colored or left blank according to numbers at the side of the grid to reveal a hidden picture.

source: Wikipedia

Simply put, a Nonogram is a grid that using "hint numbers" allows you to fill in a grid.

Example:

enter image description here

"Guarantees"

I wanted to try and figure out if a row is "guaranteed." By that I mean the ability to solve a row with nothing but that rows hint numbers. For example in a 10 long row, using the hint [3,3,2] there is only one solution that being:

[3,3,2] | [1][1][1][0][1][1][1][0][1][1]

Left of the pipe being hint numbers and right of the pipe being the row. One's representing a filled square and zeros being a blank or cross

Some rules and formatting

While trying to figure out how to solve all possible 10 long "Tape-Nonogram" guaranteed hints I attempted to solve it using this method.

Step 1

First thing I do is I write down the hint numbers I will be checking with the "tape" below, formatted the same way as written above.

[3,1,2,1]
[1][1][1][0][1][0][1][1][0][1]

Step 2

Next thing I do is write out a formula for the first hint number. The way it's written is; starting is the number of that hint number, basically a number to make it easier to look at, next is our hint number and the crosses. The way this is formatted is

(0/1):A:(0/1)

'A' Being the hint number, to the right or left is a 1 or a 0: a 1 to the left, for example will indicate that there is a blank/cross to the left of the filled in cells, a 0 indicates that there is no cross/blank.

! Note: if the cross/blank was indicated in the previous calculation, it will be formatted as such: 0[1]:A:(1/0) and will be calculated as a 0

[3,1,2,1]
[1][1][1][0][1][0][1][1][0][1]
1   0:3:1 
2   0[1]:1:1 
3   0[1]:2:1 
4   0[1]:1:0 

Step 3

Calculate the sum of the hint number and the cross/blanks

[3,1,2,1]
[1][1][1][0][1][0][1][1][0][1]
1   0:3:1 -> 0 + 3 + 1 = 4
2   0[1]:1:1 -> 0 + 1 + 1 = 2
3   0[1]:2:1 -> 0 + 2 + 1 = 3
4   0[1]:1:0 -> 0 + 1 + 0 = 1

Step 4

Sum up all of the calculated numbers

[3,1,2,1]
[1][1][1][0][1][0][1][1][0][1]
1   0:3:1 -> 0 + 3 + 1 = 4
2   0[1]:1:1 -> 0 + 1 + 1 = 2
3   0[1]:2:1 -> 0 + 2 + 1 = 3
4   0[1]:1:0 -> 0 + 1 + 0 = 1
SUMALL([4,2,3,1]) = 10

Step 5

Finally indicate if there is only one solution or not.

[3,1,2,1]
[1][1][1][0][1][0][1][1][0][1]
1   0:3:1 -> 0 + 3 + 1 = 4
2   0[1]:1:1 -> 0 + 1 + 1 = 2
3   0[1]:2:1 -> 0 + 2 + 1 = 3
4   0[1]:1:0 -> 0 + 1 + 0 = 1
SUMALL([4,2,3,1]) = 10
[Yes]

I wrote all the steps in this template below

[A,B,C...]
[0][0][0][0][0][0][0][0][0][0]
1   (0/1):A:(0/1) -> (0/1) + A + (0/1) = SumA
.   .
.   .
.   .
SUMALL([SumA,SumB,SumC...]) = Sum
[Yes/No]

The Problem

Now with all that out of the way it's time to get to the heart of what I'm asking. As you do this you tend to notice a pattern, numbers with a "SUMALL" equal to the tape length tend to all have one unique solution. But this pattern breaks down quite quickly. For example, with a tape having a length of 10, given the hint [4,4] there is more than one solution, yet the SUMALL value is the same as the length of the tape.

[4,4] {1}
[1][1][1][1][0][1][1][1][1][0]  
1   0:4:1 -> 0 + 4 + 1 = 5
2   0[1]:4:0 -> 0 + 4 + 0 = 4
SUMALL([5,4]) = 9
[No]

[4,4] {2}
[1][1][1][1][0][0][1][1][1][1]  
1   0:4:1 -> 0 + 4 + 1 = 5
2   1:4:0 -> 1 + 4 + 0 = 5
SUMALL([5,5]) = 10
[No]

This happens for multiple different hints. Using the 10 length tape which all have more than one solution yet have a SUMALL equal to the tape length.

I wanted to know, for a tape with Length N how many "False guarantees" (hints in which there is more than one solution yet the SUMALL is equal to N) exist and if this is even possible to calculate.

$\endgroup$
8
  • 2
    $\begingroup$ Why is [9] notated as 0:9:1 instead of 0:9:0? I don't see any reason why a blank space would be needed next to the 9. $\endgroup$
    – bobble
    Apr 25, 2022 at 23:57
  • $\begingroup$ That's a mistake! Well spotted sorry about that! Also, it's to keep consistency. If I was to not note that blank space it would be an arbitrary reason. Just because "hey look there's a blank at the end I'll just ignore it" $\endgroup$ Apr 26, 2022 at 0:00
  • $\begingroup$ But if you're trying to force a single solution, blanks on either end (i.e. those not between runs of shaded cells) don't matter because you can shift the whole pattern to the side. I don't understand what such things count in your notation - in fact, I suspect I'm fundamentally misunderstanding your notation - how I see it disagrees with my tried-and-tested intuition. $\endgroup$
    – bobble
    Apr 26, 2022 at 0:11
  • 5
    $\begingroup$ The only blanks that matter are blanks between two hints. A simple formula to determine whether a hint is unique is simply to sum the hints, then add the number of hints minus 1 (the number of gaps between two hints). If this is equal to the row length, it's unique. So for "3 1 2 1" it's (3+1+2+1) + (4-1) = 10. For "9", it's just 9+(1-1)=9, which is not equal to 10, so it's not unique. $\endgroup$
    – justhalf
    Apr 26, 2022 at 0:38
  • 1
    $\begingroup$ The sum for "4 4" is also not 10, it's 9. The second 1 should be bracketed. Really, I think you can see this simply by counting the number of gaps instead :) $\endgroup$
    – justhalf
    Apr 26, 2022 at 0:49

1 Answer 1

1
$\begingroup$

What we are looking for

The first thing to notice is that the "SUMALL" number depends not only on the clues, but the solution (e.g. see the last example in the question). Therefore I think we need to reword the question slightly, to find how many sets of hints have more than one solution, where at least one solution has a SUMALL equal to the length of the row.

The second thing to notice is that the SUMALL just counts the length of each hint plus any adjacent empty cells, without double-counting. Here are some example rows showing which cells are counted by SUMALL (X is filled, . is empty; ^ points to a cell that is counted)

2 2 | X X . . . X X
      ^ ^ ^   ^ ^ ^  SUMALL = 6
2 2 | . X X . . X X 
      ^ ^ ^ ^ ^ ^ ^  SUMALL = 7
2 2 | . . X X . X X
        ^ ^ ^ ^ ^ ^  SUMALL = 6

In the first example, we can see that a gap of more than two empty cells between runs results in an uncounted cell; in the second example, a gap of two empty cells between runs is completely covered, and a gap of one cell at the end is also covered; and in the third example, a gap of one between runs is covered (without being double-counted!) and a gap of more than one at the beginning or end is not completely covered.

For the SUMALL value to be equal to the length of the row, all the cells must be "covered." Each hint can cover its own run, plus at at most two empty cells (one at each end). However, to have more than one solution we need a slack of at least one cell. Together, these give us the following inequalities:

(sum of hints) + (number of hints) ≤ (length of row) ≤ (sum of hints) + 2 × (number of hints)

Note that this formula does not guarantee that all solutions will have a SUMALL equal to the row length, but just that at least one solution will (which is what we want). Take an example from the OP, with hints 3 1 2 1 and a row of length 10 we have:

(3 + 1 + 2 + 1) + 4 ≤ 10 ≤ (3 + 1 + 2 + 1) + 2 × 4
                 11 ≤ 10 ≤ 15

The inequalities are not satisfied, therefore there is no "false guarantee" (the solution is in fact unique). The other example, with hints 4 4 and a row of length 10:

(4 + 4) + 2 ≤ 10 ≤ (4 + 4) + 2 × 2
         10 ≤ 10 ≤ 12

In this case the inequalities are satisfied, so a "false guarantee" does exists as shown in the OP.

Counting solutions

We can count the hints that give "false guarantees" by, for example, generating all possible hints for a given row length and checking which satisfy the inequalities. For a row of length 10, there are 70 such sets of clues (counting permutations of the same numbers as distinct, e.g. our list includes both 1 7 and 7 1). The sequence for rows of lengths 1, 2, 3… is 0, 1, 2, 3, 5, 9, 15, 25, 42, 70…

Searching the OEIS for this sequence yields A200047, "Number of compositions [ordered partitions] of n having smallest part equal to 2," but with an offset of two: the number of "false guarantees" for a row of length n is A200047(n+2). We can see the equivalence between the two through the following argument.

Take a list of hints that yield a "false guarantee." In a solution with SUMALL equal to the row length, all gaps are of length 1 or 2, otherwise they could not be covered. The gaps at the ends of the row are length 0 or 1, but we can extend these to gaps of lengths 1 and 2 by adding one empty cell to each end. For example:

1 2 2 1 | X . . X X . . X X . X .

becomes:

        . X . . X X . . X X . X . .

Note that for a given list of hints and row length, the number of gaps of each length is fixed. Now, rearrange the gaps so that all gaps of length 1 precede all gaps of length 2:

        . X . X X . . X X . . X . .

This configuration is unique for a given list of hints; and since the list of hints can be uniquely determined from a solution, there is a one-to-one mapping between lists of hints and configurations. Now, find the first gap of length 2; it is guaranteed to exist, otherwise the solution would have no slack and it wouldn't be a "false" guarantee. Call this gap the "pivot." Every run before the pivot has a gap of length 1 to its left, and every run after has a gap of length 2 to is right, as illustrated below:

       |. X|. X X|. .|X X . .|X . .|
         2    3    2     4      3

Write down the length of each group of run and gap (as above), including the pivot gap (which doesn't have an associated run). Note that each group before the pivot has a length of at least 2, and each group after the pivot has a length of at least 3. This means two things: first, the smallest group has length 2, so any list of hints with a "false guarantee" for a row length of n can be transformed into a composition of n+2 whose smallest part is 2. Second, the pivot is always the last group of length 2, so it can be uniquely determined from just the list of group lengths. This means that the process is reversible, and any composition of n+2 with smallest part 2 can be turned into a list of hints that gives a "false guarantee." Therefore, the number of "false guarantees" and the number of compositions are the same.

This sequence has the following generating function: $$ \frac{(x - 1)^2}{(x^3+x-1)(x^2+x-1)} = \frac{x}{x^3+x-1} - \frac{1}{x^2+x-1} $$ And obeys the following recurrence relation: $$ a(n) = 2a(n-1) - a(n-4) - a(n-5) $$ And here are the first 20 terms:

n a(n)
1 0
2 1
3 2
4 3
5 5
6 9
7 15
8 25
9 42
10 70
11 116
12 192
13 317
14 522
15 858
16 1408
17 2307
18 3775
19 6170
20 10074

Glossary

In case my terminology is non-standard, here are the terms I use:

  • Cell: one of the little squares in the nonogram. Can be "filled" or "empty."
  • Hint: (a.k.a. "clue"); one of the numbers along the sides of the nonogram.
  • Run: a contiguous group of filled cells, corresponding to a hint.
  • Gap: a contiguous group of empty cells.
  • Slack: the difference between the length of a row or column and the minimum number of cells required to fit the clues. The formula for slack is (length of row) − (sum of hints) − (number of hints) + 1.
$\endgroup$

This site is temporarily in read-only mode and not accepting new answers.

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