|
It's easy to see why this puzzle has no solution. Looking at columns 4-6 we see that none of the digits 1,5,6 can occur in cells G4,H4,I4 or G6,H6,I6. So some permutation of these digits occupies G5,H5,I5 and all digits other than 1,5,6 can be eliminated from these cells. But we also see that all the digits 1,5,6 have already been placed in row G, leaving no candidates for G5. It's also easy to see why this presents a problem for the Norvig solver (and many solvers like it). If you squint at the algorithm you'll see that it behaves like DPLL (https://en.wikipedia.org/wiki/DPLL_algorithm) given a CNF encoding of the Sudoku exactly-one constraints. In this scheme constraint propagation only occurs via unit resolution. i.e., when a positive clause is reduced to a single literal because the domain of a cell is reduced to a single digit or a unit/group is reduced to having a single place for a given digit. In Sudoku land these are known as naked and hidden singles. Unfortunately, the conclusion that none of 2,4,7,8,9 can occupy G5 arises from the interaction of multiple non-unit clauses. It is simply not reachable by unit resolution. As a result, the conflict won't be discovered until the algorithm actually attempts to assign G5, and, since there are many cells that initially have fewer possibilities than G5, this is not likely to happen early in the search. Some of the faster solvers can handle this by adding checks for "locked candidates", or by representing the logic in a way that's equisatisfiable, but that makes these inferences available to unit resolution. In such cases this puzzle is recognized as unsatisfiable in microseconds. |