3 ms·
> In those, guessing/searching is basically required, right? Apparently no guessing is required! In Prolog it's fine for a variable (that represents a square
by hjek 7y ago
> In those, guessing/searching is basically required, right?
Apparently no guessing is required!
In Prolog it's fine for a variable (that represents a square in a sudoku puzzle) to be somewhere between 1 and 9. (Yes, that can be a bit mind-boggling, because in most other programming languages a variable can't really be either this or that. As far as I know, not even in SQL which is also somewhat declarative.)
You might get in a situation where one square (let's call it A) is between 1 and 3 and two other squares on the same row (let's call them B and C) are both between 1 and 2. One constraint that we have given is that all numbers on a row must be distinct (because that's one of the rules of a sudoku puzzle), so given those constraints and facts, Prolog can deduce that the value of the first square must be 3.
Therefore no guessing (or searching + backtracking) is required; only constraint propagation.
This is what the query would look like in a Prolog REPL:
[library(clpfd)], % load library for constraint logic over finite domains
A in 1..3, B in 1..2, C in 1..2, all_distinct([A,B,C]).
And this is the reply:
A = 3,
B in 1..2,
all_distinct([3, B, C]),
C in 1..2.
I can only recommend you install SWI Prolog[0] and give it a try. It's quite fun!
(Triska's explanation is probably more in depth and correct, but I thought I'd just chip in with my newbie way of explaining how I understand this. But seriously, check his videos. They're great stuff. The illustrations make the explanations accessible.)
[0]: http://www.swi-prolog.org/ http://www.swi-prolog.org/
- taeric 7y agoRight, I think this is somewhat just talking past each other. You don't have to backtrack on the values, but it is essentially searching on the constraints. That is, if you have a board where there are multiple legal moves on every open position, but only one solution, you still have to pick which constraint to propagate to find the solution. No?
- tom_mellior 7y agoBut 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.