Stuck in a "Diabolical" sudoku

Advanced methods and approaches for solving Sudoku puzzles

Stuck in a "Diabolical" sudoku

Postby SuDoKu_StUdeNt » Thu Nov 24, 2005 2:04 pm

Hi all,
I got stuck in this point:

Image

Is there a way to solve this puzzle without using trial and error? I tried even in some sudoku solving programs and ended up with nothing.

Thanks in advance.
SuDoKu_StUdeNt
 
Posts: 3
Joined: 23 October 2005

Postby tso » Thu Nov 24, 2005 5:33 pm

Take a look at the 6 cells in brackets:

Code: Select all
  8       45      3       | 45      2       9       | 7       1       6       
  29      279     6       |[37]     1       8       | 5      [239]    4       
  1249    124579  247     | 3457    6       347     | 239     239     8       
 -------------------------+-------------------------+-------------------
  123     123     5       |[127]    4       6       | 39      8       79     
  7       18      9       | 18      3       5       | 6       4       2     
  234     6       248     |[278]    9      [27]     | 1      [37]     5     
 -------------------------+-------------------------+-------------------
  6       3489    48      | 234     7       234     | 29      5       1     
  349     349     1       | 6       5       234     | 8       279     79     
  5       27      27      | 9       8       1       | 4       6       3     


Regardless of what value r6c8 is, r2c8 cannot be a 3.

After some singles, you can use colors to eliminate a 2 from r6c6 [Edit] or an xy-wing in r36c36 to place a 2 at r3c3.
Last edited by tso on Thu Nov 24, 2005 1:58 pm, edited 1 time in total.
tso
 
Posts: 798
Joined: 22 June 2005

Postby CathyW » Thu Nov 24, 2005 5:37 pm

I think this must be one of the hardest I've ever seen. Sadman Sudoku and Simple Sudoku couldn't solve it so I then pasted your grid into Sudoku Susser. Here's part of the solving log - I wouldn't even have found the forcing chain myself!

Code: Select all
* Found a forcing chain.  If we assume that square R7C6 is <2> then we can make the following chain of conclusions:

   R7C7 must be <9>, which means that
   R4C7 must be <3>, which means that
   R6C8 must be <7>, which means that
   R6C6 must be <2>, which means that
   R7C6 must be <34>.

Since this is logically inconsistent, R7C6 cannot be <2>.

* Made progress using Trebor's Tables to find inferences about the puzzle.  A total of 11829 implications about the puzzle were generated and examined in order to find these inferences - you'd run through several pencils working them out by hand!



There followed a very long list of 'veracities' which somehow enables the solution to be found.

I guess it shows that there are some puzzles that are nigh on impossible to solve by hand alone.
CathyW
 
Posts: 316
Joined: 20 June 2005

Postby Carcul » Thu Nov 24, 2005 6:11 pm

SuDoKu_StUdeNt:

