dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Nightmare, July 11

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles
View previous topic :: View next topic  
Author Message
Marty R.



Joined: 12 Feb 2006
Posts: 5160
Location: Rochester, NY, USA

PostPosted: Sun Jul 23, 2006 3:50 pm    Post subject: Nightmare, July 11 Reply with quote

This has been an interesting puzzle, with rectangles, X-Wing, XY-Wing and a Finned Wing. At this point it's easily solvable with a chain, perhaps multiple chains. I started with r4c6 and a "2" there solves the puzzle.

However, I am trying to cut back on my chain habit and I'm wondering if there are other techniques that are available to complete it.


Code:
----------------------------------------
|7   13  136 |9   46  8   |456 356 2   |
|5   23  369 |1   246 7   |49  369 8   |
|29  4   8   |3   5   26  |69  7   1   |
----------------------------------------
|8   7   35  |4   236 26  |1   56  9   |
|29  235 359 |7   36  1   |568 568 4   |
|1   6   4   |5   8   9   |7   2   3   |
----------------------------------------
|6   9   7   |8   1   3   |2   4   5   |
|3   15  15  |2   7   4   |89  89  6   |
|4   8   2   |6   9   5   |3   1   7   |
----------------------------------------
Back to top
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3165
Location: near Detroit, Michigan, USA

PostPosted: Sun Jul 23, 2006 7:47 pm    Post subject: Reply with quote

Marty,

I could make no progress without chains. Sudoku Susser says it needs a chain, and finds many of them.

I took a look for the possibility of a UR on <56> in the top right section, but I did not find anything.

Keith
Back to top
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5160
Location: Rochester, NY, USA

PostPosted: Mon Jul 24, 2006 1:31 am    Post subject: Reply with quote

Quote:
I could make no progress without chains. Sudoku Susser says it needs a chain, and finds many of them.


Thanks Keith. In the time I've been on this forum, there have been numerous discussions about trial-and-error and how certain chains fall into that category, at least in the opinion of some. I've argued against those opinions, yet deep down, I apparently agree partially.

Thus, I've tried to further explore other techniques before doing the chains, and have often felt that when I solved with chains that maybe I was missing something. Perhaps chains arent so bad after all; if they're good enough for the Susser, they should be good enough for me too. Laughing
Back to top
View user's profile Send private message
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Mon Jul 24, 2006 11:09 pm    Post subject: This puzzle features an "APE" Reply with quote

I had to use double-implication chains to complete this puzzle, Marty. I think that some kind of chain is unavoidable.

Out of curiosity I ran Ruud's "SudoCue" solver on this puzzle, to see how it would mount an attack. The program produced one very interesting new style of move, called an "Aligned Pair Exclusion," or APE. Here's the position.
Code:
  7     13   136    9     46    8    456   356    2
  5     23   369    1    2467  267   469   369    8
  29    4     8     3     5     26    69    7     1
  8     7    345   456   236   256*   1     56    9
  29   235   359    7     36    1    568   568    4
  1     6     45    45    8     9     7     2     3
  6     9     7     8     1     3     2     4     5
  3     15    15    2     67    4     89    89    67
  4     8     2     56    9    567    3     1     67

We can exclude the digit "5" from r4c6 by the following logic.

r4c6 = 5 ==> r4c8 = 6
r4c6 = 5 ==> r6c4 = 4

But now there are no candidates left at r4c4, so r4c6 = 5 is seen to be impossible. Notice that this particular "APE" is the same thing as the "four-star constellation" that someone_somewhere introduced on this board last October. So the logic isn't new ... but I've never seen the name "Aligned Pair Exclusion" before.

There's a pretty good description of two kinds of "APE"s on the ScanRaid web site.

Interestingly enough, Ruud's program resorts to a forcing chain after following up with a few obvious moves that follow the "APE".
Code:
  7     13   136    9     46    8    456   356    2
  5     23   369    1    246    7    469   369    8
  29    4     8     3     5     26    69    7     1
  8     7    345   45    236    26    1     56    9
  29   235   359    7     36    1    568   568    4
  1     6     45    45    8     9     7     2     3
  6     9     7     8     1     3     2     4     5
  3     15    15    2     67    4     89    89    6
  4     8     2     6     9     5     3     1     7

From here we can see that r1c5 = 4 is impossible via a double-implication chain:

A. r1c5 = 6 ==> {1, 3} pair in r1c2&3.
B. r1c5 = 6 ==> r4c6 = 6 ==> r4c8 = 5 ==> r1c8 = 3

