The continuum of Sudoku logic.

Advanced methods and approaches for solving Sudoku puzzles

The continuum of Sudoku logic.

Postby tso » Sun Jul 10, 2005 9:21 pm

A brilliant logician, well versed in propositional logic and deductive reasoning, who has never heard of Sudokus before and never seen any of the information in these forums, who understands the rules of the puzzle completely, sits down to solve several of them.

Here are a few of the distinct situations she encounters:

(A) She narrows down the possibilities of three cells as shown:
Code: Select all
+------------+------------+------------+
| 12  12  13 |  .   .   . |  .   .   . |

She deduces:

1) r1c1=1 => r1c3=3
2) r1c1=2 => r1c2=1 => r1c3=3
3) Therefore, r1c3=3

[Note: When she writes "A => B", the "=>" means "implies that". She could have just as easily written: "If A, then B." Same thing.]


(B) She narrows down the possibilities of four cells as shown:
Code: Select all
+------------+------------+------------+
| 12  23  13 | 14   .   . |  .   .   . |

She deduces:

1) r1c1=1 => r1c4=4
2) r1c1=2 => r1c2=3 => r1c3=1 => r1c4=4
3) Therefore, r1c4=4


(C) She narrows down the possibilities of 7 cells as shown:
Code: Select all
+------------+------------+------------+
| 12  23  34 | 45  56  16 | 17   .   . |

She deduces:

1) r1c1=1 => r1c7=7
2) r1c1=2 => r1c2=3 = > ... => r1c6=1 => r1c7=7
3) Therefore, r1c7=7

[Note: if any one of the first 6 cells were removed, she could make no deduction about r1c7.]


(D) She narrows down the possibilities of 4 cells as shown:
Code: Select all
+------------+------------+------------+
| 12   .   . | 13   .   . |  .   .   . |
|  .   .   . |  .   .   . |  .   .   . |
|  .   .   . |  .   .   . |  .   .   . |
+------------+------------+------------+
| 23   .   . | 13   .   . |  .   .   . |


She deduces:

1) r1c1=1 => r1c4=3 => r4c4=1
2) r1c1=2 => r4c1=3 => r4c4=1
3) Therefore, r4c4=1


(E) She narrows down the possibilities of 4 cells as shown:
Code: Select all
+------------+------------+------------+
| 12   .   . | 13   .   . |  .   .   . |
|  .   .   . |  .   .   . |  .   .   . |
|  .   .   . |  .   .   . |  .   .   . |
+------------+------------+------------+
| 23   .   . | 34   .   . |  .   .   . |


She deduces:

1) r1c1=1 => r1c4=3 => r4c4=4
2) r1c1=2 => r4c1=3 => r4c4=4
3) Therefore, r4c4=4 [corrected -- thanks Doyle]

[Note: This case is distinct from (D) in than no two cells have identical possibilities. It is however essentially the same situation as (B) except that the cells with possibilities (23) and (13) are not in the same group and do not directly connect to each other.]


(F) She narrows down the possibilities of 8 cells as shown:
Code: Select all
+------------+------------+------------+
| 12   .  23 | 34   .   . |  .   .   . |
|  .   .   . | 45   .   . |  .   .   . |
| 14   .   . |  .   .   . |  .   .   . |
+------------+------------+------------+
| 24  25   . | 56   .   . |  .   .   . |


She deduces:

1) r1c1=1 => r3c1=4 => r4c1=2 => r4c2=5 => r4c4=6
2) r1c1=2 => r1c3=3 => r1c4=4 => r2c4=5 => r4c4=6
3) Therefore, r4c4=6


(G) She narrows down the possibilities of 8 cells as shown:
Code: Select all
+------------+------------+------------+
| 12   .   . | 34   .   . | 23   .   . |
|  .   .   . |  .   .   . |  .   .   . |
|  .   .   . |  .   .   . |  .   .   . |
+------------+------------+------------+
| 24   .   . |  .   .   . |  .   .   . |
|  .   .   . |  .   .   . |  .   .   . |
|  .   .  25 | 56   .   . |  .   .   . |
+------------+------------+------------+
|  .   .   . |  .   .   . |  .   .   . |
|  .   .   . | 45   .   . |  .   .   . |
| 14   .   . |  .   .   . |  .   .   . |
+------------+------------+------------+


She deduces:

1) r1c1=1 => r9c1=4 => r4c1=2 => r6c3=5 => r6c4=6
2) r1c1=2 => r1c7=3 => r1c4=4 => r8c4=5 => r6c4=6
3) Therefore, r6c4=6