Yes, it is possible to solve this puzzle by hand without using trial and error, and its not that difficult. Here is the method (much more lengthy that tso's method...) I used to solve it just by hand, using nice loops and unique rectangles:

Chain 1: [r8c6]=2=[r8c8]=7=[r6c8]–7–[r6c6]–2–[r8c6], => r8c8<>9.

Chain 2: [r5c2]=8=[r7c2]=9=[r7c7]–9–[r4c7]=9=[r4c9]=7=[r4c4]=1=[r5c4]=8=[r5c2], => r5c2 = 8.

Now the grid need to be updated. After that,

Chain 3: [r3c6]=7=[r6c6]–7–[r6c8]–3–[r4c7]=3=[r3c7]–3–[r2c8]=3=[r2c4]–3–[r3c6], => r3c6<> 3.

Chain 4: [r6c3]=4=[r3c3]–4–[r3c6]–7–[r6c6]–2–[r6c3], => r6c3 = 4.

Now we have a Type-1 Unique Rectangle in cells r3c23–r9c23, from wich we can conclude that r3c2<>2,7. Two more nice loops:

Chain 5: [r8c1]=4=[r3c1]–4–[r3c6]–7–[r6c6]–2–[r6c1]–3–[r8c1], r8c1<>3.

Chain 6: [r8c1]=4=[r3c1]–4–[r1c2]=4=[r1c4]=5=[r3c4]=3=[r2c4]=7=[r2c2]–7–[r3c3]–2–[r2c1]–9–[r8c1], => r8c1 = 4.

With this conclusion, we have in box (3,1) a naked pair (3,9), wich allows several eliminations to be made in boxes (1,1) and (2,1). After the grid has been updated, we have another Type-1 Unique Rectangle in cells r1c24–r3c24, from wich we must have r3c4 = 3,7. With the naked pair (3,7) that emerges from here, the puzzle is easly solved.

Carcul
Last edited by Carcul on Thu Nov 24, 2005 2:32 pm, edited 2 times in total.
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby tso » Thu Nov 24, 2005 6:12 pm

CathyW -- I think you have an older version of Susser. It's currently 2.0.6

After it finds the forcing chain you mentioned, it finds a uniqueness rectangle, then an xyw-wing, then an nishio -- all of which advance the puzzle, but none of which are required for the solution I posted above.

It finally finds a simple xy-type forcing chain where I had a complex forcing chain. Susser does not find forcing chains in which the links are of the form "r6c8=7 => r6c46<>7 => r4c6=7" that was used in my solution. After simplifying the puzzle with all the other tactics above, a simple forcing chain using the same cells was found.
tso
 
Posts: 798
Joined: 22 June 2005

Postby Myth Jellies » Thu Nov 24, 2005 6:59 pm

I thought this looked familiar. Puzzle 104 was one of the first puzzles that I developed the Pattern Overlay Method for. There were a couple threads for it in another forum. Several other options for solving were discussed as well.

http://www.sudoku.org.uk/discus/messages/2/231.html?1128240304

http://www.sudoku.org.uk/discus/messages/6/202.html?1130395479
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby tso » Thu Nov 24, 2005 7:17 pm

Myth Jellies wrote:I thought this looked familiar. Puzzle 104 was one of the first puzzles that I developed the Pattern Overlay Method for. There were a couple threads for it in another forum. Several other options for solving were discussed as well.

http://www.sudoku.org.uk/discus/messages/2/231.html?1128240304

http://www.sudoku.org.uk/discus/messages/6/202.html?1130395479


Angus Johnson's forcing chain (found in the second thread) is slightly better than mine, requiring one less cell to get the same conclusion:

Code: Select all
  8       45      3       | 45      2       9       | 7       1       6       
  29      279     6       |[37]     1       8       | 5      [239]    4       
  1249    124579  247     | 3457    6       347     | 239     239     8       
 -------------------------+-------------------------+-------------------
  123     123     5       |[127]    4       6       | 39      8      [79]   
  7       18      9       | 18      3       5       | 6       4       2     
  234     6       248     | 278     9       27      | 1      [37]     5     
 -------------------------+-------------------------+-------------------
  6       3489    48      | 234     7       234     | 29      5       1     
  349     349     1       | 6       5       234     | 8       279     79     
  5       27      27      | 9       8       1       | 4       6       3     


It is still a complex forcing chain rather than a simple forcing chain, as it requires a link of the type "r6c8=7 => r4c9<>7", thus combining xy-type chains with coloring type chains.
tso
 
Posts: 798
Joined: 22 June 2005

Postby Jeff » Thu Nov 24, 2005 7:26 pm

Carcul wrote:.............Here is the method (much more lengthy that tso's method...) I used to solve it just by hand, using nice loops and unique rectangles:..........

Carcul, I am pleased to see these nice loop notations. Mind you that picking the right nice loop will save a lot of work. Check this:

Chain 1: [r2c4]=3=[r2c8]-3-[r6c8]-7-[r4c9]=7=[r4c4]-7-[r2c4] => r2c4<>7
After this, it just requires an XY-Wing to remove a 2 in r6c2. You may consider this Chain 2.:D
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Thu Nov 24, 2005 7:41 pm

tso wrote:It is still a complex forcing chain rather than a simple forcing chain, as it requires a link of the type "r6c8=7 => r4c9<>7", thus combining xy-type chains with coloring type chains.


Perhaps it is easier to express forcing chains as follows:

xy-type chains are pure bivalue chains (links of the type "r6c8=7 => r4c9<>7")
So-called coloring type chains are pure bilocation chains (links of the type "r4c9<>7 => r4c4=7")
When bivalue links and bilocaion links are mixed, the product is a combination chain (call it a complex chain if you like)

Forcing chain is a general name for all bivalue chains, bilocation chains and combination chains.:D
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Carcul » Thu Nov 24, 2005 8:12 pm

Jeff, you are absolutely right. I guess that, for the moment, I don't have enough experience to select the appropiate nice loop, but I suspect that my problem is not to draw the complete bilocation/bivalue graph for the grid.
Nevertheless, after I have posted what must be the most unnecessarily complicated solution to a puzzle ever posted in this forum, I found a chain equivalent to your chain 1, that allows a much more faster solution than my first one:

Chain 1: [r2c4]=3=[r2c8]-3-[r6c8]-7-[r6c6]=7=[r3c6]-7-[r2c4] => r2c4<>7.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby tso » Thu Nov 24, 2005 8:47 pm

Jeff wrote:
tso wrote:It is still a complex forcing chain rather than a simple forcing chain, as it requires a link of the type "r6c8=7 => r4c9<>7", thus combining xy-type chains with coloring type chains.


Perhaps it is easier to express forcing chains as follows:

xy-type chains are pure bivalue chains (links of the type "r6c8=7 => r4c9<>7")
So-called coloring type chains are pure bilocation chains (links of the type "r4c9<>7 => r4c4=7")
When bivalue links and bilocaion links are mixed, the product is a combination chain (call it a complex chain if you like)

Forcing chain is a general name for all bivalue chains, bilocation chains and combination chains.:D


I also include forcing chains that require pairs or trips as a single link as complex forcing chains as well as chains like the one I posted that have links that exclude two or more cells instead of one.

I'm confused about the use of the term "nice loops". I was under the impression that this refered only to repetitive or non-repetitive bivalue or bilocation chains that allowed one to make a deductions simply by examining the edge labels.

For example, in a bi-value repetitive loop, I can eliminate the candidate from the vertex at the intersection of the two matching edges without having to follow the implications around the loop. In a non-repetitive loop, I can eliminate all candidates from the houses matching the label of the edge contained in that house. Is there a way to look at the edge labels in these chains and find the deduction without following the implications around? Could you point me to where these type of nice loops are discussed? Or am I reading too much into the choice of terms?

Does the solution I posted at the top of this thread qualify as a "nice loop" in this context? What about AngusJ's version?
tso
 
Posts: 798
Joined: 22 June 2005

Fairly Simple solution

Postby PhotoCrazy » Fri Nov 25, 2005 5:54 am

Hi Everyone,

I am new to Sudoku (3 weeks) and was bitten by the bug. I thought I found a general solution to solving just about any Sudoku problem until I came across this "Diabolical" problem.

This problem required two trial and error tests. Once the trial and error tests were applied the solution was found pretty quick.

I tried to follow some of the logic and symbolism of you more experienced Sudoku fans but got confused. I think the general solution I describe is a bit easier to follow for a novice like myself.

I would greatly appreciate any feedback and don't hesitate to tell me that I am all wet around the ears and didn't find that general solution that I thought I found. So far the general solution works quite well and quickly to any Sudoku problem I have come across including this Diabolical one.

I describe the solution in the following PDF file:
[/url]http://www.photocrazy.com/Dup1.pdf[/url]

Again, any feedback will be much appreciated.

Peter
peter@photocrazy.com
PhotoCrazy
 
Posts: 1
Joined: 24 November 2005

Another Question

Postby SuDoKu_StUdeNt » Fri Nov 25, 2005 6:58 am

Hi all,
Thank you very much for your help. I have another question though: Are there sudokus that REQUIRE trial & error, or that every sudoku can be solved using logic methods?
SuDoKu_StUdeNt
 
Posts: 3
Joined: 23 October 2005

Postby emm » Fri Nov 25, 2005 10:09 am

emm
 
Posts: 987
Joined: 02 July 2005

Postby CathyW » Fri Nov 25, 2005 3:03 pm

tso wrote:CathyW -- I think you have an older version of Susser. It's currently 2.0.6


Thanks - I will go get the up to date version.
CathyW
 
Posts: 316
Joined: 20 June 2005

Next

Return to Advanced solving techniques