and we can't avoid placing two "3"s in row 1. Once we set r1c5 = 4 a couple of XY-Wings are enough to finish it off. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Myth Jellies



Joined: 27 Jun 2006
Posts: 64

PostPosted: Tue Jul 25, 2006 9:57 am    Post subject: Reply with quote

Code:
 *-----------*
 |...|9.8|...|
 |5..|...|..8|
 |.4.|.5.|.7.|
 |---+---+---|
 |8..|...|..9|
 |...|7.1|...|
 |16.|.8.|.23|
 |---+---+---|
 |6.7|...|2.5|
 |...|2.4|...|
 |.8.|...|.1.|
 *-----------*

 *-------------------------------------------------------------*
 | 7     13    136   |   9     46    8     | 456   356   2     |
 | 5     23    369   |   1     2467  267   | 469   369   8     |
 | 29    4     8     |   3     5     26    | 69    7     1     |
 |-------------------+---------------------+-------------------|
 | 8     7    *345   | b*456   236  #256   | 1    c56    9     |
 | 29    235   359   |   7     36    1     | 568   568   4     |
 | 1     6    *45    | a*45    8     9     | 7     2     3     |
 |-------------------+---------------------+-------------------|
 | 6     9     7     |   8     1     3     | 2     4     5     |
 | 3     15    15    |   2     67    4     | 89    89    67    |
 | 4     8     2     |   56    9     567   | 3     1     67    |
 *-------------------------------------------------------------*

The type 4 UR using 45 in r46c34 kills the 5's in r4c34. Then the 54-46-65 xy-wing in abc kills the 5 in r4c6 and leaves row 4's only 5 in c [r4c8]. Basic reductions will get you to a BUG+1 grid from there. Of course, you can use APE, the ALS xz-rule, subset counting, or an xyz-wing prior to the UR to eliminate the 5 in r4c8 if you prefer.
Back to top
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5160
Location: Rochester, NY, USA

PostPosted: Tue Jul 25, 2006 8:07 pm    Post subject: Reply with quote

Quote:
There's a pretty good description of two kinds of "APE"s on the ScanRaid web site.


"The Aligned Pair Exclusion can be succinctly stated: Any two cells aligned on a row or column within the same box CANNOT duplicate the contents of any two-candidate cell they both see."

This may be succinct, but it's not clear to me. What does it mean that the two cells can't duplicate the contents of any two-candidate cell? Are we talking the two cells together, or either one of the cells can't be a duplicate? Can that be restated, perhaps with less succinctness, if necessary, and more clarity?

Consider this simple example.

Code:
|679 269 27  |4   1   3   |8   5   26  |


The 679 and 269 cells both see the 27 and 26 cells. So what does that tell me about what can be done with the two three-candidate cells?
Back to top
View user's profile Send private message
Myth Jellies



Joined: 27 Jun 2006
Posts: 64

PostPosted: Tue Jul 25, 2006 10:52 pm    Post subject: Reply with quote

Marty R. wrote:
Consider this simple example.

Code:
|679 269 27  |4   1   3   |8   5   26  |


The 679 and 269 cells both see the 27 and 26 cells. So what does that tell me about what can be done with the two three-candidate cells?


It tells you that if the 269 cell equals 2 then the 679 cell must be 9 (26 and 27 are prohibited by the bivalue cells). If you had a 29 cell in the same box as the two three-candidate cells, then you could eliminate the 2 from the 269 cell using APE; or the ALS xz-rule, or AICs, or Subset Counting, etc.
Back to top
View user's profile Send private message
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Wed Jul 26, 2006 11:37 am    Post subject: Reply with quote

Myth Jellies wrote:
The type 4 UR using 45 in r46c34 kills the 5's in r4c34.

This is a sample, how a UR reduction can be "destroyed". From Marty's grid one could not know, if the 5 or one of the 2 4's were givens. In this case it would not have been allowed to eliminate 5 from r4c3.
Back to top
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5160
Location: Rochester, NY, USA

PostPosted: Wed Jul 26, 2006 5:18 pm    Post subject: Reply with quote

Myth Jellies wrote:
Marty R. wrote:
Consider this simple example.

Code:
|679 269 27  |4   1   3   |8   5   26  |


The 679 and 269 cells both see the 27 and 26 cells. So what does that tell me about what can be done with the two three-candidate cells?


