If nothing else, my proposal of “the number of bits of working memory needed for a sudoku-solving algorithm” should be unambiguous. Doubtless there will still be some algorithms which are more efficient than others, but then, some human solvers are more efficient than others, too.
In case it’s not clear, I’m not counting any squares which can be “marked in pen” against the “working memory” count.
Surely this DNF expansion is the very model of trial and error? Each product term in the DNF (before culling the unsatisfiable ones) corresponds to a way of filling out the board (or something close to that, depending on how exactly the constraints are coded), evaluated for whether it satisfies all the constraints. This is like brute-forcing through every possibility till finding one that works. If that’s not (rigorously carried out) “trial and error”, then what is?
I mean, basically, you start off with the DNF formula enumerating all possible completed Sudoku boards. And then you add on to it specific constraints of the form “Let’s demand this cell has value so and so”, “Let’s demand this cell has value so and so” to encode your specific puzzle, each time culling down the DNF formula by removing the clauses incompatible with this particular cell value. But all this amounts to is walking through every possible Sudoku board and culling out the ones incompatible with the given puzzle. Straight-up brute force exhaustive search.
(Not to mention the brute force involved in first enumerating all possible completed Sudoku boards by DNF expansion as well)
Don’t get me wrong; I’m not saying this exhaustive search trial isn’t also perfect logical reasoning! After all, I’ve been saying I don’t see a strong distinction between “logic” and “trial and error”. To me, lots of things are both. It’s just weird to put it forward as therefore an example of “definitely not trial and error”.
What do you consider this example: When you enumerate the candidates for filling in the empty squares in a block, two can be 1 or 2 (and nothing else in the puzzle eliminates one of these choices) while a third can be a 1,2 or 3. Here you can immediately fill in a 3 into the third square, but I wouldn’t call it an obvious choice, since you cannot resolve it without considering the first two squares. It is also not trial and error - you will never have to backtrack on this choice.
Thais is exactly this case from my first post:
Your example reasons about 3 blanks plus some/all relevant filled-in squares to determine the unique value for a single filled-in square.
The area where my taxonomy gets soft is that as a matter of math, a computer or human with enough storage could consider *all *the blanks with all the filled squares from the git-go and arrive at a/the solution (if one exists) in one big inference. As the esteemed **Chronos **& **indistinguishable **are speaking to each other about in tongues. 
As a matter of practicality mere humans, or at least this human, doesn’t have the working memory to do that. So while I can readily solve examples such as yours, I can’t necessarily do it when there are four more intermediate steps like “… which implies *this *pair must be a 3 and 4, which implies *that * square must be a 5 or 6 which implies …”
Once the logic chain overflows my meagre working stack space, I’m left in effect guessing between the couple of remaining candidates for my target then starting afresh down that branch of the tree, or trying to locate a more promising target square to resolve.
Okay. What confused me there is that this isn’t really a search. In test generation this is called implication, where you can fill in values directly and immediately. Say you find you have to put a “0” at the first input of a string of inverters. You can fill in all the values without doing searches. This is a bit more complicated, but if you consider the search for a solution as a tree, find the value in the third box does not make the tree grow.
Easy puzzles don’t require searches. I don’t know for sure if hard puzzles do, but I feel comforted that no one else can do them without backtracking and look ahead either.
I think the line some people are trying to draw in this thread is the difference between one-block elimination strategies and two-block elimination strategies described in this paper by Prof. Provan of UNC. The paper has a pretty good example of a sudoku where one-block strategies only get you so far at which point a single two-block strategy is applied and the rest of the puzzle falls to one-block strategies.
For some sudoku even two-block elimination strategies will not get the job done. At the time the paper was written the smallest n where n-block strategies will solve all sudoku was not known. I don’t know if that problem has since been solved.
I think the example from the paper is pretty illuminating so I’m going to reproduce it here.
This is the starting puzzle.
--- --- --- --- --- --- --- --- ---
| | 4 | || | | || | 6 | 8 |
--- --- --- --- --- --- --- --- ---
| 7 | | || | | 5 || 3 | | |
--- --- --- --- --- --- --- --- ---
| | | 9 || | 2 | || | | |
--- --- --- --- --- --- --- --- ---
--- --- --- --- --- --- --- --- ---
| 3 | | || 5 | | || | | 7 |
--- --- --- --- --- --- --- --- ---
| | | 1 || 2 | 6 | 4 || 9 | | |
--- --- --- --- --- --- --- --- ---
| 2 | | || | | 7 || | | 6 |
--- --- --- --- --- --- --- --- ---
--- --- --- --- --- --- --- --- ---
| | | || | 5 | || 7 | | |
--- --- --- --- --- --- --- --- ---
| | | 6 || 3 | | || | | 1 |
--- --- --- --- --- --- --- --- ---
| 4 | 8 | || | | || | 3 | |
--- --- --- --- --- --- --- --- ---
Using sudoku basics (one-block elimination strategies) it’s fairly easy to get to here and get somewhat stuck.
--- --- --- --- --- --- --- --- ---
|15 | 4 |23 || 7 | 9 |13 ||125| 6 | 8 |
--- --- --- --- --- --- --- --- ---
| 7 |12 | 8 || 6 | 4 | 5 || 3 |129|129|
--- --- --- --- --- --- --- --- ---
| 6 |135| 9 || 8 | 2 |13 ||15 | 7 | 4 |
--- --- --- --- --- --- --- --- ---
--- --- --- --- --- --- --- --- ---
| 3 | 6 | 4 || 5 | 8 | 9 ||12 |12 | 7 |
--- --- --- --- --- --- --- --- ---
| 8 | 7 | 1 || 2 | 6 | 4 || 9 | 5 | 3 |
--- --- --- --- --- --- --- --- ---
| 2 | 9 | 5 || 1 | 3 | 7 || 8 | 4 | 6 |
--- --- --- --- --- --- --- --- ---
--- --- --- --- --- --- --- --- ---
|19 |123|23 || 4 | 5 | 6 || 7 | 8 |29 |
--- --- --- --- --- --- --- --- ---
|59 |25 | 6 || 3 | 7 | 8 || 4 |29 | 1 |
--- --- --- --- --- --- --- --- ---
| 4 | 8 | 7 || 9 | 1 | 2 || 6 | 3 | 5 |
--- --- --- --- --- --- --- --- ---
Here’s where the two-block strategy comes in. Imagine cell (1,1) is a 1. This means cell (2,2) is a 2. This means cell (1,3) is a 3. This means cell (3,2) is a 5.
Thus we have added a 2 and a 5 in at the top of column 2. Now observe that cell (8,2) must a 2 or a 5. This is a contradiction so cell (1,1) can not be a 1.
Therefore cell (1,1) must be a 5. Once we know this, the rest of the puzzle is easily solved.
Indistinguishable made a series of posts that incredibly bafflingly tries to assert that simple Boolean multiplication is at all like trial-and-error. This is a mistake at an amazing level.
Take a numeric experession like (X+3)(X-5)(X+1) and multiplying it out to get X[sup]3[/sup]-X[sup]2[/sup]-17X-15. Was there the slightest, teeniest, fraction of a shred of trail-and-error in doing this?
Of course not! That would be absurd to think that for one second!
And replacing the values of variables for the initial settings of the board is merely replacing a variable with true or false. Much like replacing X with 4 in the above before multiplying. No other action is taken at that time. Again, is there there anything remotely going on that anyone could possibly imagine that is related to trail-and-error going on?
Never!
You’re using “search” in a more technical sense than I was. Which makes some sense because you’re far more sophisticated mathematically than I am.
In a “meta” sense I’m “searching” about in logic-space for inference rules that might plausibly drive me closer to the goal state. Using your 3-empty-block example, first I have to notice those three blocks as a plausible region to explore. Then I have to “discover” the first-order implications of the three blocks’ possible values driven by the relevant filled-in squares. Then the second order implications driven by *those *implications. One of which is the statement “*This *empty box must be a 3” and thus we advance towards the goal state of a completely filled-in puzzle.
If my mind was a reliable iterative logic solver, it could brute force through the logic space, perhaps informed by heuristics such as “look at more densely populated regions of the puzzle first.” But it isn’t. Humans suck at brute force iteration. Not only are we slow, but over even a small *n *such as 10 we get bored (Squirrel!) or lose our place and skip number 7 unnoticed.
So things which aren’t properly “search” in the technical sense seem to be in an intuitive sense. At least to me. All of which underlines the point that lots of folks throughout the thread (certainly including me) are using words without rigorously defining them.
But I think that the opposite of logical was “only solved by trial and error”.
The opposite of trial and error is
“look at what is known , and thererby deduce the next square”.
There probably are ways to make 100% sure deductions from what is known that are highly inefficient, in that you have to compare so many cells so many times to make the deduction. I saw a sudoku solver expert’s website saying that he decides that some algorithms are just too inefficient even if they are sometimes, after much hunting, make deductions. Basically he says you may as well do trial and error if the algorithm is that inefficient so he doesn’t consider the inefficient algorithm (worse than trial and error) as a “solution”.
Let’s walk a bit through Sudoku solution by DNF expansion in this way. 9 by 9 is quite large; let’s consider a simpler 4 by 4.
The puzzle we’ll solve is this one:
? ? | 2 ?
2 ? | ? 1
----+----
3 ? | ? 4
? 4 | ? ?
We begin by encoding thing as a Boolean formula. We’ll use 4 * 4 * 2 variables: each row and each column has a value, which (in our convenient 4-ary rather than 9-ary case) we can directly encode with two bits: 01 for 1, 10 for 2, 11 for 3, and 00 for 4. So our 32 variables will be Row[sub]j[/sub]Col[sub]k[/sub]Bit[sub]b[/sub] where j and k range from 1 through 4, and b ranges from 1 (for the lower order bit) through 2 (for the higher order bit). [This is slightly different from the X[sub]i, j, k[/sub] variables you propose in post 76, but only in that we use a more efficient 2 bit encoding of our 4 possible values, instead the 4 bit encoding 1: 1000, 2: 0100, 3: 0010, 4: 0001]
I will write & for AND, v for OR, and ~ for NOT.
For convenience, I will write such things as “Row[sub]j[/sub]Col[sub]k[/sub] = 1” as shorthand for “Row[sub]j[/sub]Col[sub]k[/sub]Bit[sub]1[/sub] = 1 & ~ Row[sub]j[/sub]Col[sub]k[/sub]Bit[sub]2[/sub]” (i.e., we’ve encoded the value 1, with 1 as its lower-order bit and 0 as its higher-order bit, in the two bits for grid point (j, k)), etc.
What is the formula that encodes whether we have a valid Sudoku board? Well, it’s the conjunction of the following (4 + 4 + 4) * 4 = 48 constraints:
[ul]
[li]Row[sub]1[/sub]Col[sub]1[/sub] = 1 v Row[sub]1[/sub]Col[sub]2[/sub] = 1 v Row[sub]1[/sub]Col[sub]3[/sub] = 1 v Row[sub]1[/sub]Col[sub]4[/sub] = 1 (“The first row contains a 1”)[/li][li]Row[sub]1[/sub]Col[sub]1[/sub] = 2 v Row[sub]1[/sub]Col[sub]2[/sub] = 2 v Row[sub]1[/sub]Col[sub]3[/sub] = 2 v Row[sub]1[/sub]Col[sub]4[/sub] = 2 (“The first row contains a 2”)[/li][li]Row[sub]1[/sub]Col[sub]1[/sub] = 3 v Row[sub]1[/sub]Col[sub]2[/sub] = 3 v Row[sub]1[/sub]Col[sub]3[/sub] = 3 v Row[sub]1[/sub]Col[sub]4[/sub] = 3 (“The first row contains a 3”)[/li][li]Row[sub]1[/sub]Col[sub]1[/sub] = 4 v Row[sub]1[/sub]Col[sub]2[/sub] = 4 v Row[sub]1[/sub]Col[sub]3[/sub] = 4 v Row[sub]1[/sub]Col[sub]4[/sub] = 4 (“The first row contains a 4”)[/li][li]Etc. through all the ways to say “This row/column/block contains this value”[/li][/ul]
What happens when we multiply all these constraints together and expand out into DNF form?
We get, surely you will agree with me ftg, the disjunction (i.e., ORing together) of 288 terms, one term for each valid 4 by 4 Sudoku board. One of these terms, for instance is “Row[sub]1[/sub]Col[sub]1[/sub] = 3 & Row[sub]1[/sub]Col[sub]2[/sub] = 1 & Row[sub]1[/sub]Col[sub]3[/sub] = 2 & Row[sub]1[/sub]Col[sub]4[/sub] = 4 & Row[sub]2[/sub]Col[sub]1[/sub] = 2 & Row[sub]2[/sub]Col[sub]2[/sub] = 3 & Row[sub]2[/sub]Col[sub]3[/sub] = 4 & Row[sub]2[/sub]Col[sub]4[/sub] = 1 &
Row[sub]3[/sub]Col[sub]1[/sub] = 4 & Row[sub]3[/sub]Col[sub]2[/sub] = 2 &
Row[sub]3[/sub]Col[sub]3[/sub] = 1 & Row[sub]3[/sub]Col[sub]4[/sub] = 3 &
Row[sub]4[/sub]Col[sub]1[/sub] = 1 & Row[sub]4[/sub]Col[sub]2[/sub] = 3 & Row[sub]4[/sub]Col[sub]3[/sub] = 4 & Row[sub]4[/sub]Col[sub]4[/sub] = 2”, corresponding to that particular 4 by 4 Sudoku board. There are 287 other such terms as well.
Is this not what we would get by multiplying out these constraints, ftg? Is it not indeed the case that we will get a formula with precisely one term for each and every possible Sudoku board?
And then, what next? Oh, we have some more constraints to multiply in, because we were supposed to solve this particular board:
? ? | 2 ?
2 ? | ? 1
----+----
3 ? | ? 4
? 4 | ? ?
So we multiply in the constraint “Row[sub]1[/sub]Col[sub]3[/sub] = 2”. Out of our 288 terms, some are incompatible with this, and multiply with this to yield Falsehood, and thus disappear. The others are compatible with this, already containing it as a factor, and thus remain unchanged after we multiply it in. So we now reduce to a 72 term disjunctive formula, precisely one term for each and every possible Sudoku board with a 2 at row 1, column 3. Yes? You will agree with me that this is what we get, ftg? Next we multiply in the constraint “Row[sub]2[/sub]Col[sub]1[/sub] = 2”, and walk through these 72 terms, getting rid of the ones who have a 2 at location (2, 1) and keeping the rest. Etc., etc.
Finally, in the end, we end up with a single term, corresponding to our solution.
But how do we get there? We first enumerate all 288 possible 4 by 4 Sudoku grids. Then we go through them, one by one, and get rid of all the ones without a 2 at (1, 3), then get rid of all the remaining ones without a 2 at (2, 1), then get rid of all the remaining ones without a 1 at (2, 4), then get rid of all the remaining ones without a 3 at (3, 1), etc., etc. We go through all 288 possible 4 by 4 Sudoku grids and see which, if any of them, are compatible with our puzzle, and in this way find all its solutions.
This is precisely what happens, right? We go through all 288 possible 4 by 4 Sudoku grids and see which, if any of them, are compatible with our puzzle, and in this way find all its solutions.
Ok. Going through all 288 possible 4 by 4 Sudoku grids and seeing which, if any of them, are compatible with our puzzle, and in this way finding all its solutions, is disciplined, mechanical, and logically rigorous. I won’t dispute that. As to whether it’s the sort of thing “trial and error” is meant to denote, well, I’ll leave that to the reader.
It starts out normal and then …
Boy, do you go South and then some here.
Yes, you start with a small-ish, boringly generic Boolean formula. Not at all difficult, per se, just tedious.
You then replace (repeat, replace) the variables that have a known fixed value. If there is a 1 at x,y then the variable for 1 at that spot is replaced by true. The others for x,y are replaced by false. A trivial task.
Then, and only then, do you start multiplying out the formula to get a DNF formula. That’s where the real work happens.
At no time, in any way shape or form does the formula embody some sort of universe of all possible trial-and-error solutions to that particular single puzzle let alone all puzzles.
As you multiply out, the formula may grow to exponential size. But it may not! It might start shrinking down right away. (It’s this variability of things that makes the P=NP? question so hard.)
Again: General small formula. Replace initial terms for a specific puzzle. Multiply.
So “Is this not what we would get by multiplying out these constraints, ftg? Is it not indeed the case that we will get a formula with precisely one term for each and every possible Sudoku board?” Is utterly and completely false!
Your argument is very similar to claiming that finding solutions to a set of linear equations is trial and error. This is just scut (Boolean) algebraic manipulation, nothing more.
You never said anything about multiplying out our constraints in a particular order. But, sure, fine, we can substitute the particular puzzle’s given value constraints before, rather than after, multiplying out the generic Sudoku constraints.
But, again, this remains the very model of trial-and-error; it’s exactly the same as a backtracking brute-force exhaustive search. “Can I put a 1 here? Maybe. Let’s keep going and see if we hit a problem. [Later] Oh, that didn’t work. Ok, let’s try putting a 2 here. Keep going and see if it works.”.
Yes, it’s phrased in terms of multiplying out conjunctions of disjunctions to get disjunctions of conjunctions, but it’s the exact same thing. Each disjunction is just “Ok, here’s the possibilities to try”, and as you multiply them out to combine various possibilities, you kill them off just at the moment you find you’ve run into incompatibilities. The work you carry out is isomorphic to the work you’d any way carry out in a straightforward backtracking search through possibilities.
Unless you have access to some guiding hand telling you “Listen, your life will be easier if you look at this constraint rather than that constraint; follow them in this order rather than that order. It will end up cutting things down more nicely”. Sure, if there’s some oracle around to make those choices for you, guide you through the logic of some particularly nice inference chain they’ve found for it.
But just the fact that you can always encode the puzzle as a propositional logic problem and unthinkingly multiply out to DNF form? That’s nothing more than generic backtracking search. Which is what I would have to imagine “trial and error” ever meant to anyone.
What happens when you multiply out (A v B v C v …) & X [where X may itself be a conjunction of further disjunctions]? You get (A & X) v (B & X) v (C & X) v … . You get “Try A with further constraints X first; recursively multiply out A & X there, and if you find X is compatible with A, yielding a solution, great; otherwise, if the whole thing annihilates, bad luck, move on to trying B with X. Again, if you find X compatible with B, great, and if not, move on to trying C with X…”. This is just spelling out the backtracking search. This is just spelling out the trials (A, or B, or C) and errors (the products that end up annihilating to falsehood).
(I say “backtracking”, but also, if you had a bunch of friends, you could carry this out in parallel, making all choices simultaneously in different threads and waiting for some to die off while others persevere, instead of having just one exploring-and-backtracking thread.)
I’m not denying that Sudoku reduces to a generic propositional satisfiability problem, to which any of the techniques for solving propositional satisfiability problems can be applied. I’m just denying that the generic observation “Hey, we can always turn CNF formulae into DNF formulae by multiplying out, and then just read off the solutions!” is in any way fundamentally different from “Hey, we can always methodically try out each choice, killing off the paths of choices that run into errors, and what remains will be the solutions!”
They are more or less equivalent. There have been efforts to parallelize ATPG by assigning branches of a decision tree to different processors. But the tree grows very quickly, in the worst case, so you’ll need a lot of friends, and a lot of them will be standing around while the friend with the branch which is working plugs onward.
Yes. Trial and error can be algebraicized.
Can you solve A[sup]2[/sup] + B[sup]3[/sup] = 73 with A and B integers in the range from 1 to 5?
Dumb guy, using trial and error: Uh, well let’s see. Does it work for A to be 1 and B to be 1? Hm, no. Ok, can A be 1 and B be 2. Ah, that doesn’t work either. Can…
Smart guy, using algebra: Let’s expand out (x[sup]1[sup]2[/sup][/sup] + x[sup]2[sup]2[/sup][/sup] + x[sup]3[sup]2[/sup][/sup] + x[sup]4[sup]2[/sup][/sup] + x[sup]5[sup]2[/sup][/sup]) * (x[sup]1[sup]3[/sup][/sup] + x[sup]2[sup]3[/sup][/sup] + x[sup]3[sup]3[/sup][/sup] + x[sup]4[sup]3[/sup][/sup] + x[sup]5[sup]3[/sup][/sup]) and see if we get an x[sup]73[/sup] term in the resulting polynomial. It’s just scut algebraic manipulation! Certainly not trial and error!
And yet, as we go through distributing out the multiplication, it feels an awful lot like we’re just searching through all the possibilities. “Well, if we pick x[sup]1[sup]2[/sup][/sup] from the first factor and x[sup]1[sup]3[/sup][/sup] from the second factor, we get… nope, 1[sup]2[/sup] + 1[sup]3[/sup] isn’t 73. Ok, if we pick x[sup]2[sup]2[/sup][/sup] from the first factor and x[sup]1[sup]3[/sup][/sup] from the second factor, we get… nope, 2[sup]2[/sup] + 1[sup]3[/sup] isn’t 73 either. [Many steps later] Ah, yes, there is an x[sup]73[/sup] in the result, because of the x[sup]3[sup]2[/sup][/sup] in the first factor and the x[sup]4[sup]3[/sup][/sup] in the second factor!”. Oh, it feels an awful lot like ordinary searching, but… nope. Found it by pure algebra. Completely different! No trial and error here!