dailysudoku.com

keith · Posted: Sat Dec 17, 2005 9:41 pm Post subject: A very tough but solvable puzzle

Here is a very tough puzzle, actually published (it is David Bodycombe's puzzle of 10 Dec 2005, published locally in the Detroit Free Press).

keith · Posted: Sat Dec 17, 2005 9:49 pm Post subject: Apology

I now see this one was discussed on Monday.

My solution involves, in addition to the usual,

XY Wing
Forcing Chain
Forcing Chain
"Jellyfish" (a complicated Swordfish)
XY Wing
Forcing Chain

Does anyone still have an interest in this one?

Keith

David Bryant · Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado

keith · Posted: Sun Dec 18, 2005 6:21 am Post subject: Will post solution

I'll post a solution after I have written it up.

This is a daily puzzle. Recently, the Saturday ones have been graded with six stars, and contain X Wings, XY Wings, etc. The other daily puzzles require at most a couple of block - column interactions, along with pinned squares, twins, triplets, etc.

I have not seen that these puzzles ar published or archived on a web site. I suppose you could find them at a newspaper site. The one on the Detroit Free Press site (www.freep.com, look under "comics") does not seem to be the same as the one printed in the paper.

The one for today was tough for me, as I recall it had an XY-Wing. It is MUCH easier than this one.

Keith

keith

Here is the solution, as given by Sudoku Susser

http://www.madoverlord.com/projects/sudoku.t

This is an interesting solver, because it solves puzzles the way a human would. Also, you can turn various heuristics on and off. For example, in this puzzle, if you turn the jellyfish off, it resorts to Nishio, which implies that the jellyfish is essential - if you don't find it, you have to use trial and error.

The program takes a long time to find the last forcing chain in this puzzle.

The program also has a very good manual which explains all the patterns, strategies, and heuristics for solving Sudoku. I normally solve puzzles with pencil and paper (including the Daily Sudoku, every day!), and resort to the program only as a learning tool. Then, it is very good. Take a look at the explanation of the Unique Rectangle given below. Even I can understand it!

Best wishes,

Keith

===========================
* R1C2 is the only square in row 1 that can be <1>.
* R5C8 is the only square in row 5 that can be <7>.
* R6C5 is the only square in row 6 that can be <8>.
* R5C9 is the only square in row 5 that can be <8>.
* R8C3 is the only square in row 8 that can be <8>.
* R2C1 is the only square in column 1 that can be <6>.
* R9C9 is the only square in column 9 that can be <1>.
* R3C9 is the only square in column 9 that can be <6>.
* R9C1 is the only square in block 7 that can be <3>.
* R7C1 is the only square in column 1 that can be <2>.
* R8C4 is the only square in column 4 that can be <2>.
* R8C5 is the only square in row 8 that can be <7>.
* Squares R3C6 and R8C6 in column 6 form a simple naked pair. These 2 squares both contain the 2 possibilities <59>. Since each of the squares must contain one of the possibilities, they can be eliminated from the other squares in the column.
R2C6 - removing <9> from <349> leaving <34>.
R5C6 - removing <5> from <345> leaving <34>.
R6C6 - removing <5> from <13456> leaving <1346>.
R7C6 - removing <59> from <1569> leaving <16>.
* Squares R2C6 and R5C6 in column 6 form a simple naked pair. These 2 squares both contain the 2 possibilities <34>. Since each of the squares must contain one of the possibilities, they can be eliminated from the other squares in the column.
R6C6 - removing <34> from <1346> leaving <16>.
* R5C6 is the only square in block 5 that can be <4>.
From this deduction, the following moves are immediately forced:
R2C6 must be <3>.
* A set of 2 squares form a simple hidden pair. R2C4 and R3C4 all contain all of the 2 possibilities <78>. No other squares in column 4 have those possibilities. Since the 2 squares are the only possible locations for 2 possible values, any additional possibilities these squares have (if any) can be eliminated. These squares now become a simple naked pair.
R3C4 - removing <5> from <578> leaving <78>.
* Intersection of row 5 with block 4. The value <9> only appears in one or more of squares R5C1, R5C2 and R5C3 of row 5. These squares are the ones that intersect with block 4. Thus, the other (non-intersecting) squares of block 4 cannot contain this value.
R4C2 - removing <9> from <2359> leaving <235>.
R4C3 - removing <9> from <2569> leaving <256>.
* Intersection of row 8 with block 9. The values <34> only appears in one or more of squares R8C7, R8C8 and R8C9 of row 8. These squares are the ones that intersect with block 9. Thus, the other (non-intersecting) squares of block 9 cannot contain these values.
R7C8 - removing <4> from <4569> leaving <569>.
* R8C8 is the only square in column 8 that can be <4>.
* Intersection of column 8 with block 6. The value <3> only appears in one or more of squares R4C8, R5C8 and R6C8 of column 8. These squares are the ones that intersect with block 6. Thus, the other (non-intersecting) squares of block 6 cannot contain this value.
R4C7 - removing <3> from <1359> leaving <159>.
R6C7 - removing <3> from <135> leaving <15>.
* Squares R1C9, R8C9, R1C7 and R8C7 form a Type-4B Unique Rectangle on <39>. Because they share two rows, two columns, and two blocks, if they all had possibilities <39> then the puzzle would have two solutions; you could simply exchange the <3>'s with the <3>'s in the squares to get the other solution, and their common rows, columns and blocks would still contain one of each value. If you look carefully, you'll see that the only squares in column 7 that can contain <3> are the "roof" squares -- R1C7 and R8C7. Since one of these squares must be <3>, the only way to avoid the "deadly pattern" is if neither of them can contain <9>.
R1C7 - removing <9> from <3479> leaving <347>.
R8C7 - removing <9> from <359> leaving <35>.
* Squares R6C6 (XY), R6C7 (XZ) and R4C5 (YZ) form an XY-Wing pattern on <5>. All squares that are buddies of both the XZ and YZ squares cannot be <5>.
R4C7 - removing <5> from <159> leaving <19>.
R4C8 - removing <5> from <359> leaving <39>.
* Intersection of block 6 with row 6. The value <5> only appears in one or more of squares R6C7, R6C8 and R6C9 of block 6. These squares are the ones that intersect with row 6. Thus, the other (non-intersecting) squares of row 6 cannot contain this value.
R6C2 - removing <5> from <345> leaving <34>.
R6C3 - removing <5> from <456> leaving <46>.
* Found a forcing chain. If we assume that square R3C8 is <9> then we can make the following chain of conclusions:
R3C6 must be <5>, which means that
R8C6 must be <9>, which means that
R8C9 must be <3>, which means that
R1C9 must be <9>, which means that
R3C8 must be <2>.
Since this is logically inconsistent, R3C8 cannot be <9>.
(772 links were considered before finding this chain)
* R9C7 is the only square in row 9 that can be <2>.
* Found a forcing chain. If we assume that square R3C7 is <9> then we can make the following chain of conclusions:
R3C6 must be <5>, which means that
R8C6 must be <9>, which means that
R8C9 must be <3>, which means that
R1C9 must be <9>, which means that
R3C7 must be <7>.
Since this is logically inconsistent, R3C7 cannot be <9>.
(982 links were considered before finding this chain)
From this deduction, the following moves are immediately forced:
R3C4 must be <8>.
R2C4 must be <7>.
* R1C3 is the only square in row 1 that can be <7>.
* R2C2 is the only square in row 2 that can be <8>.
* R2C3 is the only square in row 2 that can be <2>.
* R4C2 is the only square in row 4 that can be <2>.
* Squares R4C3 and R4C5 in row 4 form a simple naked pair. These 2 squares both contain the 2 possibilities <56>. Since each of the squares must contain one of the possibilities, they can be eliminated from the other squares in the row.
R4C4 - removing <5> from <135> leaving <13>.
* Intersection of column 3 with block 7. The value <9> only appears in one or more of squares R7C3, R8C3 and R9C3 of column 3. These squares are the ones that intersect with block 7. Thus, the other (non-intersecting) squares of block 7 cannot contain this value.
R7C2 - removing <9> from <459> leaving <45>.
* Squares R2C5 and R2C7 in row 2, R4C7 and R4C8 in row 4, R7C3 and R7C8 in row 7 and R9C3, R9C5 and R9C8 in row 9 form a Jellyfish pattern on possibility <9>. All other instances of this possibility in columns 3, 5, 7 and 8 can be removed.
R1C5 - removing <9> from <459> leaving <45>.
* Squares R6C2 (XY), R6C8 (XZ) and R7C2 (YZ) form an XY-Wing pattern on <5>. All squares that are buddies of both the XZ and YZ squares cannot be <5>.
R7C8 - removing <5> from <569> leaving <69>.
* Found a forcing chain. If we assume that square R1C5 is <5> then we can make the following chain of conclusions:
R1C1 must be <9>, which means that
R5C1 must be <5>, which means that
R4C3 must be <6>, which means that
R4C5 must be <5>, which means that
R1C5 must be <4>.
Since this is logically inconsistent, R1C5 cannot be <5>.
(13641 links were considered before finding this chain)
From this deduction, the following moves are immediately forced:
R1C7 must be <3>.
R2C5 must be <9>.
R1C9 must be <9>.
R8C7 must be <5>.
R1C1 must be <5>.
R8C9 must be <3>.
R2C7 must be <4>.
R3C6 must be <5>.
R3C2 must be <9>.
R8C6 must be <9>.
R6C7 must be <1>.
R5C1 must be <9>.
R6C6 must be <6>.
R4C7 must be <9>.
R4C8 must be <3>.
R4C4 must be <1>.
R6C8 must be <5>.
R6C3 must be <4>.
R7C6 must be <1>.
R4C5 must be <5>.
R7C4 must be <5>.
R4C3 must be <6>.
R9C5 must be <6>.
R5C4 must be <3>.
R5C2 must be <5>.
R6C2 must be <3>.
R7C2 must be <4>.
R7C3 must be <9>.
R9C8 must be <9>.
R9C3 must be <5>.
R7C8 must be <6>.

(Scientists say that mind exercises like these help prevent dementia later in life. They don't mention the danger of short-term insanity! KM)

keith · Posted: Sun Dec 18, 2005 7:29 am Post subject: Today's (12/17) Bodycombe puzzle

dcb wrote:

>>
I particularly liked the one for today (12/17). Have you looked at that one?
<<

Yes. As I recall, it came down to this unique rectangle:

25 ... 25
25 ... 257

(These are possible values for four squares at the corners of a rectangle in the puzzle.)

and these were the only occurrences of 2 in each row and column. Think about it. You cannot have

25 .. 25
25 .. 25

as the corners of a rectangle, because then, in these four squares, there are two solutions. Pick one, The other is obtained by interchanging 2 and 5. So, the bottom right square must be a 7.

If anyone is interested, I'll post this puzzle as a new thread.

Keith

someone_somewhere · Joined: 07 Aug 2005 Posts: 275 Location: Munich

Hi Keith,

I could not spot the jelly-fish, probable because it is not needed.
Did not know the TYPE-4B UNIQUE RECTANGLE technique.
Thank you, I learned something new.

BTW, in the solution posted (by Sudoku-Susser) the TYPE-4B UNIQUE RECTANGLE is not a must. It can be solved also without it.
But, as you said, it is very nice and I like it.

Now, caming back to the essential:
When we as human look for "forcing chains" (I am using the similar technique, called "double implication chains") the most impoartant question is: WHERE DO WE START TO LOOK?
For a computer program this question is not so important because he can/will scan seqeuntially all the posibilities, if the programmer did not put some priorities, .... which is the same as for us ....

My approch is: "to start from the pairs" and if there are only a few and they do not bring anything, than start with the "relevant" digits of the multi-digit cells. Relevant meaning for example one that appears only 2 times in a row/column/3x3 block.

As an example I have excluded 5 from r5c1 (the last forcing chain described in the solution of Sudoku-Susser) instead of the 5 from c1r5 as the (stupid) program was doing. And this because I started from pairs and r5c1 had the pair of digits 5 & 9. The computer started from r1c5 which was holding as candidates: 4, 5 & 9. So in my case I could mark the other digit as sure, but the computer was left with 2 digits after eliminating one digit.
(This does not mean that the algorithm can't be improved to get closer to the human logic).

Thank you for your contribution. I have learned something new.

see u,

David Bryant · Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado

keith

David,

A very interesting point, with which I disagree. First, a quote from WikiPedia:

"It is possible to set starting grids with more than one solution and to set grids with no solution, but such are not considered proper Sudoku puzzles; like most other pure-logic puzzles, a unique solution is expected."

http://en.wikipedia.org/wiki/Sudoku

As I understand it, "Assuming the consequent" means making an assumption that leads to a particular solution. If the puzzle has only one solution, there is no logical flaw, and no circular logic, in using techniques that take advantage of this fact.

In other words, I think the statement that a puzzle has a unique solution is a ground rule, not an assumption on my part. Glassman's characterization of solution techniques that presume a unique solution as "less than elegant" is unwarranted.

Keith

David Bryant · Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado

keith · Posted: Wed Dec 21, 2005 2:00 am Post subject: No, we just have to agree

David,

I think we just have to agree: Is the uniqueness of the puzzle known a priori or not?

If I were in your shoes, where (I believe) uniqueness is required but needs to be checked, I would use a computer program.

I spent some time today trying to construct a puzzle with not one, but only two solutions. It was a lot harder than I thought it would be. I am now thinking that if a puzzle has multiple solutions (and if all the numbers occur in the starting grid), then it will have many possible solutions (more than two or three).

I can think of one way to possibly make a puzzle that has two solutions, but it would be obvious from the start. Take a vaild filled grid. Remove all the 9's, and all but one of the 8's. Then, find a valid starting grid that includes the single 8, and no 9's. Delete the 8. This may be a puzzle with two solutions - the 8's and 9's can be interchanged. But, since both 8 and 9 are missing from the starting grid, it is obviously so.

Keith

David Bryant · Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado

David Bryant · Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado

keith · Posted: Wed Apr 26, 2006 1:14 am Post subject:

David,

This is the possible example where you cannot use Uniqueness on an initial square.

Keith

David Bryant · Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado

Marty R. · Posted: Wed Apr 26, 2006 5:22 pm Post subject:

David, how do you define a "non-unique rectangle"? When I see any rectangle with a common pair in each corner, I view it as potential to use the technique I know as "unique rectangle."

David Bryant · Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado

Hi, Marty!

It's the same thing. I know that Robert Woodhead calls it a Unique Rectangle. The thing is, the distinguishing feature of such a rectangle (no matter which of the many "types" it is) is that completing it in a certain way will lead to non-unique solutions. So it seems natural to me to think of it as a "non-unique rectangle."

I hope that's not too confusing. I'll try to use the quote marks every time, to alert you (and maybe others?) to the fact that this is my own little idiosyncracy. dcb

PS I ran into an example of a "non-unique hexagon" the other day, which is interesting because it's somewhat different -- you can read about that in the "Nightmare" forum.

keith · Posted: Wed Apr 26, 2006 11:58 pm Post subject:

I agree with David. The logic rests on avoiding solutions or possibilities that are not unique.

Also, if you are not a computer programmer, the various classifications of (non) unique rectangles are not important. Just recognize the pattern, and learn what to do with it.

Keith

Marty R. · Posted: Thu Apr 27, 2006 5:36 pm Post subject:

Thanks David.

Keith, I'm not a computer programer, although I spent nine years as one in the dark ages of mainframe computers which occupied an entire large room and whose tape drives were the size of refrigerators.

I have looked at the rectangle classifications--I assume you mean Type 1, 2, etc.--and have no idea of what I can do with the knowledge that a rectangle is Type "X."