Advanced methods and approaches for solving Sudoku puzzles

Code: Select all
`# Original Puzzle *-----------* |...|13.|..9| |.8.|.5.|.1.| |..9|..6|.7.| |---+---+---| |.31|.49|...| |6..|...|..8| |...|76.|13.| |---+---+---| |.6.|5..|2..| |.7.|.9.|.6.| |4..|.83|...| *-----------*`

Code: Select all
`# Reduced to *--------------------------------------------------------------------* | 257    245    2567-4 | 1      3      478    | 4568   245    9      | | 237    8      246    | 9      5      47     | 346    1      2346   | | 135    145    9      | 48     2      6      | 3458   7      35-4   | |----------------------+----------------------+----------------------| | 2578   3      1      | 28     4      9      | 567    25     267    | | 6      245    57-4 ? | 3      1      25     | 4579   2459   8      | | 258    9      2458   | 7      6      258    | 1      3      245    | |----------------------+----------------------+----------------------| | 9      6      3      | 5      7      14     | 2      8      14     | | 158    7      58     | 24     9      124    | 345    6      1345   | | 4      125    25     | 6      8      3      | 579    59     157    | *--------------------------------------------------------------------*`

I use Templates to handle Colors and Multi-Colors. At this point, my solver says [r1c3]<>4 and [r3c9]<>4. These correspond to Multi-Colors reductions. Now, here's where I get lost. My solver indicates next that [r5c3]<>4 through Templates as well. Is there some higher form of Coloring that explains this elimination? TIA!!!
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

Way before that, I wonder what was the move your solver came up with this state:
Code: Select all
` *--------------------------------------------------------------------* | 257    245    24567  | 1      3      478    | 4568   2458   9      | | 237    8      23467  | 9      5      47     | 346    1      2346   | | 135    145    9      | 48     2      6      | 3458   7      345    | |----------------------+----------------------+----------------------| | 2578   3      1      | 28     4      9      | 567    25     2567   | | 6      245    2457   | 3      1      25     | 4579   2459   8      | | 2589   2459   2458   | 7      6      258    | 1      3      245    | |----------------------+----------------------+----------------------| | 139    6      38     | 5      7      14     | 2      489    134    | | 1358   7      358    | 24     9      124    | 3458   6      1345   | | 4      1259   25     | 6      8      3      | 579    59     157    | *--------------------------------------------------------------------*`

I couldn't see any "Templates" move from there...
udosuk

Posts: 2698
Joined: 17 July 2005

udosuk wrote:Way before that, I wonder what was the move your solver came up with this state:
Code: Select all
` *--------------------------------------------------------------------* | 257    245    24567  | 1      3      478    | 4568   2458   9      | | 237    8      23467  | 9      5      47     | 346    1      2346   | | 135    145    9      | 48     2      6      | 3458   7      345    | |----------------------+----------------------+----------------------| | 2578   3      1      | 28     4      9      | 567    25     2567   | | 6      245    2457   | 3      1      25     | 4579   2459   8      | | 2589   2459   2458   | 7      6      258    | 1      3      245    | |----------------------+----------------------+----------------------| | 139    6      38     | 5      7      14     | 2      489    134    | | 1358   7      358    | 24     9      124    | 3458   6      1345   | | 4      1259   25     | 6      8      3      | 579    59     157    | *--------------------------------------------------------------------*`

I couldn't see any "Templates" move from there...

Excluding Naked/Hidden Singles, here's how I obtained my pencilmarks. (The puzzle is from my own generator.)
Code: Select all
`    b6  -  9     Locked Candidate (1)    b8  -  2     Locked Candidate (1)r7c1    <> 8     Templates -- Pass C (Multi-Colors)r6c2    =  9     Forcing Chain/Net on [r3c4]r7c1    =  9     Forcing Chain/Net on [r3c4]r2c3    <> 7     Forcing Chain/Net on [r3c4]r4c9    <> 5     Forcing Chain/Net on [r4c8]r5c3    <> 2     Forcing Chain/Net on [r4c8]r7c3    =  3     [r7c3]=8 => [b7]=INVALIDr1c3    <> 4     Templates -- Pass C (Multi-Colors)r3c9    <> 4     Templates -- Pass C (Multi-Colors)r5c3    <> 4     Templates -- Pass C ( ??? )`
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