It tells you that if the 269 cell equals 2 then the 679 cell must be 9 (26 and 27 are prohibited by the bivalue cells). If you had a 29 cell in the same box as the two three-candidate cells, then you could eliminate the 2 from the 269 cell using APE; or the ALS xz-rule, or AICs, or Subset Counting, etc.

Thank you Mr. Jellies, but don't underestimate my thickheadedness. It seems to me that if the 269 cell were a 2, then the 679 cell would be a 9 because it's now a single, not because of one of the alphabetical rules.

And I'm sorry to say that I still don't understand the "rule" as stated on the other site, that I quoted in my earlier post. About all I can see thus far is that situation with both cells seeing a two-candidate cell might be a good place to start a forcing chain.
Back to top
View user's profile Send private message
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Wed Jul 26, 2006 5:48 pm    Post subject: What's in a name? Reply with quote

Marty R wrote:
And I'm sorry to say that I still don't understand the "rule" as stated on the other site, that I quoted in my earlier post. About all I can see thus far is that situation with both cells seeing a two-candidate cell might be a good place to start a forcing chain.

Since I brought this up, I feel as if I ought to jump in again.

I think the "rules" are getting so specialized -- and the names are getting so exotic -- that it's hard to keep track of all of them.

I think the "APE" is just a special case of the "four-star constellation" we've already kicked around pretty thoroughly. The only reason I brought it up at all is because it's a new name for a (short) variety of forcing chain, it appears to be gaining wide acceptance among sudoku programmers, and others might be interested.

I'm pretty sure you're exactly right, Marty -- the "APE" can always be visualized as a variety of forcing chain. If you want to use the new name for it, fine. If not, that's fine as well. The underlying logic is what matters. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Marty R.



Joined: 12 Feb 2006
Posts: 5160
Location: Rochester, NY, USA

PostPosted: Wed Jul 26, 2006 11:20 pm    Post subject: Reply with quote

Quote:
I'm pretty sure you're exactly right, Marty -- the "APE" can always be visualized as a variety of forcing chain. If you want to use the new name for it, fine. If not, that's fine as well. The underlying logic is what matters. dcb


Thanks David. I have no trouble with the name or other terminology, albeit it can be confusing at times. And I will always welcome a new technique or pattern that suggests a certain spot may be a potential for a productive chain.

What bothers me is my inability to understand the definition of the "APE" rule, as originally stated on the other site, and the attempted clarification here:

"The Aligned Pair Exclusion can be succinctly stated: Any two cells aligned on a row or column within the same box CANNOT duplicate the contents of any two-candidate cell they both see."

I do not know what "CANNOT duplicate the contents" means, whether it applies to either cell individually, or the two cells in combination. That's all I'm asking for, a restatement of the rule that I can understand.
Back to top
View user's profile Send private message
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Thu Jul 27, 2006 12:21 am    Post subject: Restating the "succinct" rule Reply with quote

Marty R wrote:
I do not know what "CANNOT duplicate the contents" means, whether it applies to either cell individually, or the two cells in combination. That's all I'm asking for, a restatement of the rule that I can understand.

Well, I'm not real hot with definitions, but I'll try to clarify this one, by being a little more verbose.

Suppose there are two cells (A, B) that can both "see" one or more other cells, each of which has just two possible candidates. Then in the final solution, you will not find those two cells (A, B) containing, between them, any of the pairs of candidates both A and B could "see".

I think the thing about being aligned in a row or column, and within the same box, is just a red herring. It may make the particular combination a little bit easier to look for. But the principle is simple: combinations of values that eliminate all candidates from one or more cells are simply impossible. In other words, I see nothing earth-shaking about the "APE" -- it's just a catchy new name for a form of proof by contradiction. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Thu Jul 27, 2006 9:27 am    Post subject: Reply with quote

Marty,

you can find four nice puzzles, that can be solved with APE there. I suppose you would solve the first 2 without seeing it, but in the 3rd and maybe the 4th you might stumble at it.

For me APE is a subset of ALS, which one can spot rather easily, where all the other ALS's i had, i found "accidentally" when looking for chains using tuples.

PS: another APE puzzle:
Code:
 +-------+-------+-------+
 | . . . | 6 5 3 | . . . |
 | . 2 . | . . 4 | 3 . . |
 | 4 . . | . 2 . | . 1 . |
 +-------+-------+-------+
 | . . . | . 3 . | . 2 . |
 | . 6 5 | . . 7 | 4 . . |
 | 8 . . | 4 . . | . . . |
 +-------+-------+-------+
 | 3 . . | 1 . . | . 9 . |
 | . 4 2 | . . . | 1 . . |
 | . . 8 | 2 7 . | . . . |
 +-------+-------+-------+
