View previous topic :: View next topic |
Author |
Message |
alanr555
Joined: 01 Aug 2005 Posts: 198 Location: Bideford Devon EX39
|
Posted: Tue Nov 01, 2005 1:02 am Post subject: Re: Look-ahead logic |
|
|
Code: |
> People who criticize "trial and arror" are being imprecise in their
> thinking. Every move in a Sudoku puzzle involves some degree of
> looking ahead, and the question is how much.
The "Trial and Error" question is not about how far ahead one looks but
about the "initial suppositions" made.
Use of "Is it 'A' or is it 'not-A'?" comes well within the logic category in my
book. What does not is "Is it 7 or is it 3?" where one is testing specific
values.
I believe that my idea is precise - although I have some difficulty in
expressing it, given past reactions.
A "NON-TE" solution is one where a "rule" can be devised which does
not involve positing a specific value for a cell and then "back-tracking"
to that same cell and positing another value if the first one leads to a
contradiction.
A "TE" solution does precisely what is excluded above. It posits a specific
value for a cell (albeit one taken from the candidate profile for that cell)
and thenproceeds to "solve" the puzzle until it comes to a contradiction
when it concludes that the first assumption was false.
Techniques such as 'slicing/dicing' do not depend upon positing any
values for any cells - they refer to the fact of a value being present.
Very often in solving a puzzle, one is "considering" a specific digit. This
is NOT the same as positing it in a a specific cell. eg: If one of the cells
in column 1 contains a '9' then the value '9' cannot appear in any other
cell in column 1. Although this refers to a specific value (9) it is not TE -
merely the manifestation/implementation of a general rule in the context
of considering one particular digit. One is starting with the "KNOWNS" of
cells already resolved to '9', the occupation of some cells by digits other
than '9' and the presence/absence of digit '9' in the candidate profiles
of the unresolved cells plus other patterns of candidate profiles - based
on number of candidates and number of occurrences.
Logic of the type "Cell P has value A and so cell Q cannot be A" is quite
different to "Assume that Cell P has value A and check whether this
prevents completion of the puzzle without violating the "1-9 in every
row/column/region" rule.
If anything the distinguishing feature of TE is probably the theme of being
able to "backtrack" (ie resolve cells temporarily on the basis of an
assumption but de-resolve them if a contradiction ensues).
This is quite different to the use of "follow until contradicted" logic in
techniques such as forcing chains and colouring. Whilst the follow through
to contradiction is necessary to prove the technique as a technique, the
application does not involve the need for backtracking. What is required
is recognition that certain patterns are present in the puzzle and then a
knowledge of the implications (eg if a particular digit appears in columns
1 and 2 but not in column 3, one of the unresolved cells in column 3 must
contain that digit). To prove such a rule may well require the use of the
"reductio ad absurdum" logic but application of the rule does not.
With forcing chains, it is necessary only to demonstrate that each member
of the chain is connected by a "binary link" to one or two companions and
then to find the actual value of just one member of the chain. This is not
TE - unless one 'guesses' a member cell!
Thus I suggest that one is not being imprecise in claiming that there is
a distinction between 'trial and error' and other methods. It is not the
'looking ahead' that is significant, it is the making of an assumption
about the value of an particular cell and allocating a value to another
cell on the basis of one initial assumption being correct.
Alan Rayner BS23 2QT
| [/code] |
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich
|
Posted: Tue Nov 01, 2005 7:23 am Post subject: |
|
|
Hi,
I have a nice collection, of the ones I did not manage ...
I keep them as a source of inspiration.
You want one? Some?
see u,
P.S. they are all like bottles of old wine. You don't open all of them simultan. I take them one by one. With a pice of cheese. |
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
AZ Matt Guest
|
Posted: Tue Nov 01, 2005 8:40 pm Post subject: |
|
|
To someone_somewhere
Please post a good one, but not too good (start with a classic Calafornia vintage, save the Lafitte Rothschild '63 for later)
To Alanr55
Can there be a logical guess, a method to one's madness, a unified theory of chaos??? Perhaps what was meant by the comment that your definition was impercise was that it was, in fact, entirely too percise. Science and art often overlap. It was Plato who first conceptualized a universe made up of relatively infinitesimally small parts. (The parts were actually smaller than he guessed -- but hey, what a guess!!!) |
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich
|
Posted: Tue Nov 01, 2005 8:58 pm Post subject: |
|
|
Hi,
Let's start with a simple one, just to warm up:
500000000
400070006
908405000
010003090
005209600
040800020
000604503
700020004
000000009
feel free to use techniques like:
- Column on 3x3 Block interaction
- Row on 3x3 Block interaction
- Hidden Pair
- Nacked Pair
- X-wing on column and
- XY-wing
to get to the solution
see u, |
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich
|
Posted: Tue Nov 01, 2005 9:07 pm Post subject: |
|
|
Hi,
Now that you are warmed up, let us take the one published (by mistake) on 30 Sep 2005 in USATODAY:
123045000
000000000
600700200
070080030
040020060
050010090
009003008
000000000
000290714
After a couples of:
- Row on 3x3 Block interaction and
- Column on 3x3 Block interaction
you will have to use something different for "putting" the last 28 numbers.
I did not continue, but there are some 24 cells with only two candidate numbers for them. So, probable no big deal.
Tell us, what technique you have used.
see u, |
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich
|
Posted: Tue Nov 01, 2005 9:17 pm Post subject: |
|
|
Hi,
To keep you at the same level, here an other one:
000005020
090800000
010700000
200000070
000009400
000030000
000060140
500200000
000000900
a nice 17 cell Sudoku.
Here you can spot some hidden pairs and triples (if you did not drink to much wine). You can see also some nacked pairs (numbers, not humans).
After findung 33 numbers, you get to a candidate table with almost all cells having 2 possible digits.
Should not be a big problem to knack it.
see u, |
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich
|
Posted: Tue Nov 01, 2005 9:21 pm Post subject: |
|
|
Hi,
Now you need a fish for the wine.
Let's take a swordfish from the menu:
050400000
000030800
000000001
300080700
060000050
000200000
000506040
108000300
000000000
Tip: look for the digit 7.
see u, |
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich
|
Posted: Tue Nov 01, 2005 9:29 pm Post subject: |
|
|
Hi,
Now we finished the apperitives and starters.
Something still very light:
000000000
086000210
300107009
700302001
023000760
600704003
800609005
059000370
000000000
You could detect the taste of: hidden pair, X-wing on Column, XY-wing and Swordfish on Row.
see u, |
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich
|
Posted: Tue Nov 01, 2005 9:43 pm Post subject: |
|
|
Hi,
OK, now it cames the staff for someone better than me:
370600000
009000000
020080650
000005000
060010080
000400000
098020040
000000300
000007012
I put 3 numers, one 6, one 8 and one 5. And that was it.
There are only 57 left.
P.S. I have also a couple of Sudoku, for which I was not even able to pin ONE SIGLE (bloody) digit in some empty cell. I was sober, otherwise some random setting would have matched.
good look and
see u, |
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Wed Nov 02, 2005 12:59 am Post subject: Re: Lookahead logic |
|
|
AlanR555 wrote: | The "Trial and Error" question is not about how far ahead one looks but about the "initial suppositions" made ... |
Well, I'm probably beating a dead horse, but I'll try to explain why your notion about "initial suppositions" is vacuous.
1. Every move in a Sudoku puzzle involves some degree of looking ahead. Let's take the simplest possible situation, which might look something like this:
Now you will certainly deduce that the value of "?" must be "1". But how did you make that deduction? By looking ahead one move and seeing that if you place any other value in that spot a contradiction will result. In other words the two trains of thought "'?' must be a '1'" and "'?' cannot be a '2' nor a '3' nor a '4' nor a ... nor a '9', and must therefore be a '1'" are logically equivalent.
2. Let's take a slightly more complicated example. Imagine the grid looks like this:
Code: | . 8 . . . . . . .
. . . . . . . 2 .
. . . . . . . 3 .
. . . . . . . . 9
. 3 5 . 7 6 . 4 2
. . 8 . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . 8 |
My question is, would the guy who immediately places a "9" at r5c1 be making a "supposition," or not?
3. I could make up even more complex examples to illustrate my point, but I don't think it's necessary. The simple fact is that some people can "see" many moves farther ahead than either you or I can. To someone who can apprehend in a few seconds why it's impossible to place any other value than the one he chooses in a particular cell, there's absolutely no "supposition" about it -- he simply notices the impending contradiction and avoids it. And that's exactly what you did when you chose to replace the "?" with a "1" in my first example, or what you might do when you choose to place a "9" at r5c1 in my second example.
I'll repeat what I said earlier -- it's not "trial and error" if one can see all the logical implications of a particular move and choose the right number to put into some cell. It's only "trial and error" if one guesses blindly. And "supposition" has nothing to do with it. dcb |
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
alanr555
Joined: 01 Aug 2005 Posts: 198 Location: Bideford Devon EX39
|
Posted: Wed Nov 02, 2005 6:17 am Post subject: Re: Look-ahead logic |
|
|
Code: |
I'm curious what you'll have to say about this puzzle:
400 000 001
080 400 000
000 000 000
000 700 850
001 900 000
200 000 000
030 006 080
600 010 400
000 020 000
+++
Thank you for this puzzle. It led me to develop a new technique.
Using the standard techniques I reduced it to a puzzle with fifty cells
resolved as follows:
460 208 001
180 400 200
020 100 048
946 731 852
001 902 004
200 604 910
732 546 189
690 017 420
014 029 000
I looked for a way forward not involving Trial and Error - having
checked that I had a congruent set of candidate profiles as follows.
- - 3579; - 79 -; 357 379 -;
- - 3579; - 679 35; - 3679 3567;
35 - 79; - 679 35; 67 - -;
---;---;---;
38 57 -; - 58 -; 67 367 -;
- 57 38; - 58 -; - - 37;
---;---;---;
- - 58; 38 - - ; - - 35;
58 - - ; 38 - - ; 3567 367 3567;
I noticed that a lot of the profiles had just two candidates and after some
trials came up with the following method.
1) Compile a grid of the cells with just two candidates.
- - -; - 79 -; - - -;
- - -; - - 35; - - -;
35 - 79; - - 35; 67 - -;
---;---;---;
38 57 -; - 58 -; 67 - -;
- 57 38; - 58 -; - - 37;
---;---;---;
- - 58; 38 - - ; - - 35;
58 - - ; 38 - - ; - - -;
To be effective this MUST be with a congruent grid - after clearing
any hidden pairs etc lurking in it so as to maximise the number of
occurrences with just two candidates.
2) Identify any two cells with a large separation.
I chose r2c6 and r8c9 for this purpose.
3) Plot TWO routes using binary chains between the two cells but with
the following special features.
a) Each of the two routes (which may have by-ways!) must start from
the same cell but be distinguished by assuming ONE of the two
candidates as the "entry" value for that cell.
b) The "next" link in the chain shall be based on the value of the
candidate that is NOT the "entry" value. (ie if a cell has a profile
of AB and an entry value of A, then the next link should be for
value B - which will be the 'entry' value for the next cell.)
4) Only one successful route is needed for each initial value. If both
values have a successful route then NO information has been gained
and the only recourse is to select another pair of cells for testing or
to give up on believing that this technique is relevant for the case.
The same options apply if NO route can be found. The objective is
to find a route for ONE value and to demonstrate that there is no
route for the other initial value.
5) If just one initial value has a successful chain, the values used for
that route should be considered as "resolved".
Using the xample here:
Starting with value 3 as a possibility for r2c6 the chain becomes
r2c6 to r3c6 using 5
r3c6 to r3c1 using 3
r3c1 to r9c1 using 5
r9c1 to r8c3 using 8
r8c3 to r8c9 using 5
This is successful and so '3' is a possible value for r2c6.
Starting with value 5 as a possibility for r2c6 the chain becomes
r2c6 to r3c6 using 3
r3c6 to r3c1 using 5
r3c1 to r5c1 using 3
r5c1 to r6c3 using 8
r6c3 to r6c9 using 3
This is then a choice of route - to r5c7 or r6c2 using 7 in each case.
r6c9 to r6c2 using 7
r6c2 to r5c2 using 5
r5c2 to r5c7 using 7
This joins the shortcut from earlier (both arriving on 7)
r5c7 to r3c7 using 6
r3c7 to r3c3 using 7
This is a "dead end" as there is no link from r3c3 using 9.
As this is unsuccessful, value '5' is NOT a possible value for r2c6.
Accordingly we are able to set r2c6 as 3 and also
r3c6 as 5
r3c1 as 3
r9c1 as 5
r8c3 as 8
r8c9 as 5
These values are sufficient to progress the puzzle and allow completion
using the standard techniques.
+++
It is accepted that there is an element of 'trial and error' in this approach
but the crucial factor is that no values are allocated to any cells until
after confirmation of the success of the exercise and there is definitely
no backtracking (ie the method of assuming something to be true until
proven otherwise is NOT used).
Incidentally my former occupation was "systems analyst" but I am now
on "Incapacity Benefit" arising from my unfitness for full-time work. I
have never been an engineer and my programming skills are very
limited indeed. Thus my interest is in developing the methodology for
potential use by humans rather than programming it.
Alan Rayner BS23 2QT
|
|
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich
|
Posted: Wed Nov 02, 2005 6:41 am Post subject: |
|
|
Hi Allan,
After getting to the position:
460208001
180400200
020100048
946731852
001902004
200604910
732546189
690017420
014029000
there is an other way. The "easy" way is "hard" to find:
5 not in r5c1, it is in r5c2 or r6c2 (Column on 3x3 Block interaction)
5 not in r6c3, it is in r5c2 or r6c2 (same)
7 not in r6c3, it is in r5c2 or r6c2 (same)
5 not in r1c5, it is in r2c6 or r3c6 (same)
5 not in r2c5, it is in r2c6 or r3c6 (same)
5 not in r3c5, it is in r2c6 or r3c6 (same)
3 not in r3c3, Nacked Pair 3 5 in r3c1 and r3c6 (same Row)
5 not in r3c3, Nacked Pair 3 5 in r3c1 and r3c6 (same Row)
3 not in r3c7, Nacked Pair 3 5 in r3c1 and r3c6 (same Row)
5 not in r3c7, Nacked Pair 3 5 in r3c1 and r3c6 (same Row)
3 not in r6c9, XY-Wing X=5 Y=8 in r8c3; X=5 Z=3 in r8c9; Y=8 Z=3 in r6c3;
7 in r6c9 - Sole Candidate
...
So, if you know the XY-Wing and "see" when it is there, you can safe other, more advanced techniques for later use.
see u, |
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
alanr555
Joined: 01 Aug 2005 Posts: 198 Location: Bideford Devon EX39
|
Posted: Wed Nov 02, 2005 6:42 am Post subject: |
|
|
Code: |
> It is just an x-y wing, but it does solve 15 cells.
I still do not get WHERE the XY-wing is situated.
I solved it without using any advanced techniques other than the "new"
one (routing) included in another post.
> To get to this information is fairly easy:
r2 = *****{35}***
r3 = {35}****{35}***
r5 = {38}{57}**{58}****
r6 = *{57}{38}*{58}***{37}
r8 = **{58}{38}*****{35}
r9 = {58}**{38}*****
++
I agree with the above candidate profiles being the pairs.
> So you know from looking at this that if you solve one, you solve all.
How come? I did not know it!
> And there is an imbalance -- there is a non-repeating pair and
> two "unlinked" cells (naked pairs).
Which cells are these? (references please)
> If there wasn't, there would be no reason to look at the puzzle this way
> because you would know that you can't solve anything. So the key to
> the solve is in the 37 and 35 in column 9, and you can see that if you
> had a seven in r6c9, you'd have to have two 5s in r8.
This is not at all obvious.
I have a 7 in r6c9 in my full solution and only one '5' in row 8!!
> Again, as I see now this is just a back door x-y wing -- you can rule out
> the 3 in r6c9 that way using just the information in rows 6 and 8.
I do not see that. However using r6c2,r6c9 and r8c9 as the three corners
of an XY-wing it looks possible to eliminate the '5' from r8c3 and this
leads to quite a number of resolutions. Looking again at the rectangle,
I see now that the 3 in r6c9 comes from changing one's perspective
by using r6c3, r8c3 and r8c9 as the corners.
+++
Thank you for the commentary.
I missed the XY-wing.
Are there any tips on how to spot them easily??
Alan Rayner BS23 2QT
|
|
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
alanr555
Joined: 01 Aug 2005 Posts: 198 Location: Bideford Devon EX39
|
Posted: Wed Nov 02, 2005 7:56 am Post subject: Re: Lookahead logic |
|
|
Code: |
> 1. Every move in a Sudoku puzzle involves some degree of looking
> ahead. Let's take the simplest possible situation, which might look
> something like this:
> ? 2 3 4 5 6 7 8 9
> Now you will certainly deduce that the value of "?" must be "1".
> But how did you make that deduction?
> By looking ahead one move
No. I did not look ahead to anything.
I used the information given and what is termed "counting" OUTSIDE the
Sudoku grid to determine that '1' is the missing number from the
string 123456789. In computer terms that would be a 'string comparison'.
I certainly did NOT work on the principle of
Let's try a '9' and see if it conflicts. Ah it does. Lets try an '8' etc - which
is what I mean by suppositions. In the case of one line like this the
situation is trivial. Trial and Error would mean (to my mind) putting
a value in the box and then "erasing" it later if a logical inconsistency
arises. Almost a priori this demands that one is concerned with more
than one cell an so I will pass to the next example.
> and seeing that if you place any other value in that spot a contradiction > will result.
Your mind may work that way. Mine does not.
> In other words the two trains of thought "'?' must be a '1'" and "'?'
> cannot be a '2' nor a '3' nor a '4' nor a ... nor a '9', and must therefore
> be a '1'" are logically equivalent.
Yes if the universe is 123456789, they are equivalent.
However at no point have I filled in a cell with the possibility that I may
have to change it later. I put in a '1' and stick by it - no changes!
I do not assume that '1' is correct. I apply logic (outside the grid!) and
then state categrically (without fear of contradiction!) that value 1
is what must go in that cell.
+++
> 2. Let's take a slightly more complicated example. Imagine the grid
> looks like this:
. 8 . ; . . . ; . . .
. . . ; . . . ; . 2 .
. . . ; . . . ; . 3 .
. . . ; . . . ; . . 9
. 3 5; . 7 6 ; . 4 2
. . 8 ; . . . ; . . .
. . . ; . . .; . . .
. . .; . . .; . . .
. . .; . . .; . . 8
> My question is, would the guy who immediately places a "9" at r5c1 be > making a "supposition," or not?
I would not dare to do so.
The 'count' on row 5 indicates that there are three values missing (as
six present taken from nine leaves 3). A comarison of the values present
indicates that 1,8,9 are missing.
It is clear that value 8 cannot be used as '8' is already present in the box.
This leaves 1 and 9 as candidates.
I have no information on which to base the exclusion of '1' and so I
would leave both numbers as candidates.
The middle left box has six spaces remaining. We know that 2,4,6,7
must appear within that box but cannot be in row 5 and so must be in
either row 4 or row 6 - with UNKNOWN distribution between the two.
Taking '4' as the member of that group that is not placed in columns
2 or 3 (just an example, it could be any of them) we have numbers
1,4,9 to be fitted into colum 1 in that box. Digit '9' cannot go in row 4
and so the possible combinations are 194 and 419.
I do not see any constraint to either combination but there may well be
some logical rules which prevent the 419 combination in column 1.
Thus, I would marvel at the person able to apply that logic. For me it
would be guessing. The important thing is to apply the logic and then to
commit to the result - with no possibility of later amendment. As soon as the potential for backtracking is admitted, the context changes to one
of trial and error.
So, I would ask the person who places the '9' directly in r5c9 to demonstrate the logic behind her/his action. I admit that I may not
understand it because I do not think in terms of "moves". Moves are
relevant in chess. Sudoku has placements or resolutions and each
placements makes future placements easier (or at least no harder).
Unlike Chess a placement is either right or wrong. The only differences
between solvers of the same sudoku puzzle are the SEQUENCE of their
placements and the time taken to solve the puzzle. Aside from that are
the decision-making processes adopted and any aids (such as candidate
profiles or other "pencil marks") that may be used but they are in one
sense peripheral to the actual commitment of a digit to a cell.
> 3. I could make up even more complex examples to illustrate my point, > but I don't think it's necessary. The simple fact is that some people
> can "see" many moves farther ahead than either you or I can.
I do not know about you but for me this is undoubtedly true as I cannot
see even one move ahead.
> To someone who can apprehend in a few seconds why it's impossible to
> place any other value than the one he chooses in a particular cell,
> there's absolutely no "supposition" about it -- he simply notices the
> impending contradiction and avoids it.
OK - but such person is not adopting trial and error. She/he is applying
logic, and I have no objection to that. If the player COMMITS to a value
that is fine - so long as that is based on whatever logic she/he has to
hand and it is accepted that no change is permissible.
In the second example, if the thought process is
"Lets try putting a '1' in r5c1 and if it goes wrong later we can try it as
as a '9' in that cell" then that is trial and error because the personis
positing a specific value. This is in stark contrast to the logical approach
which says that "Value '1' must go there as all the other digits have been
allocated.". We do not 'Try 2' but have real reasons within the limits of
our own logical ability (not all can be Star Trek Vulcans!!).
> And that's exactly what you did when you chose to replace the "?" with
> a "1" in my first example
No. I did not. I applied a logical rule with NO trial or error involved. The
logic was applied outside the grid - taking the given information and
manipulating it. The analogy is with a computer that does its calculations
before writing the result to a hard disk or onto paper. It is given some
logical rules. It goes to the hard disk, extracts the data items that it
needs, manipulates them in memory by applying the logic of a program,
reaches a conclusion and writes a result just before clearing the memory
ready for the next task. I agree that human processing is different but
the categorisation of the processes is comparable
> or what you might do when you choose to place a "9" at r5c1 in my
> second example.
For me that would be trial and error. Thus I would record both 1 and 9
as candidates and wait for later information before deciding which of
the two should go into that cell. However, if I encounter a technique
that would explain why '9' is correct and I get to learn how to apply
that (logical) technique then I would commit to '9'. As yet, no!
> I'll repeat what I said earlier -- it's not "trial and error" if one can see
> all the logical implications of a particular move and choose the right
> number to put into some cell.
We agree on that point.
> It's only "trial and error" if one guesses blindly.
or for irrational reasons like '7' being one's lucky number!
I put it slightly differently.
It is trial and error if one posits a specific value and commits to it in
order to determine if a contradiction results.
In the second example, if I were to posit '1' as the correct value (and I have no reason other than the above commentary to suppose that it is not) that would be trial and error. Further, even if I were to posit '9' as
the correct value it would still be trial and error FOR ME (with all due respect to djb's experience in stating '9' to be correct) even if for the
'far-seeing player it would be logical).
> And "supposition" has nothing to do with it.
It would do if I were to put in a '9' in the second example and it is an
acknowledged factor in the London Daily Telegraph puzzles (which is
why I would not contemplate tackling them).
Alan Rayner BS23 2QT
|
|
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Wed Nov 02, 2005 2:12 pm Post subject: Re: Lookahead logic |
|
|
Alanr555 wrote: | Incidentally my former occupation was "systems analyst" ... |
That's interesting. I suppose it was a fairly large company? I worked with computing systems for years, but each company was fairly small -- we were all "programmer/analysts" at the shops I worked at. Sometimes I had to design a system, and sometimes I had to code it.
AlanR555 wrote: | It is clear that value 8 cannot be used as '8' is already present in the box.
This leaves 1 and 9 as candidates.
I have no information on which to base the exclusion of '1' and so I would leave both numbers as candidates. |
Good! Now I see why we're having this discussion.
Let's review the position I had presented -- the one that elicited the quoted response:
Code: | . 8 . . . . . . .
. . . . . . . 2 .
. . . . . . . 3 .
. . . . . . . . 9
. 3 5 . 7 6 . 4 2
. . 8 . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . 8 |
In the example, the only way the digit "8" can be entered in the upper right 3x3 box is in either r2c7 or r3c7. Therefore "8" cannot appear at r5c7, and a "1" must go there. This forces the "8" into r5c4, and the "9" into r5c1.
I don't want to make too big a deal of it, Alan, but I think this illuminates the basic difference between the way I look at a puzzle (on a good day) and the way you attack the same puzzle. You can understand my logic when I explain it step by step, in what appears to me to be the wrong direction. But when I present something I grasped by "seeing" a pattern in the puzzle, you often think it's trial and error.
You might try "seeing" the pattern above, just for grins. Have a great day! dcb |
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich
|
Posted: Wed Nov 02, 2005 2:16 pm Post subject: |
|
|
Hi,
I was thinking that the line:
3 not in r6c9, XY-Wing X=5 Y=8 in r8c3; X=5 Z=3 in r8c9; Y=8 Z=3 in r6c3;
is describing pretty well the XY-Wing.
The cells involved are r8c3, r8c9, c6c3 and finally r6c9.
We have in r8c9 the 2 digits: XY (X=5, Y=
in r8c9 the 2 digits: XZ (X=5, Z=3)
in r6c3 the 2 digits: YZ (Y=8, Z=3
Now Z (Z=3) can't be in the so called 4-th cell, in our case r6c9.
If it's still not clear, please let me know.
see u, |
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
AZ Matt Guest
|
Posted: Wed Nov 02, 2005 6:39 pm Post subject: |
|
|
To alanr555
someone_somewhere describes the "easy" solve, but like you, I see the puzzle differently, and quite differently than you. You asked where I saw the "irregularity." It was in the r6c9 and r8c9.
I solved the puzzle to the point where there were no more "traditional" solves, which in my method includes solving through naked and hidden trips and quads, and sat back and "looked" at the puzzle. This is what I saw:
r2 = *****{35}***
r3 = {35}****{35}***
r5 = {38}{57}**{58}****
r6 = *{57}{38}*{58}***{37}
r8 = **{58}{38}*****{35}
r9 = {58}**{38}*****
There were many (many!) other unsolved cells, but I could see these cells were linked; if you solved for one, you solved for all. You ask "How can you see that?" I don't know what to say other than it's true. That is what I look for, and that is how, and why, they are linked. There are other cells that will be solved, of course (in this case the puzzle falls like a house of cards), but solving them don't necessarily solve these, so in that context, these cells are a set.
If you set this out on a sudoku grid, you will see two "irregularities." All but r6c9 and r8c9 are partners in matched pairs, and r6c8 is "alone" (i.e., it hasn't different numbers than any other cell).
I now refer to this "method" (if it deserves the moniker) as "uncovering the x-y wing," and I've seen it where only the classic x-y wing cells are involved all the way out to 23 cells. I am working on
And thanks someone_somewhere for the puzzles. I am looking forward to them. Ah, if only I could wrest the heavy shackles of employment... |
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
alanr555
Joined: 01 Aug 2005 Posts: 198 Location: Bideford Devon EX39
|
Posted: Wed Nov 02, 2005 7:24 pm Post subject: |
|
|
Code: |
> I solved the puzzle to the point where there were no more "traditional" > solves, which in my method includes solving through naked and hidden > trips and quads, and sat back and "looked" at the puzzle.
r2 = *****{35}***
r3 = {35}****{35}***
r5 = {38}{57}**{58}****
r6 = *{57}{38}*{58}***{37}
r8 = **{58}{38}*****{35}
r9 = {58}**{38}*****
+++
Yes, I reached the same point and noticed the prevalence of cells with
a candidate profile containing just two digits. I wrote out them in a form
very similar to this one as I "sensed" that some form of binary chain
could play a very useful part.
> There were many (many!) other unsolved cells, but I could see these
> cells were linked; if you solved for one, you solved for all. You ask
> "How can you see that?" I don't know what to say other than it's true.
Maybe - but what is the logical rule in this case?
> That is what I look for,
This concept of "looking for" something in Sudoku is difficult for me. It is
much more that I "find" something - to which I can apply a logical rule
in order to gain more information. The phrase "take what you get" would
seem to be relevant here.
> and that is how, and why, they are linked.
I do not get a "why" in what has been quoted here.
> There are other cells that will be solved, of course (in this case the
> puzzle falls like a house of cards),
Yes, I know as I solved the puzzle using a "special binary chain" but
it did involve "trial and error" in that the methodology requires some
attention to TWO chains - one for each value in the selected cell -
and the selection of a cell is also a possible trial/error situation. I agree
that the puzzle fell swiftly after resolving this subset - one through which
there is a veritable network of binary links.
> but solving them don't necessarily solve these, so in that context, these
> cells are a set.
They are a set in the sense that they have a common property - having
just two entries in their candidate profile. Thus I gladly accept that they
are a set. Now what are the rules that enable one to make use of such
a set?
There is a suggestion that the "two-member" cells can be paired and that
the "straggler" pairs are significant. Is this a rule? If so, what does it
tell us about the straggler pairs (ie the ones that are not in pairs of pairs)?
Is it just a pointer to an XY-Wing occurrence (ie a method of directing the
search for an XY-Wing scenario)?
> If you set this out on a sudoku grid, you will see two "irregularities." All > but r6c9 and r8c9 are partners in matched pairs,
That is broadly true - but the pairs in column 1 are part of a threesome.
> and r6c8 is "alone" (i.e., it hasn't different numbers than any other cell).
Strange comment! r6c8 is not even a member of the set. It is marked
with an asterisk in the grid above!!
> I now refer to this "method" (if it deserves the moniker) as "uncovering
> the x-y wing," and I've seen it where only the classic x-y wing cells are
> involved all the way out to 23 cells. I am working on
This seems useful.
Anything which narrows the search for these patterns has to be good.
I just get phased lokking through candidate profiles for patterns.
Thank you for making this link. The rule would seem to be
"If there is a preponderance of two-member profiles and many of them
exist as pairs of pairs, there is likely to be an XY-wing involving the
two-member cell that is not part of a pair"
Is this a fair statement?
Alan Rayner BS23 2QT
|
|
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Wed Nov 02, 2005 7:41 pm Post subject: "15-cell solve" by AZ Matt |
|
|
AZ Matt wrote: | r2 = *****{35}***
r3 = {35}****{35}***
r5 = {38}{57}**{58}****
r6 = *{57}{38}*{58}***{37}
r8 = **{58}{38}*****{35}
r9 = {58}**{38}*****
There were many (many!) other unsolved cells, but I could see these cells were linked; if you solved for one, you solved for all. You ask "How can you see that?" I don't know what to say other than it's true. ... |
Perhaps we can see it more easily if it's lined up in a nice neat grid:
Code: | . . . . . . . . .
. . . . . 3/5 . . .
3/5 . . . . 3/5 . . .
. . . . . . . . .
3/8 5/7 . . 5/8 . . . .
. 5/7 3/8 . 5/8 . . . 3/7
. . . . . . . . .
. . 5/8 3/8 . . . . 3/5
5/8 . . 3/8 . . . . . |
AlanR555 wrote: | (AZ Matt wrote:)
> So you know from looking at this that if you solve one, you solve all.
How come? I did not know it! |
It should be apparent now, Alan. Every cell marked as a pair in this array takes on just one of two values, and all of them are clearly linked via rows and columns. In mathematical phraseology, they form a connected graph. So there are only two states in which the array can exist, and you can determine what those states look like by picking a value in any one of the cells and following the chains of inference. Since all the links in the chain are binary, it's clear that the result will be binary.
AlanR555 wrote: | (AZ Matt wrote:)
> So the key to the solve is in the 37 and 35 in column 9, and you can see
> that if you had a seven in r6c9, you'd have to have two 5s in r8.
This is not at all obvious.
I have a 7 in r6c9 in my full solution and only one '5' in row 8!! |
I think that AZ Matt misspoke here. He meant to say that if you had a three in r6c9 you'd have to have two fives in row 8:
r6c9 = 3 ==> r8c9 = 5 and also r6c9 = 3 ==> r6c3 = 8 ==> r8c3 = 5
Thanks for sharing your insights, AZ Matt! When are you going to join the forum as a registered member? dcb |
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
alanr555
Joined: 01 Aug 2005 Posts: 198 Location: Bideford Devon EX39
|
Posted: Wed Nov 02, 2005 7:43 pm Post subject: Re: Lookahead logic |
|
|
Code: |
> My former occupation was "systems analyst"
>> I suppose it was a fairly large company?
I spent about eighteen years in local government and then was freelance
for a further fifteen or so - working for colleges.
>> I worked with computing systems for years, but each company was
>> fairly small -- we were all "programmer/analysts" at the shops I
>> worked at.
Different category - but more satisfying in some respects.
>> Sometimes I had to design a system, and sometimes I had to code it.
Yes - but I never got round the 'coding' bit after languages got more
complicated than dBaseIII. Perhaps that too was my inability to look
ahead rather than proceeding incrementally.
> Let's review the position I had presented -- the one that elicited the quoted response:
. 8 . . . . . . .
. . . . . . . 2 .
. . . . . . . 3 .
. . . . . . . . 9
. 3 5 . 7 6 . 4 2
. . 8 . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . 8
In the example, the only way the digit "8" can be entered in the upper right 3x3 box is in either r2c7 or r3c7.
Great. Using my system of "Mandatory Pairs" I would mark that fact as
a subscript '8' in each of those two cells and then use that information
later. Holding it in short-term memory whilst checking out r5c1 is not
part of my skillset
> Therefore "8" cannot appear at r5c7, and a "1" must go there.
I would have reached that point - yes.
> This forces the "8" into r5c4, and the "9" into r5c1.
Yes
> I think this illuminates the basic difference between the way I look at
> a puzzle (on a good day) and the way you attack the same puzzle.
Yes - even the language differs ('Look at' and 'attack'!!)
> You can understand my logic when I explain it step by step, in what
> appears to me to be the wrong direction.
That concept I cannot grasp.
The direction you described must be the route - accumulating information
along the way so that a conclusion is reached. Your "looking" seems to
reach a conclusion (albeit a correct one) and then find supporting
evidence afterwards. My mind does not work llike that.
> But when I present something I grasped by "seeing" a pattern in the
> puzzle, you often think it's trial and error.
No - that is not and was not my point.
Trial and Error is where one posits a value for a cell and works the grid
until a contradiction occurs. That very plainly is NOT what is being done
here to reach the 9 directly by omitting the intervening steps.
> You might try "seeing" the pattern above, just for grins.
A blind person might try to cross the highway unaided. She/he just does
not have the equipment to be consistently successful - even if the other
side of the road is reached on several occasions.
Alan Rayner BS23 2QT
|
|
|
Back to top |
|
![](templates/subSilver/images/spacer.gif) |
|
|
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
|