Vidar's Monster #4

Advanced methods and approaches for solving Sudoku puzzles

Vidar's Monster #4

Postby vidarino » Fri Mar 17, 2006 6:54 pm

Yes, I think it's time for another one!

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


This one, like Monster #2 goes to work right from the start.:)

Since the earlier monsters I have improved my solver considerably, so it's fairly capable of dealing with them, but this one still gives it a good run for its money. I'm very interested in seeing how other solvers - manual or programs - deal with this.

It does have a few singleton magic cells, but solving those cells appear to be pretty darn tricky.

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Vidar's Monster #4

Postby AlexB » Sat Mar 18, 2006 11:20 pm

What a great puzzle! My VB6 based solver "The Su Doku Assistant" (http://www.stokepoges.plus.com) was stretched to the limit and took 8 seconds to find the unique solution. The steps it used are listed below.

AlexB

Prune R1C2 from 3579 to 359 (colouring of 7 starting at R1C2, leading to problem in row 5).
Prune R2C1 from 2357 to 235 (colouring of 7 starting at R2C1, leading to problem in row 5).
Prune R5C2 from 17 to 1 (inconsistency detected starting from R5C2 = 7).
Prune R5C4 from 1278 to 278 (in same row, R5C2 = 1).
Prune R5C8 from 128 to 28 (in same row, R5C2 = 1).
Prune R4C2 from 13579 to 3579 (in same column, R5C2 = 1).
Prune R4C2 from 3579 to 359 (inconsistency detected starting from R4C2 = 7).
Set R1C2 equal to 3 (no other candidate for R1C2 leads to a valid solution).
Prune R1C4 from 2378 to 278 (in same row, R1C2 = 3).
Prune R1C5 from 2358 to 258 (in same row, R1C2 = 3).
Prune R4C2 from 359 to 59 (in same column, R1C2 = 3).
Prune R2C1 from 235 to 25 (in same subgrid, R1C2 = 3).
Prune R2C5 from 235 to 3 (no other cell in same row can be a 3).
Prune R7C5 from 35689 to 5689 (in same column, R2C5 = 3).
Prune R7C4 from 3468 to 34 (only cells R7C4 and R7C9 in that row can be 3 or 4).
Prune R7C9 from 13469 to 34 (only cells R7C4 and R7C9 in that row can be 3 or 4).
Prune R7C7 from 1568 to 1 (no other cell in same row can be a 1).
Prune R2C7 from 157 to 57 (in same column, R7C7 = 1).
Prune R6C7 from 1678 to 678 (in same column, R7C7 = 1).
Prune R8C7 from 568 to 68 (in same column, R1C7 and R2C7 must be 5 or 7).
Prune R6C7 from 678 to 68 (in same column, R1C7 and R2C7 must be 5 or 7).
Prune R1C8 from 2459 to 249 (in same subgrid, R1C7 and R2C7 must be 5 or 7).
Prune R2C8 from 1245 to 124 (in same subgrid, R1C7 and R2C7 must be 5 or 7).
Prune R1C9 from 2479 to 249 (in same subgrid, R1C7 and R2C7 must be 5 or 7).
Prune R3C9 from 1279 to 129 (in same subgrid, R1C7 and R2C7 must be 5 or 7).
Prune R8C4 from 2368 to 236 (in row 7, R7C5 or R7C6 = 8 and pruned cell is in same subgrid).
Prune R8C6 from 2589 to 259 (in row 7, R7C5 or R7C6 = 8 and pruned cell is in same subgrid).
Prune R9C4 from 468 to 46 (in row 7, R7C5 or R7C6 = 8 and pruned cell is in same subgrid).
Prune R9C6 from 589 to 59 (in row 7, R7C5 or R7C6 = 8 and pruned cell is in same subgrid).
Prune R4C8 from 123 to 23 (colouring of 1 starting at R4C8, leading to problem in row 6).
Prune R1C9 from 249 to 29 (inconsistency detected starting from R1C9 = 2).
Prune R9C8 from 4589 to 589 (in column 9, R7C9 or R9C9 = 4 and pruned cell is in same subgrid).
Prune R3C2 from 579 to 79 (inconsistency detected starting from R3C2 = 5).
Prune R3C4 from 127 to 12 (inconsistency detected starting from R3C4 = 7).
Prune R1C3 from 24579 to 2459 (in row 3, R3C2 or R3C3 = 7 and pruned cell is in same subgrid).
Prune R2C3 from 2457 to 245 (in row 3, R3C2 or R3C3 = 7 and pruned cell is in same subgrid).
Prune R3C5 from 25 to 5 (inconsistency detected starting from R3C5 = 2).
Prune R3C3 from 2579 to 279 (in same row, R3C5 = 5).
Prune R1C5 from 258 to 28 (in same column, R3C5 = 5).
Prune R7C5 from 5689 to 689 (in same column, R3C5 = 5).
Prune R2C6 from 1257 to 127 (in same subgrid, R3C5 = 5).
Prune R1C5 from 28 to 8 (inconsistency detected starting from R1C5 = 2).
Prune R1C4 from 278 to 27 (in same row, R1C5 = 8).
Prune R6C5 from 2689 to 269 (in same column, R1C5 = 8).
Prune R7C5 from 689 to 69 (in same column, R1C5 = 8).
Prune R7C6 from 589 to 8 (no other cell in same row can be a 8).
Prune R5C4 from 278 to 8 (no other cell in same column can be a 8).
Prune R5C1 from 27 to 7 (no other cell in same row can be a 7).
Prune R5C8 from 28 to 2 (no other cell in same row can be a 2).
Prune R4C1 from 23579 to 2359 (in same column, R5C1 = 7).
Prune R6C1 from 2379 to 239 (in same column, R5C1 = 7).
Prune R9C1 from 5679 to 569 (in same column, R5C1 = 7).
Prune R6C3 from 279 to 29 (in same subgrid, R5C1 = 7).
Prune R6C6 from 12789 to 1279 (in same subgrid, R5C4 = 8).
Prune R1C8 from 249 to 49 (in same column, R5C8 = 2).
Prune R2C8 from 124 to 14 (in same column, R5C8 = 2).
Prune R4C8 from 23 to 3 (in same column, R5C8 = 2).
Prune R6C8 from 1238 to 138 (in same column, R5C8 = 2).
Prune R4C9 from 12367 to 1367 (in same subgrid, R5C8 = 2).
Prune R6C9 from 12367 to 1367 (in same subgrid, R5C8 = 2).
Prune R9C2 from 5789 to 7 (no other cell in same row can be a 7).
Prune R9C8 from 589 to 8 (no other cell in same row can be a 8).
Prune R8C2 from 589 to 8 (no other cell in same column can be a 8).
Prune R3C3 from 279 to 7 (no other cell in same column can be a 7).
Prune R8C8 from 3589 to 5 (no other cell in same column can be a 5).
Prune R1C8 from 49 to 9 (no other cell in same column can be a 9).
Prune R2C8 from 14 to 4 (no other cell in same subgrid can be a 4).
Prune R1C3 from 2459 to 4 (no other cell in same row can be a 4).
Prune R1C7 from 57 to 5 (no other cell in same row can be a 5).
Prune R1C4 from 27 to 7 (no other cell in same row can be a 7).
Prune R2C6 from 127 to 1 (no other cell in same row can be a 1).
Prune R2C7 from 57 to 7 (no other cell in same row can be a 7).
Prune R4C2 from 59 to 5 (no other cell in same column can be a 5).
Prune R3C2 from 79 to 9 (no other cell in same column can be a 9).
Prune R6C8 from 138 to 1 (no other cell in same column can be a 1).
Prune R3C4 from 12 to 2 (no other cell in same subgrid can be a 2).
Prune R3C9 from 129 to 1 (no other cell in same subgrid can be a 1).
Prune R1C9 from 29 to 2 (no other cell in same subgrid can be a 2).
Prune R6C7 from 68 to 8 (no other cell in same subgrid can be a 8).
Prune R4C4 from 1267 to 1 (no other cell in same column can be a 1).
Prune R8C7 from 68 to 6 (no other cell in same column can be a 6).
Prune R2C3 from 245 to 25 (in same column, R1C3 = 4).
Prune R4C6 from 1279 to 279 (in same column, R2C6 = 1).
Prune R6C6 from 1279 to 279 (in same column, R2C6 = 1).
Prune R8C4 from 236 to 36 (in same column, R3C4 = 2).
Prune R4C9 from 1367 to 367 (in same column, R3C9 = 1).
Prune R6C9 from 1367 to 367 (in same column, R3C9 = 1).
Prune R4C1 from 2359 to 239 (in same row, R4C2 = 5).
Prune R4C1 from 239 to 29 (in same row, R4C8 = 3).
Prune R4C9 from 367 to 67 (in same row, R4C8 = 3).
Prune R6C9 from 367 to 67 (in same subgrid, R4C8 = 3).
Prune R8C4 from 36 to 3 (in same row, R8C7 = 6).
Prune R8C9 from 369 to 39 (in same row, R8C7 = 6).
Prune R9C9 from 469 to 49 (in same subgrid, R8C7 = 6).
Prune R8C6 from 259 to 29 (in same row, R8C8 = 5).
Prune R6C1 from 239 to 3 (no other cell in same row can be a 3).
Prune R8C6 from 29 to 2 (no other cell in same row can be a 2).
Prune R8C9 from 39 to 9 (no other cell in same row can be a 9).
Prune R9C4 from 46 to 6 (no other cell in same column can be a 6).
Prune R9C6 from 59 to 5 (no other cell in same column can be a 5).
Prune R7C9 from 34 to 3 (no other cell in same column can be a 3).
Prune R9C9 from 49 to 4 (no other cell in same column can be a 4).
Prune R7C4 from 34 to 4 (no other cell in same subgrid can be a 4).
Prune R7C5 from 69 to 9 (no other cell in same subgrid can be a 9).
Prune R7C1 from 569 to 6 (no other cell in same row can be a 6).
Prune R9C1 from 569 to 9 (no other cell in same row can be a 9).
Prune R2C1 from 25 to 5 (no other cell in same column can be a 5).
Prune R2C3 from 25 to 2 (no other cell in same subgrid can be a 2).
Prune R7C3 from 59 to 5 (no other cell in same subgrid can be a 5).
Prune R4C1 from 29 to 2 (no other cell in same column can be a 2).
Prune R6C3 from 29 to 9 (no other cell in same column can be a 9).
Prune R4C5 from 269 to 69 (in same row, R4C1 = 2).
Prune R4C6 from 279 to 79 (in same row, R4C1 = 2).
Prune R6C5 from 269 to 26 (in same row, R6C3 = 9).
Prune R6C6 from 279 to 27 (in same row, R6C3 = 9).
Prune R4C5 from 69 to 6 (in same column, R7C5 = 9).
Prune R6C6 from 27 to 7 (in same column, R8C6 = 2).
Prune R4C6 from 79 to 9 (no other cell in same row can be a 9).
Prune R6C5 from 26 to 2 (no other cell in same row can be a 2).
Prune R6C9 from 67 to 6 (no other cell in same row can be a 6).
Prune R4C9 from 67 to 7 (no other cell in same column can be a 7).
AlexB
 
Posts: 1
Joined: 18 March 2006

Postby absolute beginner » Sun Mar 19, 2006 11:00 am

Hello AlexB
your logical steps are very poor described.
The first two are for example very tricky
and "Set R1C2 equal to 3 (no other candidate for R1C2 leads to a valid solution)." is just try and error.
I 'm not very satisfied with your solution.
But I haven't found a better one
absolute beginner
 
Posts: 22
Joined: 26 February 2006

Postby tarek » Sun Mar 19, 2006 12:16 pm

Another good one before....

This is my solver's log....
Difficulty Score: 310932 (Ultimate)
Non single moves: 17
Advanced moves: 17
Difficulty Index: 1........ (All non single moves were advanced...)
Non (Simple xy Chains): 8
Non (Simple xy chain) Index: 0.47
Guesses: 2 (2 contradiction eliminations needed & 2 Nishio eliminations)
Guessing Index: 0.11

Here are the 4 most difficult steps according to my solver, interesting to see how others would tackle these
Code: Select all
*-----------------------------------------------------------------*
| 1      3579   24579 | 2378   2358   6     | 57     2459   2479  |
| 2357   6      2457  | 9      235    1257  | 157    1245   8     |
| 8      579    2579  | 127    25     4     | 3      6      1279  |
|---------------------+---------------------+---------------------|
| 23579  3579   8     | 1267   269    1279  | 4      123    12367 |
| 27     1      6     | 278    4      3     | 9      28     5     |
| 2379   4      279   | 5      2689   12789 | 1678   1238   12367 |
|---------------------+---------------------+---------------------|
| 569    2      59    | 3468   35689  589   | 1568   7      13469 |
| 4      589    1     | 2368   7      2589  | 568    359    369   |
| 5679   5789   3     | 468    1      589   | 2      4589   469   |
*-----------------------------------------------------------------*
7 in r1c2 would make placing other 7s impossible (Nishio)
*-----------------------------------------------------------------*
| 1      359    24579 | 2378   2358   6     | 57     2459   2479  |
| 2357   6      2457  | 9      235    1257  | 157    1245   8     |
| 8      579    2579  | 127    25     4     | 3      6      1279  |
|---------------------+---------------------+---------------------|
| 23579  3579   8     | 1267   269    1279  | 4      123    12367 |
| 27     1      6     | 278    4      3     | 9      28     5     |
| 2379   4      279   | 5      2689   12789 | 1678   1238   12367 |
|---------------------+---------------------+---------------------|
| 569    2      59    | 3468   35689  589   | 1568   7      13469 |
| 4      589    1     | 2368   7      2589  | 568    359    369   |
| 5679   5789   3     | 468    1      589   | 2      4589   469   |
*-----------------------------------------------------------------*
7 in r2c1 would make placing other 7s impossible (Nishio)
*-----------------------------------------------------------------*
| 1      359    24579 | 2378   2358   6     | 57     2459   2479  |
| 235    6      2457  | 9      235    1257  | 157    1245   8     |
| 8      579    2579  | 127    25     4     | 3      6      1279  |
|---------------------+---------------------+---------------------|
| 23579  3579   8     | 1267   269    1279  | 4      123    12367 |
| 27     1      6     | 278    4      3     | 9      28     5     |
| 2379   4      279   | 5      2689   12789 | 1678   1238   12367 |
|---------------------+---------------------+---------------------|
| 569    2      59    | 3468   35689  589   | 1568   7      13469 |
| 4      589    1     | 2368   7      2589  | 568    359    369   |
| 5679   5789   3     | 468    1      589   | 2      4589   469   |
*-----------------------------------------------------------------*
1 in r4c8 would lead to a contradiction (Simple Guess)
*-----------------------------------------------------------------*
| 1      359    24579 | 2378   2358   6     | 57     2459   2479  |
| 235    6      2457  | 9      235    1257  | 157    1245   8     |
| 8      579    2579  | 127    25     4     | 3      6      1279  |
|---------------------+---------------------+---------------------|
| 23579  3579   8     | 1267   269    1279  | 4      23     12367 |
| 27     1      6     | 278    4      3     | 9      28     5     |
| 2379   4      279   | 5      2689   12789 | 1678   1238   12367 |
|---------------------+---------------------+---------------------|
| 569    2      59    | 3468   35689  589   | 158    7      1349  |
| 4      589    1     | 2368   7      2589  | 68     359    369   |
| 5679   5789   3     | 468    1      589   | 2      4589   469   |
*-----------------------------------------------------------------*
8 in r8c7 would lead to a contradiction (Simple Guess)



Another interesting point (there were only 3 possible ALS rule eliminations & were through a small number of nodes.....)...

Interesting to see how would the single-step NICE person would solve this:D

Tarek
User avatar
tarek
 
Posts: 2607
Joined: 05 January 2006

Postby vidarino » Sun Mar 19, 2006 1:24 pm

tarek, pretty much the same sticking points as myself, apart from the second one:

Grouped X-Cycle:
R2C1-7-R2C6=[R13C4]-7-R5C4=R5C1-7-R2C1 -> R2C1 <> 7

A.k.a. Hinge / Empty Rectangle.:)

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Re: Vidar's Monster #4