Back to top
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5160
Location: Rochester, NY, USA

PostPosted: Thu Jul 27, 2006 5:34 pm    Post subject: Reply with quote

Thanks guys. I think it's best that I just let this drop. If I don't get it by now, I'm not gonna get it.

The only ALS I've ever heard of is the disease that nobody wants.

Ravel, I tried that puzzle and it took a little work. There was a finned wing, strong link, type 4 rectangle and x-wing. Then I was stuck, so I tried a chain which lead to a contradiction. Then another chain solved the whole thing.

Perhaps I used the APE rule without knowing I used it.
Back to top
View user's profile Send private message
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Fri Jul 28, 2006 7:22 am    Post subject: Reply with quote

I really think you dont need it :)

So just to finish the topic: The 3 pairs kill all candidates in r9c1, when they cannot be 7.

Code:
 #17    178    9   |  6     5   3    |  2    78    4         
  567   2      67  |  789   1   4    |  3    578   579       
  4     578    3   |  789   2   89   |  679  1     5679   
 -----------------------------------------------------   
 #79    79     4   |  5     3   1    |  68   2     68         
  2     6      5   |  89    89  7    |  4    3     1         
  8     3      1   |  4     6   2    |  79   57    579       
 -----------------------------------------------------   
  3     57    #67  |  1     4   568  |  78   9     2         
  5-79  4      2   |  3     89  589  |  1    6     78         
 #169   19     8   |  2     7   69   |  5    4     3         
Back to top
View user's profile Send private message
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Fri Jul 28, 2006 3:04 pm    Post subject: This "APE" has a sort of "mirror-image" Reply with quote

Ravel, when I reached that point in this puzzle I saw a double-implication chain which amounts to the same thing, more or less.
Code:
  17    178    9   |  6     5   3    |  2    78    4
  567   2      67  |  789   1   4    |  3    578   579
  4     578b   3   |  789   2   89   |  679  1     5679b
 -----------------------------------------------------
  79    79     4   |  5     3   1    |  68b  2     68
  2     6      5   |  89    89  7    |  4    3     1
  8     3      1   |  4     6   2    |  79   57    579
 -----------------------------------------------------
  3     57a    67  |  1     4   568  |  78b  9     2
  579   4      2   |  3     89  589  |  1    6     78
  169   19     8   |  2     7   69   |  5    4     3

A. r7c3 = 7 ==> r7c2 = 5
B. r7c3 = 7 ==> r7c7 = 8 ==> r4c7 6 ==> r3c9 = 6 ==> r3c2 = 5

Here's why this DIC looks like a "mirror-image" of the APE you pointed out.

-- Your contradiction left no candidates at r4c1. We can also think of this as meaning (somewhat illogically) that both "7" and "9" have to fit into r4c2.

-- Think about column 2, with both "7" and "9" occupying r4c2. Then r9c2 = 1, and r1c2 = 8, leaving only "5" to occupy both r3c2 and r6c2. In other words, the contradiction you derived implies (broadly speaking) the contradiction I arrived at.

I can't exactly prove this idea -- I'm not even sure I can express it clearly. But it's as if the double-implication chain I used is a sort of dual, or mirror-image, of the "APE" chain you explained. dcb

PS This setup has other possibilities. For instance, consider what happens if r1c2 = 1 ...

A. r1c2 = 1 ==> r1c1 = 7 ==> r4c1 = 9 ==> r8c1 = 5
B. r1c2 = 1 ==> r9c2 = 9 ==> r4c2 = 7 ==> r7c2 = 5

This also leads pretty directly to your conclusion that r8c1 <> 7, because of r1c1 = 1, r9c2 = 1, r4c2 = 9, and r4c1 = 7. My point is that there are quite a few chains of inference involving the same basic structure, any one of which is enough to crack this puzzle wide open. For a human solver, any of these are equally useful ... the challenge is just to spot any one of them.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Fri Jul 28, 2006 9:48 pm    Post subject: Reply with quote

Very interesting, David.

I like your idea of "dual" chains (we have this for hidden/naked sets and the "dual" fish patterns with k and 9-k rows/columns involved).

Unfortunateley in the moment i am too busy to think more about that.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles All times are GMT
Page 1 of 1

 
Jump to:  
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