===========================================================
Note: The logical connections between the cells are *identical* in (F) and (G). In each case, no two cells have the same two possibilities. If she refers to cells by their remaining possibilities, she can write the following for

BOTH examples:

1) (12)=1 => (14v=4 => (24)=2 => (25)=5 => (56)=6
2) (12)=2 => (23)=3 => (34)=4 => (45)=5 => (56)=6
3) Therefore, (56)=6
===========================================================


(H) She eliminates the possibility of the digit '1' from all but the 4 cells a, b, c and d in rows 1 and 4.

There is one other cell that might contain '1' in columns 2 and 5:

Code: Select all
+------------+------------+------------+
|  .   a   . |  .   b   . |  .   .   . | <-- only two spots for '1' in this row
|  .   .   . |  .   .   . |  .   .   . |
|  .   .   . |  .   .   . |  .   .   . |
+------------+------------+------------+
|  .   c   . |  .   d   . |  .   .   . | <-- only two spots for '1' in this row
|  .   .   . |  .   .   . |  .   .   . |
|  .   .   . |  .  13   . |  .   .   . |
+------------+------------+------------+
|  .   .   . |  .   .   . |  .   .   . |
|  .   .   . |  .   .   . |  .   .   . |
|  .  12   . |  .   .   . |  .   .   . |
+------------+------------+------------+

She deduces:

1) a=1 => r9c2=2
2) a/1 => b=1 => d/=1 => c=1 => r9c2=2
3) Therefore, r9c2=2

4) a=1 => c/=1 => d=1 => r6c5=3
5) a/=1 => b=1 => r6c5=3
6) Therefore, r6c5=3

[Here she is using "/=" to mean "is not equal to". Though she's never heard of an 'x-wing', she does notice that this formation is similar to (A).]


(I) She eliminates the possibility of the digit '1' from all but the 6 cells a through f in rows 1, 4 and 7.

There is one other cell that might contain '1' in column 2.

Code: Select all
+------------+------------+------------+
|  .   a   . |  .   b   . |  .   .   . | <-- only two spots for '1' in this row
|  .   .   . |  .   .   . |  .   .   . |
|  .   .   . |  .   .   . |  .   .   . |
+------------+------------+------------+
|  .   c   . |  .   .   . |  .   d   . | <-- only two spots for '1' in this row
|  .   .   . |  .   .   . |  .   .   . |
|  .   .   . |  .   .   . |  .   .   . |
+------------+------------+------------+
|  .   .   . |  .   e   . |  .   f   . | <-- only two spots for '1' in this row
|  .   .   . |  .   .   . |  .   .   . |
|  .  12   . |  .   .   . |  .   .   . |
+------------+------------+------------+

She deduces:

1) a=1 => r9c2=2
2) a/=1 => b=1 => e/1 => f=1 => d/=1 => c=1 => r9c2=2
3) Therefore, r9c2=2.

[She's never heard of a 'swordfish', she does notice how this is similar to (B).]


(J) She eliminates the possibility of the digit '1' from all but the 8 lettered cells in rows the noted

rows.

There is one other cell that might contain '1' in column 2.

Code: Select all
+------------+------------+------------+
|  .   a   . |  .   b   . |  .   .   . | <-- only two spots for '1' in this row
|  .   .   . |  .   .   . |  .   .   . |
|  .   .   . |  .   .   . |  .   .   . |
+------------+------------+------------+
|  .   c   . |  .   .   . |  .   d   . | <-- only two spots for '1' in this row
|  .   .   . |  .   .   . |  .   .   . |
|  .   .   . |  .   e   f |  .   .   . | <-- only two spots for '1' in this row
+------------+------------+------------+
|  .   .   . |  .   .   g |  .   h   . | <-- only two spots for '1' in this row
|  .   .   . |  .   .   . |  .   .   . |
|  .  12   . |  .   .   . |  .   .   . |
+------------+------------+------------+

She deduces:

1) a=1 => r9c2=2
2) a/=1 => b=1 => e/1 => f=1 => g/=1 => h=1=> d/=1 => c=1 => r9c2=2
3) Therefore, r9c2=2.


(K) In this case, all the lettered cells must be either 1 or 2, while r9c8 can be 1, 2 or 3:

