## Some nice toughies...

Advanced methods and approaches for solving Sudoku puzzles
Clear this as well.
Last edited by daj95376 on Wed Jun 07, 2006 3:36 am, edited 1 time in total.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

daj95376 wrote:When I started my solver, I knew there was a long list of techniques ahead for me to implement. I wrote the basics -- Naked/Hidden Singles/Pairs/Triples/Quads and Locked Candidates (1&2). Then I stopped and took a deep breath before implementing X-Wing, Swordfish, and Jellyfish.

At this point, I stopped again to consider the increasingly complex (and often convoluted) techniques that lay ahead.

its good to stop and ponder at this point
so many techniques with so many cute names pop up here that
we need to stand back a bit and think about some unifying properties
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Looking at daj95376's points which increases the difficulty of a sudoku (it seems to be a generalization of the magic points) with brute force could be an interesting approach for those programers which are interested to find a short and human-understandable proof of a solution rather than to install a human-like method to find such a proof. With other words: It could be a method to simplify the deductive proofs of a solution.

Another way to simplify proofs would be simply to check whether we can skip one of the more complicated techniques and use a later one instead getting a stage where the first one is not further necessary (and so having a less number of complicate steps).

By the way statistics about the methods with which we can catch these semi-magic points deductively (after finding them with brute force) could be improve the order of techniques in a sudoku program which is aimed to get fast sudoku solutions and does not use brute force techniques.

Pyrrhon
Pyrrhon

Posts: 240
Joined: 26 April 2006

daj95376 wrote:When I encounter an invalid candidate in a cell with two candidates, then I report the valid candidate as leading to a solution -- instead of the invalid candidate leading to a contradiction.

Hi there daj,

What is the purpose of the above statement ? .......& how do you choose the VALID candidates from the INVALID candidates?

When you report INVALID candidates you automatically use the VALID candidates because they will lead to the solution.

tarek

tarek

Posts: 2650
Joined: 05 January 2006

Here is another very tough one for you:
#5:
Code: Select all
`.3.8.....1.5.......4...952.....9...28.1..5.7.....1...4...5.724..9.2..8..4........`

Code: Select all
`. 3 .|8 . .|. . .1 . 5|. . .|. . .. 4 .|. . 9|5 2 .-----+-----+-----. . .|. 9 .|. . 28 . 1|. . 5|. 7 .. . .|. 1 .|. . 4-----+-----+-----. . .|5 . 7|2 4 .. 9 .|2 . .|8 . .4 . .|. . .|. . .`

Solve it without guessing and have fun
Karlson

Posts: 26
Joined: 14 May 2006

This one is not so hard:
Code: Select all
`29     3       2679    |   8     5       246     |   467     16     167        1      2678    5       |   346   23467   2346    |   3467    9      3678       67     4       678     |   1     367     9       |   5       2      3678   ----------------------------------------------------------------------------    3567   567     4       |   367   9       368     |   1       58     2          8      26      1       |   346   2346    5       |   9       7      36         29     2567    23679   |   367   1       2368    |   36      58     4          ----------------------------------------------------------------------------    36     1       368     |   5     368     7       |   2       4      9          3567   9       367     |   2     346     1346    |   8       136    1567       4      25678   23678   |   9     368     136     |   67      136    1567       `

r3c5=7 => r3c1=6 => r7c1=3 => r6c3=3 => r6c7=6 => r2c7=3 => r3c5=3
=> r2c5=7
ravel

Posts: 998
Joined: 21 February 2006

Yea, you are right - I posted the false one
This one is it:
#6:
Code: Select all
`...........16394..8.......94...9...5.6...8.2...7..31.42.......1..94213...........`

Code: Select all
`. . .|. . .|. . .. . 1|6 3 9|4 . .8 . .|. . .|. . 9-----+-----+-----4 . .|. 9 .|. . 5. 6 .|. . 8|. 2 .. . 7|. . 3|1 . 4-----+-----+-----2 . .|. . .|. . 1. . 9|4 2 1|3 . .. . .|. . .|. . .`
Karlson

Posts: 26
Joined: 14 May 2006

Last edited by daj95376 on Wed Jun 07, 2006 3:37 am, edited 1 time in total.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

Karlson wrote:#6:
Code: Select all
`. . .|. . .|. . .. . 1|6 3 9|4 . .8 . .|. . .|. . 9-----+-----+-----4 . .|. 9 .|. . 5. 6 .|. . 8|. 2 .. . 7|. . 3|1 . 4-----+-----+-----2 . .|. . .|. . 1. . 9|4 2 1|3 . .. . .|. . .|. . .`

This puzzle (again 3 steps for my program) for a long time looks easier than it is. With a swordfish, 2 type4 URs, 2 short chains (r4c3<>8 and r6c8<>9), a longer one, that ended in a 6-cell uniqueness pattern (r4c2<>1) and an xy-chain (r8c2=5 -> r2c1=7) i came here. It looks easy with all the pairs, but i could not finish it without a monster chain (e.g. r1c1<>3). Maybe i missed another uniqueness trick ?
Code: Select all
`357    9      2346  |  8      17    24  |  2567   13   267        57     25     1     |  6      3     9   |  4      58   278        8      234    2346  |  5      17    24  |  267    13   9       ----------------------------------------------------------   4      23     23    |  1      9     6   |  8      7    5          1      6      5     |  7      4     8   |  9      2    3          9      8      7     |  2      5     3   |  1      6    4          ----------------------------------------------------------   2      3457   348   |  39     68    57  |  567    49   1          56     57     9     |  4      2     1   |  3      58   678        356    1      348   |  39     68    57  |  2567   49   267        `
ravel

Posts: 998
Joined: 21 February 2006

