| View previous topic :: View next topic |
| Author |
Message |
Hollydoll
Guest
|
 Posted: Tue Oct 11, 2005 4:31 pm Post subject: Do I have to guess |
 |
|
This is a puzzle that appears ti only be solved by guessing, Is that correct?
123 845 976
x8x 962 143
694 731 285
x7x x8x x3x
x4x x2x x6x
x5x x1x x9x
x19 4x3 6x8
46x 1x8 3x9
x3x 296 714 |
|
| Back to top |
|
 |
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Tue Oct 11, 2005 5:20 pm Post subject: |
|
|
On a quick once over it certainly looks like it, Holly.
I'll do a bit more digging, but it doesn't look promising. dcb |
|
| Back to top |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Tue Oct 11, 2005 6:07 pm Post subject: Are "forcing chains" a form of guessing? |
|
|
After studying your question, this is the best I can come up with, Holly.
It's clear that the bottom row of 3x3 boxes can only interact with the rest of the puzzle via the middle left 3x3 box. Because the triplet {2, 5, 7} appears in rows 7 & 8, and because the pair {5, 7} appears in row 2, we can deduce that there are two valid states for the top left, bottom left, bottom center, and bottom right 3x3 boxes. Choosing either a "2" or a "7" for r8c1 will force this part of the puzzle into one of those two states. So a critical "guess" for the central part of the puzzle, which is more complex, might successfully be made starting with the {2, 9} pair in r4c1.
I learned that r4c1 = 9 by following a "forcing chain" --
r4c1 = 2 ==> r4c9 = 1 ==> r5c9 = 7 ==> r6c9 = 2
the "2" in r6c9 creates a {3, 6, 8} triplet in r6c1, r6c3, & r6c4, so we have
r6c9 = 2 ==> r6c7 = 4 ==> r4c7 = 5 ==> r4c4 = 6 ==> r4c3 = 2
This contradiction (two "2"s in row 4) proves that r4c1 = 9, and the rest of the puzzle is easily solved from there.
Note that one could also start a forcing chain from r5c3, since the state of the bottom row of 3x3 boxes causes r9c3 to be either a "5" or an "8", so that's how the middle row of 3x3 boxes connects with the rest of the puzzle. I'm not sure if that chain is shorter than the one I found, or not, because I didn't bother to trace it out. dcb
PS I'm not sure if you'd call this form of solving a Sudoku "guessing" or not. The steps I used are all logical, but there are quite a few of them, so maybe it was a "guess." Otoh, I didn't have to work all the way through the puzzle to obtain a contradiction, either. |
|
| Back to top |
|
|
alanr555
Joined: 01 Aug 2005
Posts: 198
Location: Bideford Devon EX39
|
| Posted: Thu Oct 13, 2005 6:41 pm Post subject: |
|
|
| Code: |
I put this one through the Step Solver. It stopped at the same point as
is portrayed and had the same candidate profiles as I developed looking
at it manually - fairly easy in this case!
The Solver then gives one the option of "guessing" a cell (which involves
making a change to the start grid!) or xx to automatic mode. The
latter does not give step-by-step commentary on-line but it DOES leave
an audit log of what it has done.
The log states that a procedure called "Ariadne's Thread" was used and
the detail shews that the program postulates a value for a cell and then
backs out if it finds a contradiction.
Here it tried the first cell that it encountered (r2c1) and tried value 5 in
that cell. During processing it found that r4c1 was also ambiguous and
so had to test each value (2,9) of that cell on the assumption of value
5 in r2c1. Both the sub-paths failed (by leading to a contradiction) and
so the program decided on value 7 for r2c1 and demonstrated that
this leads to a unique solution.
It is the certainty of a unique solution that is comforting here. There is,
though, the question of the logic in getting there. The computer chose
the first cell found and the first value found as its initial test. Our human
solver did some work on the puzzle and found that a particular cell (or
perhaps a couple of them) would be the critical choice. This demonstrates
a commendable (and qualitative!) distinction from the pure processing
power of the computer solver.
+++
The big quesion to be asked is whether IF-THEN logic is really distinct from
guessing and back tracking.
With IF-THEN one has to postulate a starting cell - here derived by logical
thinking rather than artifical choice (ie the first found!). So far so good!
Then the human explores the implications of the choice until a real
contradiction ensues - after which the postulation changes to the
the other alternative.
In the case of 5/7 in r2c1, this boils down to
IF 5 then a contradiction ensues
ELSE - meaning try value 7 - a valid solution arises.
The only difference with the computer system is that it takes a snapshot
at the end of the "normal" logic and returns to that check point if the
subsequent processing leads to a contradiction whereas the human has
to hold the implications in temporary storage until the contradiction is
exposed rather than writing onto the actual puzzle solution.
It is said sometimes that virtually all solution techniques are really
just IF/THEN logic as in "IF we put a 2 there THEN we cannot put a three
somewhere else ..." or "IF there is a 2 in that cell, THEN we cannot put
a 3 in this other one ...". Where does the definition stop?
My view is that we can allow "if there IS ..." but not "if there WERE TO BE ...."
In the current case we KNOW that r4c1 is 2 or 9. We cannot deduce which
value on the basis of the ACTUALITY of the value in another cell or even
of the notes that we add as humans or computers. We seem to NEED to
make the IF condition dependent upon the CURRENT cell value rather
than the value of a DIFFERENT cell.
As a working definition, I would propose that IF...THEN logic should be
deemed allowable (within the ethos of this site) provided that it does
not depend on a specific value being in any specific cell (other than the
actual UNALTERABLE values already developed as part of the solution).
Under that definition, I find this puzzle to be "cosa non grata" in that,
although it has a unique solution, it is not one that can be derived by
applying logic without assuming that a value is confirmed when it is merely a candidate.
+++
An important distinction must be made between logical rules where
compliance with a start condition independent of actual values leads to
an unvarying outcome AND rules where the outcome is dependent upon
the specific values of the start condition. The former are fully acceptable,
but the latter should not be in the context of THIS site..
Thus, I believe that, for example, the XY-wing IS allowable. It can be shewn by logical deduction that IF a specific pattern occurs (ie ab/bc/ca)
in the three corners of a rectangle then value of the fourth corner cannot
be the value common to the adjacent corners but absent in the opposite
corner. Although the proof depends upon IF/THEN assumptions, the outcome is a certainty in terms of the value always being excluded -
irrespective of the actual values in the adjacent corners.
Alan Rayner BS23 2QT
|
|
|
| Back to top |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Thu Oct 13, 2005 9:06 pm Post subject: What about Aristotle's law of the excluded middle? |
|
|
| AlanR555 wrote: | | My view is that we can allow "if there IS ..." but not "if there WERE TO BE ...." |
I disagree.
The first law of logic is that the values "true" and "false" are mutually exclusive. An unambiguous statement is either true, or it is false. There is no middle ground. That is why we call this rule "Aristotle's law of the excluded middle."
In symbolic logic we write this rule as
(A) or (not A)
THAT STATEMENT CANNOT BE FALSIFIED.
It appears to me that you're trying to draw a distinction between two different forms of this rule:
[(A) or (not A)] <==> [(not A) or (not(not A))]
In other words, it seems that you're trying to apply a grammatical rule (no double negatives!) to logic. I protest. Logic is not grammar. In logic, the negation of truth is falsity and the negation of falsity is truth, every time. dcb |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