Code: Select all
+------------+------------+------------+
|  .   .   . |  .   .   . |  .   .   . |
|  .   .   . |  .   g   . |  h   .   . |
|  .   .   e |  f   .   . |  .   .   . |
+------------+------------+------------+
|  .   .   d |  .   .   . |  .   .   . |
|  .   .   . |  .   .   j |  i   .   . |
|  .   c   . |  .   .   . |  .   .   . |
+------------+------------+------------+
|  .   .   . |  .   .   k |  .   l   . |
|  .   b   . |  .   .   . |  .   .   . |
|  a   .   . |  .   .   . |  .  123  . |
+------------+------------+------------+


She deduces:

1) a=1 => b=2 => ... k=1 => l=2
2) a=2 => b=1 => ... k=2 => l=1
3) Therefore, r9c8=3


(L) In this case, the same cells as in the above puzzle each of two possibilities:

Code: Select all
+------------+------------+------------+
|  .   .   . |  .   .   . |  .   .   . |
|  .   .   . |  .  78   . | 89   .   . |
|  .   .  56 | 67   .   . |  .   .   . |
+------------+------------+------------+
|  .   .  45 |  .   .   . |  .   .   . |
|  .   .   . |  .   .  12 | 91   .   . |
|  .  34   . |  .   .   . |  .   .   . |
+------------+------------+------------+
|  .   .   . |  .   .  23 |  .  13   . |
|  .  23   . |  .   .   . |  .   .   . |
| 12   .   . |  .   .   . |  .  19   . |
+------------+------------+------------+


She deduces:

1) r9c1=1 => r9c8=9
2) r9c1=2 => r8c2=3 ... [follow same logical path as in (K)] ... => r7c8=1 => r9c8=9


Each puzzle seemed brought new situations. She was able to build on what she learned solving the easier ones to use more complex logic to solve the harder ones. Though she often went back and solved them again, she NEVER found that a newer, more complex method replaced one that she had earlier found, even in a specific instance. She would use the methods she found easier until she could go no further, try something harder to push forward, then go back to the easier ones again.

She eventually worked on puzzle in which she was unable to reduce the possibilities for *any* of the cells to less than three -- but she was still able to crack them using more ingenious logical methods that I would like to explain here but there is no room in the margin.

Still, in the end, there was one puzzle that was so hard that she could make very little headway. Though she suspected it was very likely that there were methods yet undiscovered that would it to be simplified, and with experience, study and practice she would uncover them, for now, it was beyond her. She instead choose to solve this last one by what most people refer to as "trial and error" or "bifurcation" but is actually "proof by contradiction" or "Reducto ad absurdum".

She made an assumption and followed it until she found a contradiction, thereby enabling her to eliminate her assumption from the possibilities. While solving this one, she was forced to use *all* the skills she had learned early - in *addition* to making these assumptions. She enjoyed solving this one quite a bit. It wouldn't occur to her to use this tactic unless and until she could find no other way -- until she had *proved* to herself there was no other way.


When she had solved the last of the puzzles -- which was an enjoyable task for her -- she showed her solutions along with her methods for solving to several people far more familiar with Sudoku, many of whom are far more educated than she is and obviously very intelligent. She is told many strange things, conflicting things, including, but not limited to:

-- She "guessed" the answer in some of the puzzles.
-- She used "trail and error" in some of the puzzles.
-- She used methods that were "not elegant".
-- No one enjoys solving puzzles using some of the methods she used.
-- Though she solved them, some of the puzzles are "invalid" -- as no human could possibly solve them.
-- Many of the puzzles she solved are "not solvable by logic".
-- She "cheated herself" of the joy of solving some of the puzzle by "real logic".
-- All types of logic puzzles -- if correctly formed -- can always be solved by "just logic" and never
require methods analogous to some that she has used.
-- She used "inductive logic". (A claim she knows simultaneously false and pointless.)

Which puzzles were "invalid" and/or "not solvable by logic" varied from person to person. Which methods were "guessing", "not elegant" or "fun" varied from person to person. Which puzzles were "beyond
human ability" unless you drew lots of lines and charts, which is there for "not fun" varied from person to person.

Oddly, how subjectively difficult or how long it took to solve any individual puzzle seemed only loosely correlated to whether or not the puzzle was labeled "invalid" or not -- some of the "invalid" puzzles were actually easy.

Though this woman is imaginary, nonetheless, she came to me and complained about these ironically illogical statements about logic. She wondered what reasoning was behind trying separate into categories things that were so obviously one and the same, different only in degree, a continum of logic from simpler to more comlex. Would one differentiate 2*2=4 from 123*456=56088 simply because we *know* the first but must *calculate* the second? Does it change if we memorize that second product? Or if we forget the first for that matter? Is it more fun or elegant to fill in 3x2=6 than to perform multi-digit multiplication? Am I the only person that enjoys trying to muliply two 5 digit numbers in my head while stuck in traffic?