there is an empty rectangle of 5s:
Code: Select all
`357*   9      2346  |  8      17    24  |  2567   13   267       57*    25*    1     |  6      3     9   |  4      58*  278       8      234    2346  |  5      17    24  |  267    13   9       ----------------------------------------------------------   4      23     23    |  1      9     6   |  8      7    5         1      6      5     |  7      4     8   |  9      2    3         9      8      7     |  2      5     3   |  1      6    4         ----------------------------------------------------------   2      3457   348   |  39     68    57  |  567    49   1         56-    57     9     |  4      2     1   |  3      58*  678       356    1      348   |  39     68    57  |  2567   49   267 `

then a few dual implication chains and nice loops solve it
Karlson

Posts: 26
Joined: 14 May 2006

daj95376 wrote:My emphasis was on finding cell candidates that produced invalid puzzles if used.

However, to keep my solver from printing out two equivalent statements for a cell with two candidates when one is removed, I only report the assignment of the final cell value. Thus, my solver's output would seem to conflict with the statements I made about finding invalid cell candidates. I added this statement to explain this contradiction.

I'm sorry if it was confusing!

PS: I'm in the process of updating my solver so that it lists the chain associated with an invalid cell candidate. Without validation, my results seem to lack acceptability.

That seems fine, you have to keep in mind that contradiction elimination is considered by most of us as Guessing & therefore should be in the outermost loop in your solver......

having said that, any other technique [although more complex] which does not have contradiction elimination takes preference in our discussions in the advanced techniques, & a better solver or solution would have fewer contradiction eliminations IMO.

tarek

tarek

Posts: 2650
Joined: 05 January 2006

Karlson wrote:there is an empty rectangle of 5s:
then a few dual implication chains and nice loops solve it

Thanks, in fact i had seen the ER, but it did not help much and i forgot to save the candidate list.
Could you please spell out the chains and loops, then i could write down an overall solution.

PS: Looking at it again now, this chain (of "acceptable" length) plus the ER would solve it:
r9c1=5 => r1c1=3 => r1c8=1 => r1c5=7
r9c1=5 => r2c1=7,r2c2=5 => r2c8=8 => r2c9=2 => r1c7=2 (=> r9c9<>2)
r9c1=5 => r9c6=7 => r9c9=6
=> r1c9 is empty
ravel

Posts: 998
Joined: 21 February 2006

After the ER we arrive here:
Code: Select all
` 357  9    2346 | 8    17   24   | 2567 13   267  57   25   1    | 6    3    9    | 4    58   278  8    234  2346 | 5    17   24   | 267  13   9   ----------------+----------------+---------------- 4    23   23   | 1    9    6    | 8    7    5    1    6    5    | 7    4    8    | 9    2    3    9    8    7    | 2    5    3    | 1    6    4   ----------------+----------------+---------------- 2    3457 348  | 39   68   57   | 567  49   1    6    57   9    | 4    2    1    | 3    58   78   35   1    348  | 39   68   57   | 2567 49   267 `

chain 1:
R8C2=5 => R7C2=7 => R7C6=5 (5 in R7)
R8C2=7 => R8C8=5 => R2C8=8 => R1C7=5 (5 in C7)
=> R7C7 <> 5
nice loop:
R1C7=6 => R9C7=5 => R9C9=2 => R1C9=6 => R1C7<>6
Code: Select all
` 357  9    2346 | 8    17   24   | 257  13   267  57   25   1    | 6    3    9    | 4    58   278  8    234  2346 | 5    17   24   | 267  13   9   ----------------+----------------+---------------- 4    23   23   | 1    9    6    | 8    7    5    1    6    5    | 7    4    8    | 9    2    3    9    8    7    | 2    5    3    | 1    6    4   ----------------+----------------+---------------- 2    3457 348  | 39   68   57   | 67   49   1    6    57   9    | 4    2    1    | 3    58   78   35   1    348  | 39   68   57   | 2567 49   267 `

Does anyone find a simple nice loop here because I can only find a long dual implication chain here...
Karlson

Posts: 26
Joined: 14 May 2006

Code: Select all
`*--------------------------------------------------------*|^357   9     2346 | 8     17    24   | 257   13    267  ||^57   *25    1    | 6     3     9    | 4     58    278  || 8    -234   2346 | 5     17    24   | 267   13    9    ||------------------+------------------+------------------|| 4    *23    23   | 1     9     6    | 8     7     5    || 1     6     5    | 7     4     8    | 9     2     3    || 9     8     7    | 2     5     3    | 1     6     4    ||------------------+------------------+------------------|| 2     3457  348  | 39    68    57   | 67    49    1    || 6     57    9    | 4     2     1    | 3     58    78   || 35    1     348  | 39    68    57   | 2567  49    267  |*--------------------------------------------------------*Eliminating 3 from r3c2(ALS-XZ A=235 in r4c2, r2c2 B=357 in r2c1, r1c1  x=5 z=3)`

Then there is a Type 4 UR

tarek

tarek

Posts: 2650
Joined: 05 January 2006

You guys are waay out in front with #6. Would someone please tell me how to get past this point?
Code: Select all
` 35679 234579 23456  | 8     157   24   | 2567  13567 2367 57    257    1      | 6     3     9    | 4     578   278 8     23457  23456  | 57    157   24   | 2567  13567 9---------------------+------------------+------------------ 4     123    238    | 17    9     67   | 68    37    5 135   6      35     | 157   4     8    | 9     2     37 59    589    7      | 2     56    3    | 1     68    4---------------------+------------------+------------------ 2     3457   34568  | 39    678   567  | 5678  49    1 567   578    9      | 4     2     1    | 3     5678  678 13567 13457  34568  | 39    678   567  | 25678 49    267`
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext