First off, let me state my question. Then, I will go on at length about the question's context, which will hopefully serve to clarify the question a little. Indeed, I understand that the question is very general and rather vague. It is this : "In sudoku, by what other ways can we find that (P implies Q) ?"

The question follows from a neat little thing that happened last night, after I finally had enough time to finish recoding my little sudoku solver. It came up with two nice little lines of output :

When confronted with :

100007090030020008009600500005300900010080002600004000300000010040000007007000300

Solver answered with :

162857493534129678789643521475312986913586742628794135356478219241935867897261354

And when confronted with :

001002000030040050500600300007000006080000040200000100006009007040070080000500900

Solver answered with :

871352469632948751594617328457231896189765243263894175326489517945173682718526934

Although many of you may consider this somewhat "dépassé", I consider it something of an achievement given the original approach Solver uses. Those of you who know these puzzles by their little names will have recognized "ArtoI's AI Etana" and "Ocean Anemone", and perhaps even noticed that Solver's answer was correct.

Sadly, Solver still fails to make good on tougher puzzles. Hence, my question. Now, to properly answer it, one must know a little more about how Solver goes about his business.

Solver is deceptively stupid. However, one thing Solver is not allowed to do, is "take a guess". Solver may only play moves which he knows, without a shadow of a doubt, to be correct, and Solver is never ever allowed to take back a move he has made.

Solver uses one main routine, and two simple upkeep routines. The first simple upkeep routine is to check for patterns which most if not all of you are very familiar : finding out naked or hidden singles, pairs, triples, quads, and finding out x-wings, swordfish and jellyfish. Solver considers these to be valid (and I daresay he's quite allowed to!), even though most of these patterns are completely alien to his main routine. These patterns, once checked, just make the main routine a little shorter to go through.

Solver's main approach, seeing as he is so deceptively stupid, is nothing less than brute-force. That's because Solver can't really tell whether what he's doing is really useful or not. It doesn't matter much to him how long it takes, as long as he gets there. All he needs to know is that a move is allowed. And even though Solver's approach is definitely brute-force, it is nonetheless purely deductive. And, mind you, Solver does come up with an answer in a sufficiently short amount of time for my tastes (i.e., under a minute).

Before I go into how Solver works, I need to take a little time to explain how Solver sees the problem of sudoku. Many of you may already be familiar with Solver's simplistic vision, which can be summarized by these two main tenets :

(A)

Solver considers the 9x9 puzzle to be a question about 729 "candidates", each "candidate" being a proposition (for lack of a better term) that says "value X placed in the cell (row Y, column Z) is true". Solver's objective is to show which 81 of these propositions are actually true.

(B)

Solver considers that these candidates are under 324 basic "constraints". 81 of these constraints are "row-value" constraints, 81 are "column-value", 81 are "box-value" and 81 are "cell" constraints. Each of these basic constraints governs, at the offset, 9 candidates. And each of these constraints has this to say about its nine candidates : "exactly one of my candidates is true" (for example : of the nine candidates that have the value X along row Y, exactly one is true). Therefore, another way of putting Solver's problem is, to show which candidate is actually true for all 81 constraints.

Now then, here is how Solver goes about his business :

1. After having run through his first simple upkeep routine stated above, Solver's introdution consists in identifying all the implications that are known "directly" from the constraints. These are :

1.a) Each candidate trivially implies itself. Thus, Solver notes for all remaining candidates, (X implies X) and (~X implies ~X).

1.b) Any two candidates that share a constraint exclude each other. This is given directly from the definition of the basic constraints : exactly one of the candidates is true. Therefore, for any two candidates X and Y that share some constraint, (X implies ~Y).

1.c) (edit...) Forgot to mention the very important point that Solver also notes, for any constraint having only two unsolved candidates X and Y remaining, that (~X implies Y).

(Although I may forget to mention it occasionnaly, let it be known that when Solver identifies any implication, he always also take note of the "contrapositive". The contrapositive of (X implies Y) is (~Y implies ~X).)

And now, Solver goes into his main routine :

2. "Collapse" all the implications he's found out about so far. Basically, at this point, Solver simply infers from his known combinations of ((X implies Y) and (Y implies Z)) what necessarily follows, that (X implies Z). Solver also goes through all the inverse/converse/whateververse of this, such as that from ((~X implies ~Y) and (~Y implies Z)), it necessarily follows that (~X implies Z). He does this until he can no longer identify any new relationships.

3. Use the force, Solver : given all the implications Solver has worked out, Solver makes any and all direct deductions and eliminations he can. These are all of the form : from ((X implies Y) and (~X implies Y)) it follows that (Y), and from ((X implies ~Y) and (~X implies ~Y)), it follows that (~Y).

(Those of you familiar with this approach will know that at this point, solver has worked out all "simple" chains. "Simple" in this case involves a lot of somewhat complicated stuff, such as many types of colouring for instance.)

If Solver finds anything worthwhile during step 3, he will execute his simple upkeep routine and then start back at 2. Otherwise, he moves on to...

4. Solver then checks for something unusual, which is actually a very limited generalization of step 3 : since he knows that exactly one candidate in a constraint is true, he can deduce readily that if a candidate X exists, such that X "sees" all the candidates Y of some constraint, then X must be false. "Sees" here simply means Solver has worked out that (X implies ~Y) for all those candidates. Solver also checks whether he can do the same thing with (~X implies ~Y), which will prove that X is true.

(This happens to be a generalization of what is often called "line-box reductions", but of course taking in much more than just lines and boxes. By the time Solver gets here, he may know that for a given Y, (X implies ~Y) only through some arbitrarily long chain of implications.)

Again, if something worthwhile happens, it's upkeep time and back to 2. Otherwise...

Here, Solver does something very unnecessary, but very cute. Which helps him tame the rather large number of combinations he's dealing with. It's the simple second upkeep routine, where Solver gets rid of redundant constraints and candidates. This operation does not add any information to what Solver knows, and therefore doesn't help directly, so I won't go into detail about it. It sets the ground for some serious candidate vs. constraint checking...

5. If Solver gets here, which he does (more than once, even!) for the two puzzles mentioned above, he's very desperate! Solver is now looking for candidate pairs for which he can identify a hitherto unknown relationship. This is actually a variant of 4, in which solver attemps to lock out a full constraint, but this time by using two candidates instead of one. While he's doing this, he will also identify a simpler form which presents itself at the same time. The simpler form is :

5.a) If some candidate X "sees" all but one candidate Y of some constraint, then Solver may infer that (X implies Y). A corresponding inference is also allowed if (~X) "sees" all but one candidate, for then (~X implies Y).

5.b) The more complicated case is when solvers finds that X "sees" more than one candidate in some constraint, but there are also more than one candidate that X does not "see". Solver then looks for another candidate, Y, such that Y "sees" at least all those candidates that X does not see. When he finds such a pair, Solver knows that (X implies ~Y). Solver also checks the other combinations, by trying to cover the constraint with (~X and ~Y), (X and ~Y) and (~X and Y), all of which lead to an inference, respectively : (~X implies Y), (X implies Y) and (~X implies ~Y).

If Solver finds anything, again, it's upkeep and back to 2.

Otherwise, Solver grumpily gives up the match.

But Solver would really really like to find more and different ways about how he can determine that (P implies Q). Could you help him ?

I like to delude myself into thinking that Solver deserves a little help, given what he has managed to achieve with so little!

And I will, of course, be glad to elaborate on what I've already said, rather quickly, if there are any questions about that.