3 ms·
But when you are at a state like A = 3, B in 1..2, all_distinct([3, B, C]), C in 1..2. you don't yet have a complete solution in which each va
by tom_mellior 7y ago
But when you are at a state like
A = 3,
B in 1..2,
all_distinct([3, B, C]),
C in 1..2.
you don't yet have a complete solution in which each variable is bound to a number. In fact, you don't even have a guarantee that a solution exists. To get to this point no search is necessary, but to get from this point to a guaranteed solution, you need to call a "labeling" predicate, which will do backtracking search.
- hjek 7y ago> In fact, you don't even have a guarantee that a solution exists. If there's more than one soluton or no possible solution, then it's not a "well-posed" sudoku puzzle; at least according to Wikipedia here: > The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.[0] But yes, I guess for puzzles with multiple solutions, you'd necessarily have to search for them. It's also possible to make a mine sweeper field that has no valid assignment of mines[1], yet usually mine sweeper games don't do that. As you note about this state, B in 1..2, all_distinct([B, C]), C in 1..2. it has no unique solution seen in isolation, so search/labelling would be required; just like it would on a blank sudoku square with no hints at all. [0]: https://en.wikipedia.org/wiki/Sudoku https://en.wikipedia.org/wiki/Sudoku [1]: https://worldcomp-proceedings.com/proc/p2016/PDP7565.pdf https://worldcomp-proceedings.com/proc/p2016/PDP7565.pdf
- tom_mellior 7y agoYou're right about Sudoku of course, but I thought we were talking of the general case. Even more general than recreational puzzles: Real-world applications of constraint programming won't generally be so nice as to have a single solution.