Code: Select all
` *-----------------------------------------------------------* | 257 \$@245   2567  | 1     3     478   | 4568 @245   9     | | 237   8     246   | 9     5     47    | 346   1     2346  | | 135 \$#145   9     |#48    2     6     | 3458  7     35    | |-------------------+-------------------+-------------------| | 2578  3     1     | 28    4     9     | 567   25    267   | | 6    \$245  -457   | 3     1     25    | 4579 @2459  8     | | 258   9   #@2458  | 7     6     258   | 1     3   #@245   | |-------------------+-------------------+-------------------| | 9     6     3     | 5     7    #14    | 2     8    #14    | | 158   7     58    |#24    9     124   | 345   6     1345  | | 4     125   25    | 6     8     3     | 579   59    157   | *-----------------------------------------------------------*`

Here is my interpretation of that particular move... It's basically comprised of 3 intertwining turbot chains...

@: [r6c3]=4=[r6c9]-4-[r5c8]=4=[r1c8]-4-[r1c2]
#: [r6c3]=4=[r6c9]-4-[r7c9]=4=[r7c6]-4-[r8c4]=4=[r3c4]-4-[r3c2]
\$: [r5c2]=4=[r13c2]

So basically, if r6c3<>4 then both r13c2<>4, forcing r5c2=4
Therefore either r6c3=4 or r5c2=4, hence r5c3<>4.

Personally I think some of the forcing chains/nets produced by your solver are a bit too long... Feels like brute forcing... No offence intended...

Some typos edited
Last edited by udosuk on Thu Aug 10, 2006 8:22 am, edited 2 times in total.
udosuk

Posts: 2698
Joined: 17 July 2005

oh, I like that, a brute forcing chain...
maria45

Posts: 54
Joined: 23 October 2005

maria45 wrote:oh, I like that, a brute forcing chain...

So you will like this solution

1. r6c9=5,*r4c1=5*,r4c4=8,r3c5=2,r3c4=4,r2c6=7,r1c1=7,*r8c4=2*,*r6c6=2*,r4c8=2,*r2c9=2*
=> no 2 in column 1
After some singles:
2. r9c9=7,r9c2=1,r9c78=59,r8c79<>5,r3c9=5,*r3c2=4*,r7c1=9,r8c4=4,r7c6=1,r3c4=8,r8c7=8,
*r7c8=4*,*r12c7=46*,r4c1=8,*r5c3=7* => no 4 in row 5
ravel

Posts: 998
Joined: 21 February 2006

Thank You udosuk and ravel for your responses. I guess the final answer is that the elimination in question doesn't seem to have a Coloring counterpart.

Yes, udosuk, my Forcing Chains/Nets in this puzzle are best described as guessing ... along with my INVALID step. I normally disable XY-Chains and Forcing Chains/Nets in my solver. However, I was in the mood to throw the kitchen sink at a group of puzzles, and this puzzle caught my eye because I couldn't explain one of the Templates eliminations with Coloring. This has happened before and I decided to ask others if I was missing something important about Coloring.

I guess the only question now is whether or not a new technique is warranted for this elimination and others like it. What caused this elimination to occur at the Templates level instead of as a chain of some sort?

What do you think about solving this puzzle without my Forcing Chains/Nets?
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

Code: Select all
` *--------------------------------------------------------------------* | 257   X245    2567-4 | 1      3      478    | 4568  X245    9      | | 237    8      246    | 9      5      47     | 346    1      2346   | | 135   x145    9      |c48     2      6      | 3458   7      35-4   | |----------------------+----------------------+----------------------| | 2578   3      1      | 28     4      9      | 567    25     267    | | 6     X245    57-4 ? | 3      1      25     | 4579  X2459   8      | | 258    9     a2458   | 7      6      258    | 1      3     A245    | |----------------------+----------------------+----------------------| | 9      6      3      | 5      7     b14     | 2      8     B14     | | 158    7      58     |C24     9      124    | 345    6      1345   | | 4      125    25     | 6      8      3      | 579    59     157    | *--------------------------------------------------------------------*`

How about a colored x-wing, which is very similar to a finned x-wing.

a=A-B=b-C=c-x=X

Note that x is the only thing preventing the x-wing represented by X from being true. Color a and/or color X must be true. Both a and the X-wing represented by X take out the 4 in r5c3.
Myth Jellies

Posts: 593
Joined: 19 September 2005

Thank You MJ!!! I'd never realized that colors and a negative premise could be used in such a manner. You must have had a lot of fun tracking it down!
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006