Hacker News Reader

Comment by taeric | Hacker News Reader

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?

View on HN

A 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) 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.

I'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.

If 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.

I'll have to dive on it more, but 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.)

It 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'.

> 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/

Right, 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?

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.

> 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

[1]: https://worldcomp-proceedings.com/proc/p2016/PDP7565.pdf

You'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.

Reply on news.ycombinator.com