Actually, there’s another way to put an upper bound on the number of puzzles: Start with the number of solutions, and then decide for each square whether it’s going to start off revealed or hidden. That gives an upper bound for the number of puzzles at 2^81 times the number of solutions. Which is still an overestimate, because some of those “puzzles” would be left with insufficient information to solve them, but it should be a much closer estimate, since the typical puzzle has much fewer than half of the numbers revealed.
I refuse trial an error solutions but I will spend a lot of time trying to find solutions that involve logical comparisons I haven’t tried before. Usually I will find one but the time I spend is embarrassing.
I notice my times seem to run in patterns, recently I went through a period where my average times had more than doubled and it had me worried. The last few days they have come back in line. I have severe insomnia and for some reason that doesn’t seem to affect me much. I am starting to think that too many sweets or carbs was the culprit.
Sudoku puzzles are very similar to the problem of automatic test pattern generation, which involves creating a set of test vectors with input values for a digital circuit that will detect all detectable faults in the circuit under some fault model. The most common is to set every gate input and output to a 1 or 0, as if it were tied to power or ground. The fault is detected if some output of the curcuit under the fault does not match the good output. ATPG is of course NP complete.
Say you need a 0 at the output of an OR gate. Then the only possibility you have to consider is when all inputs the gate are 0. That’s like have 8 of the squares in a row or column filled in.
ATPG algorithms use “trial and error” also. If there is a choice between a 0 and a 1 somewhere, it selects one, continues to process, and backtracks to use the other value if it hits a contradiction. There are often several levels of backtracking, and the difficulty of the circuit can be related to the number of backtracks required to generate a test. Unlike Sudoku some faults are untestable, which we can find if we riun out of options and still and still don’t have a test.
One area of research was analyzing the circuit to find the best choice when begin forced to try a value. Has anyone done that for Sudoku? When I make a choice I try to select a value which will have the most impact on the rest of the puzzle, but it is just intuition at this point.
I need to write a column about this some day.
Of course, in almost ten years, nobody’s managed to actually explain the difference between “logical comparisons” and “trial and error” in a meaningful way. There’s a bunch of folks saying “it’s obvious” in this thread, then giving an example that’s just trial and error with a bound on the number of squares you can fill in before you have to have a contradiction.
Assuming a unique solution and that at least 16 squares have to be filled in to begin the puzzle, that means that there’s “logical comparison” that requires no more than a mental stack depth of 70. There seems to be widespread agreement that that if you need to use all 70, that’s just “trial and error.” A previous post asserts that a depth of 8 is not “trial and error.” So where’s the boundary?
I’m with the people who claim that everybody’s using trial and error, with a different internal limit to how hard the trial can be. I’d be willing to change my mind on this, but do that, I’d want to seem something, for example, like:
- Here’s a list of rules you can use to determine a the value of a square.
- None of these rules needs more than some depth <x> of trial stack (where <x> is well short of “the whole thing.”)
- This list of rules is complete: ALL puzzles can be solved by application of these rules and no others.
I think a lot of the fuzziness is on that last clause. If the set of “logical comparisons” is infinite (or finite but bounded only by the size of the search space), then I’m back to “but that’s just trial and error.”
This immediately crossed my mind when i posted. I can’t figure out a way to discern trial and error from logical solution. I feel certain there is a way to define it, I just don’t know what it is. It really gets down to how long of a sequence of moves can I keep track of before I start having to write things down.
Any given person will have a (perhaps somewhat fuzzy) limit to how many steps they can store in their head, and one can define “trial and error” to mean only searches that exceed that number of steps. But then, two people might have different standards of “trial and error”.
If you want, you could ask “Can all puzzles be solved using seven steps or less of mental storage?”, or the like. Or, if you wanted to take into account that more advanced “logical” methods are more complicated, and you wanted to formalize things further, you could ask something like “Can all puzzles be solved by an algorithm using less than 100 bits of working memory?”. But until you put that number in, the question can’t be answered.
To me, “trial and error” is having to reason more than one level of reductio ad absurdum at a time. That is, if I have a square that can only be two values, or a row, column or block where a value can only be in one of two squares, then making a 50/50 guess should either lead to a contradiction or a verity (a square either is a value, or cannot be a value). IOW, the sort of situation where you solve a forced chain. For multiple either/or branches you have to solve a “forced net” (see above link), which is utterly beyond me.
There is IMO a bright line available. It only really plays in the very easy puzzles, or the late stages of more difficult puzzles.
If there is any blank square whose value is fully determined by only already-filled squares, and hence there is no need to consider any other blank squares to solve the instant blank square we’re in what I call “obvious mode”. Fill in that target square with that obvious value & continue.
Contrast that with the harder case where there are no blank squares which are fillable by obvious mode thought. Now you’re stuck using more complicated approaches:
What some might call “trial and error” or “smart trial and error” I call “logical definitive search” where you attempt to use dependencies between the filled squares and some small number of target blank squares to *uniquely *determine the value of at least one of those targets.
The next fall-back is what I call “logical non-definitive search.” Same as above, but the best guess-free logic you can apply can only reduce your target square to 2 or more candidate values. You’re forced to explore by trial the candidate values. You “guess” which of the several to try first, but that’s the first and only entrance of randomness into the decision process at that ply.
Last of all is what most would call “trial and error” and I call “brute force”: simply selecting a promising target square then randomly guessing a candidate value that’s not prohibited by the filled squares and is also *not *informed by any logic derived from the other blank squares. Then working forward from that assumption (in mental if not physical pencil) until you win or contradict. And backtracking to the original guess when you contradict. This is the naïve beginning programmer algorithm.
To me at least the first line between “obvious mode” and the others is very bright. Beyond that I can distinguish between the cases pretty easily, but I can see how some people might quibble that these are distinctions that don’t amount to real differences.
And as Chronos says, different people with different memory & logical abilities and Sudoku skills will be able to “logical definitive search” farther and deeper than others. Their decision tree goes farther. So they can tackle harder puzzles while staying entirely in obvious or logical definitive search mode. Other lesser thinkers might have to fall back to brute force at the same point in the same puzzle.
I tend to play games that enable me to stay in logical search mode, definitive or otherwise. If I get “stuck”, where my best logic can make no progress anywhere and my next move is to choose a target square, reduce the choices to those permitted by the filled squares only and then pick one candidate value at random I simply give up on that puzzle.
I suspect, from watching many other people play on airplanes, that many people consider anything other than “obvious mode” to be pure “trial and error” and too unrewarding to bother with.
nm
I play the hard and mdium levels and tend to average at about the 50% range in performance. Once I get to evil I need to pull out a pencil and paper which doesn’t interest me.
I see people counting “steps”, but what defines a step?
[In particular, for every Sudoku puzzle, it is a valid logical inference “If the board is partially filled in like so, then the unique completion is like so”. Why can I not admit that as an atomic one-step rule of logic? I don’t necessarily mean to take the stand that there’s no reasonable nontrivial formal definition of a “step” you can give, only that I don’t know what it is to be as of yet.]
But there are many techniques that bridge the “obvious mode” and the “trial and error” mode, such as two in a box. I’ve almost never had to use trial and error on first and second stage puzzles, and on only say 10% of level 3 puzzles. Level 4 puzzles often requires it. One such method is two in a box. Say you are working on a 3 x 3 block, and number m and number n only appear in two squares. Even if other numbers can appear in these two squares due to lack of constraints, you know they actually cannot, and in this way one of the other squares become obvious. Some hard puzzles are 3 in a box.
When doing trial and error I circle the choice I make (of two) and put a single line under the values filled in due to this choice. That makes it simple to backtrack.
I think when people guess they don’t do it logically but fill in a value willy nilly, which leads to a disaster more often than not. Trial and error is not really guessing.
Granted a big issue here is that the term “trial and error” means different things to different people. Ref indistinguishable, “step” has the same problem.
Some consider any move past “obvious mode” to be “trial and error.” Others consider the first time they have to use pencil = admit that a backtrack might be in their future past this point to be “trial and error.”
I was trying to offer my taxonomy as one set of reasonably (to me at least) well-defined terms.
A clarifying question about terminology:
Am I correct in interpreting “obvious mode” here as meant to include only the one rule of inference “If it is the only blank square remaining in its row, column, or box, fill it with the remaining value”?
(Or is there something more to it? Keeping in mind, in some sense, every Sudoko board has the property that every blank square’s value is fully determined by only the provided already-filled squares.)
The Wikipedia Sudoku page is unfortunately a mess, and has been for a while.
Waaay back when it had some useful details that got wished into the cornfield. In particular, it had the method for encoding a puzzle as a Boolean formula. Some of the “Math-ier” stuff has been shoved into other pages. (Check the first link if you’re into enumerating puzzles.) But not the full encoding.
The Boolean encoding must exist simply because the existence-of-a-solution version of the problem is NP-Complete (from SAT). But it can be worked out directly. Let X[sub]i,j,k[/sub] denote if there is an “i” (0-9) at grid point (j,k). The restrictions are encoded as a sequence of Boolean conditions plus the locations of the givens have the variables replaced by true or false. If this Boolean formula is true, there is (at least) one solution.
Can you determine the value of a Boolean formula via trial and error? Sure. But there are other ways not at all related. For example, you can just multiply out all the clauses to get a Boolean formula in DNF. (An sequence of products of literals "or"ed together.) If it comes out “false”, there is no solution. If it comes out as a single product, that tells you the unique solution. If not, there’s more than one.
The reason people don’t use the latter method in general for all things NP is that the formula can get very large, even exponential, during the processing. Even if the result is going to be quite simple. But it isn’t trial and error. (And it isn’t Quine McCluskey either.)
I don’t know how many times I’ve pointed out in these types of threads that just because something is a method to solve a problem that doesn’t mean it’s the only method.
Long ago, Steve Cook pointed out that the “trail and error” method for string matching using a push-down-store, while naively exponential, could be simulated in linear time. (Vs. the quadratic time the obvious algorithm is.) This inspired a search for a direct method and the result was Knuth–Morris–Pratt. So not all things that look “trail and error”/exponential really are. That’s why P=NP? is still an open problem.
No, it’s not quite *that *obvious. The point is that the inference chain involves only the one blank square we’re trying to fill plus the already filled squares.
Here’s an arbitrary example of inference more complex than “the 9th value in a row, column, or block is determined to be X”, but still considers only a single blank in the inference.
Assume the board has a row and a column, each of which have 7 filled and 2 blanks. The intersection is one of the blanks. That’s our target. We reason like this: We see the row is lacking a 1 and a 2. The intersection is therefore either a 1 or a 2. There is already a 2 appearing in the column. Therefore the intersection must be the 1.
There are more complex qualifying inferences than this example. The key distinction I make is whether the target blank can be determined by inspecting only the filled-in squares and giving zero thought to any potential constraints to or from other blank squares.
I’m not arguing that this is some kind of deep or powerful observation; it’s merely my taxonomy of search methods.
Do you know how far back? Wikipedia does keep copies of all previous page versions:
I’m using it (or the similar “stack depth”) to mean more or less “a proposed number placed into a specific square.”
“If I place a 4 in square “A”, that means I could put a 5 or a 9 in square “B”, which would mean that the “9” couldn’t go in square “C”, leading to a contradiction” would have two or three “steps” depending on whether you could the failure “step.”
Others may differ.
Unfortunately, is was quite some time ago, so a large range of uncertainty. I tried to search back at one point years ago, but it was a hopeless mess even then. I was making more a comment on Wikirot than anything.