Postby foxglove » Sun Mar 19, 2006 1:33 pm

vidarino wrote:I'm very interested in seeing how other solvers - manual or programs - deal with this.
Vidar


This I had never seen!

Image

needs 2 /3 heuristic based guesses to solve (monster # 2 never needs 3)
foxglove
 
Posts: 12
Joined: 04 February 2006

Postby tarek » Sun Mar 19, 2006 1:50 pm

vidarino wrote:Grouped X-Cycle:
R2C1-7-R2C6=[R13C4]-7-R5C4=R5C1-7-R2C1 -> R2C1 <> 7
A.k.a. Hinge / Empty Rectangle.:)


Very good news, This illustrates how an elimination previously relegated to Nishio (a technique that heavily relies on the contradiction wording), can be eliminated using another technique (that relies on patterns & spacial geometry in its wording...)

It will absorb some of the Nishio eliminations, where contradiction comes from an empty box. As it will also absorb some other x-cylce eliminations, I think I would place it after the finned fish (nothing beats a pond full of fish).........

Tarek
User avatar
tarek
 
Posts: 2607
Joined: 05 January 2006

Postby absolute beginner » Sun Mar 19, 2006 9:03 pm

vidar, i think the following implications seem easier,
especially because they need no groups.

(a) r6c3=7 => 4c9 = 7 (last in block) => r4c5 = 7 (last in block)
=> r2c6 = 7 => r1c7 = 7
(b) r1c2=7 => r9c2 <> 7 => r9c1=1 => r6c3=7 (last in block)
so with (a) r1c2 <> 7
(c) r2c1=7 => r9c1 <> 7 => r9c2=7 => r6c3 = 7 (last in block)
so with (a) r2c1 <> 7

