Some nice toughies...

Advanced methods and approaches for solving Sudoku puzzles

Postby daj95376 » Tue May 16, 2006 4:21 pm

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

Postby gsf » Tue May 16, 2006 4:41 pm

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

Postby Pyrrhon » Wed May 17, 2006 5:56 am

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

Postby tarek » Wed May 17, 2006 10:49 am

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
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby Karlson » Wed May 17, 2006 1:26 pm

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 .|. . 2
8 . 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

Postby ravel » Wed May 17, 2006 3:30 pm

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

Postby Karlson » Wed May 17, 2006 3:46 pm

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

Postby daj95376 » Wed May 17, 2006 3:53 pm

Another invalid reply.
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

Postby ravel » Thu May 18, 2006 2:10 pm

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

Postby Karlson » Thu May 18, 2006 4:23 pm

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

Postby tarek » Fri May 19, 2006 6:56 am

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
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby ravel » Fri May 19, 2006 7:34 am

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

Postby Karlson » Fri May 19, 2006 12:10 pm

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

Postby tarek » Fri May 19, 2006 12:26 pm

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
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby ronk » Fri May 19, 2006 1:00 pm

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

Return to Advanced solving techniques