4 ms·
I'm curious on your first point. There are puzzles that have multiple legal plays but only a single solution. In those, guessing/searching is basically require
by taeric 7y ago
I'm curious on your first point. There are puzzles that have multiple legal plays but only a single solution. In those, guessing/searching is basically required, right?
- triska 7y agoA valid Sudoku puzzle is such that the given clues admit precisely one solution. Hence, if you somehow manage to take into account all the initially available information, then no search is required, because, in a sense, the given hints already narrow down the entire space of (ostensibly) possible assignments to a single one. There are constraint solvers that do this. For example, with the CLP(B) version based on BDDs that I mentioned, the solver internally constructs a Binary Decision Diagram (BDD) which is like a (ideally: more compact) truth table of all assignments that satisfy the requirements. Therefore, with the CLP(B) version I posted, search is never necessary for valid Sudoku puzzles, because they admit precisely one solution, and the constraint solver deduces this unique solution by reasoning about the decision diagram. There's a severe drawback to this: The BDD may be exponential in the number of variables. That's a problem, because there are dozens of variables in many Sudoku puzzles. In practice, we are often lucky, and the worst-case space requirements do not arise. For comparison, the CLP(FD/ℤ) formulation is based on constraint propagation that ensures a certain kind of consistency for all individual constraints in isolation, but not necessarily for the combination of all constraints, i.e., the problem as a whole. In practice, at least for Sudoku puzzles, this also often leads to finding the unique solution without any search. This may also be the case if only the minimum number of clues for a valid Sudoku puzzle (i.e., 17, per https://arxiv.org/abs/1201.0749 https://arxiv.org/abs/1201.0749) is specified, as the parent mentions. In general, search is still required. In the concrete case of (standard) Sudoku, the required search, if there is any at all, is typically very small, because the many constraints usually narrow down the entire space considerably. Reducing the amount of required search is the key attraction and goal of the consistency techniques that are used by constraint systems. The available systems differ in how much and how fast they are able to prune inconsistent values, leading to notions such as global consistency, domain consistency, bounds consistency etc. that give some indication of propagation strength.
- taeric 7y agoI'll see if I can find my references again, but pretty sure this is not true. You can have a specified puzzle that has a single solution but requires a guess. I agree most are not this way, but they can be made.
- triska 7y agoIf you find such a puzzle, please let me know! Assuming the CLP(B) solver is correctly implemented, the CLP(B) solution I posted will give the unique solution without any search. On the other hand, it is comparatively easy to find puzzles where the CLP(ℤ) version will require search, even if only a small amount.
- taeric 7y agoI'll have to dive on it more, but https://news.ycombinator.com/item?id=14246452 https://news.ycombinator.com/item?id=14246452 is last time I remember discussing it. I thought the point was that sometimes searches were needed. Did I misunderstand? Have things changed? (Neither would surprise me.)
- suyjuris 7y agoIt seems a bit misleading to talk about not needing search, if you are only referring to a very specific part in the implementation of a constraint solver. Without context, I would have interpreted it as being able to avoid an exponential search over the solution space, which is (for general sudoku, under mild assumptions) impossible. So while it appears to be an advantage in principle, the claim is actually 'sometimes this is faster in practice'.
- deleted 7y ago[deleted]
- 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.