Nonogram, also known as Picross or Griddlers, is a puzzle where the objective is to determine if each cell on the 2D grid should be colored or left blank, using the numbers of consecutive colored cells on each line.
The following is an example Nonogram puzzle with solution.
The problem is, some commercial Nonogram games/mobile apps have puzzles which are not solvable by hand (e.g. have multiple solutions, or require deep backtracking). However, they also offer some lives to the player, where one life is lost when you try to color a cell whose correct answer is blank. So now it's time to brute-force those nasty "puzzles"!
In order to simplify the task, imagine just one line with its clue and nothing else:
3 7 | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
[3,7] are the clues, and the line length is 15 cells. Since it has multiple possible solutions, we need to risk some lives in order to fully solve this line (i.e. determine all colored cells).
Given a line with clues (a list of positive integers) and the line length, find the maximum number of lives you will lose, assuming that you brute-force the line with optimal strategy.
Note that you always guess colored cells. In actual games, guessing empty cells (either right or wrong) have no effect on your lives, so you can't "solve" the puzzle that way.
Also, you can assume the input always represents a valid Nonogram line, so you don't need to worry about something like
Let's look at some simpler examples first.
There are exactly three possibilities for this line (
O is a colored cell,
. is an empty one):
O . O O . O . . O O . O . O O
If we try coloring cell 0 (0-based index from left), one of the following happens:
- The cell is correctly colored. Now we have two possibilities, and we can choose between cell 2 and cell 4 in order to fully solve the line. Either case, we will lose one life in the worst case.
- The cell is empty, and we lose a life. In this case, we have already identified the unique solution to this line, so we're done with 1 life lost.
Therefore, the answer for
[1,2], 5 is 1.
Binary search? Nope.
The most obvious first choice is 4 or 5, which will reveal one possibility if it's blank (at a cost of 1 life). Let's say we chose 4 first. If cell 4 is indeed colored, we extend it to the left, i.e. try 3, 2, 1 and 0 until a life is lost (or cell 0 is colored, then we end up spending no lives at all). Whenever a life is lost, we can uniquely determine the solution, e.g. if we see something like this:
_ _ X O O _ _ _ _ _
then we already know the answer is this:
. . . O O O O O . .
Therefore, the answer for
, 10 is also 1.
Start with cell 11, which, if empty, will reveal the following solution right away.
O O O . O O O O O O O X . . .
Then try 12, which, if empty, gives two possibilities which can be solved at the cost of 1 extra life.
O O O . . O O O O O O O X . . . O O O . O O O O O O O X . .
Now try 2. If empty, it leads to three possibilities which can be solved similarly to the
[1,2], 5 example.
. . X O O O . O O O O O O O . . . X O O O . . O O O O O O O . . X . O O O . O O O O O O O
If you keep minimizing the risk in this manner, you can reach any solution with max. 2 lives spent.
[1,2] 5 => 1  5 => 2  5 => 4  5 => 0  10 => 1 [2,1,5] 10 => 0 [2,4] 10 => 2  15 => 2  15 => 2  15 => 3 [3,7] 15 => 2 [3,4] 15 => 3 [2,2,4] 15 => 4 [1,1,1,1,1,1,1] 15 => 2 [2,1,1,3,1] 15 => 3 [1,1,1,2,1] 15 => 5
For the last two cases, the optimal strategy is not going through the minimum blanks, but simply going from left to right (or right to left). Thanks to @crashoz for pointing it out.
Standard code-golf rules apply. The shortest valid submission in bytes wins.
If someone comes up with a polynomial-time algorithm (with the proof of correctness), I will award +100 bounty to such a solution.