
Does an ambiguity in a correct puzzle (i.e.
one that has at least one solution) always lead
to two solutions (or a doubling of solutions
with each level of ambiguity)? In other words,
must the guess always be right (for a
correct puzzle)?

Does one have to make a pair of guesses for
each undetermined cell at an ambiguity, or does
guessing for one cell implicitly make a guess
for the others (upto the next ambiguity)?
Generally, at an ambiguity with n
undetermined cells, should a solver make
2n guesses, or just 2?

At an ambiguity, suppose we make a guess (a
cell location and the new state of that cell)
X_{1}, and from it we can
derive another statelocation tuple
X_{2}, then there would have
been no point in guessing
X_{2} instead of
X_{1}. Can we work out an
algorithm to select/find the better guess
X_{1}, given our initially
intended guess X_{2}, thus
reducing the number of guesses we have to
recursively make?

If we apply that algorithm to its own result
repetitively, can we find an optimum guess? Do
we get a loop?
The first question may be answered by visiting
Hirofumi Fujiwara's Nonogram pages,
which include some ambiguous puzzles with only one
solution (try ‘Dog’ and ‘Rabbit’), so the
answer is “no”. Before I added solutionchecking to
my solver, it produced numerous solutions for a
couple of these puzzles, but I could see that some
were wrong. After adding the checker, only one
correct solution was produced. The presence of any
correct solutions alongside wrong ones proved that
some of the guesses were wrong. This leads to a
further question: what's the simplest such puzzle
that can be constructed?
My solver currently assumes that the second part
of the second question is true. But previously, you
could reverse this by compiling the library with
the C macro nonogram_GUESSAGAIN
defined — this isn't possible any more. When I
tried that with one of puzzles, it produced several
thousand correct solutions, some of which (chosen
arbitrarily) were identical. (I didn't feel like
checking them all).
An argument for making fewer guesses
is that, after making one guess (at cell
c_{1} to state
s_{1}), we may be able to
determine the state s_{2} of
another cell c_{2} which we
could have chosen for a guess instead of
c_{1}. Anything we derive from
(c_{2}, s_{2})must
also be derivable from
(c_{1}, s_{1}),
so when we backtrack to try alternative guesses
from
(c_{1}, s_{1}),
we know that a guess
(c_{2}, s_{2})
will provide no information that wasn't provided by
(c_{1}, s_{1}).
But what about trying
(c_{2}, ¬s_{2})
in place of
(c_{1}, s_{1})?
Firstly, since we chose
(c_{1}, s_{1}),
we should also try its opposite,
(c_{1}, ¬s_{1}),
which will produce one of three possibilities:

(c_{2}, s_{2})

(c_{2}, ¬s_{2})

(c_{2}, ?), i.e.
another ambiguity is reached
For case 1, c_{2} must be
s_{2} irrespective of
c_{1}, so guessing
(c_{2}, ¬s_{2})
must lead to an inconsistency. For case 2, we can
determine no more information from guessing
(c_{2}, ¬s_{2})
instead of
(c_{1}, ¬s_{1}).
For case 3, when another ambiguity is reached,
either c_{2} will be chosen for
another guess, or another cell will be chosen,
which may indirectly determine
c_{2}. Therefore, making a guess
at c_{1} means that no
alternative guess at c_{2} is
required.
In summary, after making a pair of guesses at
c_{1}, there are 3 × 3
combinations of consequences for
c_{2}:
(P is a point of ambiguity;
Q_{n} is some point
after making a guess in c_{1} at
P.)
Each entry gives a reason why each of the
guesses for c_{2} does not have
to be made after trying the guesses for
c_{1}. “NXI” means “no extra
information”, i.e. the guess at
c_{1} would already have derived
at least as much information as the guess at
c_{2}. “I” means “inconsistency”
— the guess would not lead to any solutions. “WBT”
means “will be tried” — another ambiguity was
reached by the guess at c_{1},
so one or more subsequent guesses would have been
made that would eventually fill
c_{2}, so a guess there instead
of c_{1} would imply NXI. If the
pair of guesses at a subsequent ambiguity both lead
to inconsistency, then the grid was already
insoluable at the previous guess.