Ok, but thats excludes just two digits, but does not solve the puzzle
absolute beginner
 
Posts: 22
Joined: 26 February 2006

Postby Myth Jellies » Wed Mar 22, 2006 8:55 am

Code: Select all
*-----------------------------------------------------------------*
|*1     #3579  #24579 |*2378   2358   6     |#57*   #2459* #2479* |
|-2357   6      2457  | 9      235    1257  | 157    1245   8     |
|*8     #579   #2579  |*127    25     4     |#3*    #6*    #1279* |
|---------------------+---------------------+---------------------|
| 23579  3579   8     | 1267   269    1279  | 4      123    12367 |
|*27     1      6     |*278    4      3     |(9*)   (28*)  (5*)   |
| 2379   4      279   | 5      2689   12789 | 1678   1238   12367 |
|---------------------+---------------------+---------------------|
| 569    2      59    | 3468   35689  589   | 1568   7      13469 |
| 4      589    1     | 2368   7      2589  | 568    359    369   |
| 5679   5789   3     | 468    1      589   | 2      4589   469   |
*-----------------------------------------------------------------*

Heh, Frankenswordfish:)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby SHuisman » Thu Mar 23, 2006 10:33 pm

My own solver solved it with logic, it only needs a LOT off 'error net'-logic! I wish i could post a log, but it's in dutch. Maybe i'm reprogramming my solver to be compatible with other languages.
SHuisman
 