I asked "So what? You can solve as you like. What does it matter if so many others have it wrong?"

She agreed except for one thing. Some of the people who create these puzzles, who have decided arbitrarily what is and isn't a "valid" Sudoku, are treated as "authorities" -- by the press, by solvers, by other puzzle creators, many or most of which seem to be following suit, declaring certain constructions as "non-puzzles", "not solvable by logic", etc., though again, where each of them will draw the line is arbitrary.
Last edited by tso on Fri Aug 05, 2005 3:20 pm, edited 2 times in total.
tso
 
Posts: 798
Joined: 22 June 2005

Postby Karyobin » Tue Jul 12, 2005 9:06 am

Very impressive stuff, tso. References to Fermat, writing style suggestive of a Jonathan Livingstone Seagull complex. One huge error though...
She enjoyed solving this one quite a bit.


Good for her. Had I written your soliloquy I'd have been forced to write:
She was a bit disappointed by this.


No matter how you dress it up, the reason there is a debate is that there comes a tipping point on the 'continuum' ('Q' complex here?) when some people feel they've been cheated. Not because the methods, or the puzzle itself is, in some way, 'invalid' but because technique matters.

In all your logico-mathematic musings you have forgotten one important quotation, attributed to both Einstein and Dirac:
It must be beautiful.
Karyobin
 
Posts: 396
Joined: 18 June 2005

Postby Pappocom » Wed Jul 13, 2005 3:01 am

normxxx, your contribution has been moved to the Solver Programs forum.

- Wayne
Pappocom
 
Posts: 599
Joined: 05 March 2005

Postby tso » Thu Aug 04, 2005 4:03 pm

Karyobin wrote:No matter how you dress it up, the reason there is a debate is that there comes a tipping point on the 'continuum' ('Q' complex here?) when some people feel they've been cheated. Not because the methods, or the puzzle itself is, in some way, 'invalid' but because technique matters.


Hasn't that 'tipping point' moved quite a bit since Sudoku emmigrated from Japan -- even in just the 3 weeks since I posted this?


Karyobin wrote:In all your logico-mathematic musings you have forgotten one important quotation, attributed to both Einstein and Dirac:
It must be beautiful.


As the eye of the beholder becomes trained, what was ugly may become beautiful.


(I've only seen the original series and the movies. Is that "Q" reference a good thing or a bad thing?)
tso
 
Posts: 798
Joined: 22 June 2005

Postby Karyobin » Thu Aug 04, 2005 4:44 pm

Oh dear. Sorry for sounding so forceful, three weeks is a long time in trial and error though eh?:)

Has the tipping-point moved - absolutely, and it's been fun to watch. Still, for the time being Forcing Chains are about as far down the T & I road as I'd like to go.

As the eye of the beholder becomes trained, what was ugly may become beautiful.


Well my eye's going to have to become pretty trained in order for me to appreciate the kind of "Oh well, it's one of two options so off we go..." T & I approach that I envisaged when I wrote that!

However, bearing in mind the invention and undeniable practical use of Forcing Chains and Turbot Fish, amongst others, I do wonder whether the problem with genuine T & I lies in the fact that 'normal' people can't hold all the steps in their minds at any single point (possibly because it's impossible to know how many steps will/won't lead to a result). This may lead to a feeling that one has somehow lost touch with the puzzle in a way that does not occur with the other more defined /refined strategies.

Bum, the cricket's rained off.

BRING IT ON!!!



P.S. Oh yeah, about the 'Q'-complex thing - not bad as far as I'm concerned, I definitely suffer from one.
Karyobin
 
Posts: 396
Joined: 18 June 2005

sorry to Quibble...

Postby Doyle » Thu Aug 04, 2005 6:29 pm

... but in Statement 3 of Example E (of the original post), r4c4 = 4, not 1

As to the broader issue, I'm more with Karyobin, if only because resorting (my bias shows) to T/E inhibits finding more direct processes. Would the fish be in our aquarium otherwise?
Doyle
 
Posts: 61
Joined: 11 July 2005

Postby stuartn » Thu Aug 04, 2005 10:10 pm

Our piscatorial friends (IMHO) are perhaps the limit of what we can achieve without resorting to T&E techniques. I personally am at a loss here - is forcing valid because it reflects the investigative nature of the solving process - or is it invalid because it involves chance? very tricky -

Stuart

www.brightonandhove.org

I'm sure there's another tinnie in the fridge.
stuartn
 