Posts: 17
Joined: 23 March 2006

Postby tarek » Fri Mar 24, 2006 4:19 am

SHuisman wrote:it's in dutch.
Don't let that stop you from posting it, couldn't we tell fom the numbers & symbols !!?

tarek
User avatar
tarek
 
Posts: 2607
Joined: 05 January 2006

Postby SHuisman » Fri Mar 24, 2006 1:00 pm

tarek wrote:
SHuisman wrote:it's in dutch.
Don't let that stop you from posting it, couldn't we tell fom the numbers & symbols !!?

tarek


The problem with my solver is the following;
It's 'log'-file is quite poor, and with this puzzle you will need a lot off:
If i put a Y in cel X, than another cel will have no candidates left after some basic elimination. Then Y can be removed as candidate.

I believe this technique is something like nishio / error net. I Should say it's more a guess-technique than logic. But some will say it is logic.

I finished my english version of my solver;
Downloadable here:
http://members.home.nl/sghuisman/

Now all i have to do is find some way to post it here, because the log is 'stored' in a list.
But it is always reproducable with my solver and the puzzle above (below as well):
Code: Select all
1....6....6.9....88....436...8...4....6.439.5.4.5......2.....7.4.1.7......3.1.2..
SHuisman
 
Posts: 17
Joined: 23 March 2006


Return to Advanced solving techniques

cron