Posts: 211
Joined: 18 June 2005

Postby Karyobin » Thu Aug 04, 2005 10:56 pm

Just two points:

1. What's (IMHO) stand for? I know I should know, but the pixie gibbereth...

2. Chance? I may have misunderstood, but surely the only manifestation of chance is in which chain you (the protaganist) pick; there surely can't be any chance in sudoku other than that we take with us...



Wow. Don't know where that came from. Maybe from that bit in The Empire Strikes Back...
Karyobin
 
Posts: 396
Joined: 18 June 2005

IMHO

Postby Doyle » Fri Aug 05, 2005 12:01 am

In My (stuartn's) Humble Opinion.
Doyle
 
Posts: 61
Joined: 11 July 2005

Postby DAAVE » Fri Aug 05, 2005 12:31 am

i stopped reading at the thought of a logical woman.

seriously though, why can't trial and error be considered a form of logic?
sometimes it's the only way to win on minesweeper.


i think it is acceptable only as a last resort.
DAAVE
 
Posts: 3
Joined: 02 August 2005

Postby PaulIQ164 » Fri Aug 05, 2005 12:40 am

So far as I can tell, the first three deductions can be rephrased in a way that doesn't involve any conditional statements (e.g., in situation B, the logic is that r1c1, r1c2 and r1c3 are three cells with three candidates between them, therefore must contain some permutation of 123, and therefore r1c4 cannot conatin 1 2 or 3, so must be 4). Once you get to D and beyond, I can see no way to make the deductions without using conditional statements (if-thens or '==>'s). Doesn't this offer a point at which you could be justified in saying there's a break in the continuum, and that perhaps logic at the other side of it is not valid (beautiful fun, whatever)?
PaulIQ164
 
Posts: 533
Joined: 16 July 2005

Postby stuartn » Fri Aug 05, 2005 8:08 am

Karyobin wrote:

Chance? I may have misunderstood, but surely the only manifestation of chance is in which chain you (the protaganist) pick; there surely can't be any chance in sudoku other than that we take with us...


Agree - perhaps chance isn't the right way of putting it - the contents of the fridge were distracting my thought process. PaulIQn was on the wavelength though with the comment regarding conditional arguments.

stuartn

www.brightonandhove.org
stuartn
 
Posts: 211
Joined: 18 June 2005

Postby Wolfgang » Fri Aug 05, 2005 8:26 am

PaulIQ164 wrote:...I can see no way to make the deductions without using conditional statements (if-thens or '==>'s). Doesn't this offer a point at which you could be justified in saying there's a break in the continuum...

Dont think so. Eg turbot fish or xy-wing are based on that conditional statements. But because they are proved as technique, you dont need the if-thens anymore. You only have to recognize the pattern and can eliminate this or set that number (and with some practice you will recognize them).
On the other hand, in the extreme you can invent a "technique" for each solvable puzzle by postulating, this pattern has this solution.
But i think, there is much common sense of how hard a puzzle is. Because of this it is very annoying for me, when i find "evil" puzzles that are very simple and on the same site an evil one that needs a forcing chain over 20 cells.
Wolfgang
 
Posts: 208
Joined: 22 June 2005

Postby Karyobin » Fri Aug 05, 2005 9:53 am

DAAVE: T & E is considered logic, it's just that some (myself included) feel it unattractive, possibly because, as you yourself phrased it, it's generally a last resort. But this debate has raged, then throbbed, and now only resurfaces occasionally. By and large we generally agree (now we're in our dotage) that it's amore a case of horses-for-courses.

The rest of you: I 'm a pattern-spotter by nature. I like nothing better than to use some of the candidate patterns you lot have developed to solve these things. Essentially, if I can't see where a construct begins and ends before I start along a line of reason, I tend to not want to use it.

Doyle: I knew I should have remembered what IMHO meant. Cheers.



Anyway, the choice is: Breakfast or Cricket?

BRING IT ON!!!
Karyobin
 
Posts: 396
Joined: 18 June 2005

Postby PaulIQ164 » Fri Aug 05, 2005 2:17 pm

Wolfgang wrote:Dont think so. Eg turbot fish or xy-wing are based on that conditional statements. But because they are proved as technique, you dont need the if-thens anymore. You only have to recognize the pattern and can eliminate this or set that number (and with some practice you will recognize them).


But just because you recognise and have named the piece of conditional logic you're using, does that really stop it being conditional?
PaulIQ164
 
Posts: 533
Joined: 16 July 2005

Next

Return to Advanced solving techniques