Meet My Nemesis!

Post the puzzle or solving technique that's causing you trouble and someone will help

Meet My Nemesis!

Postby Adak » Tue Mar 18, 2008 3:40 am

This is #8 from the Sudoku 17 file. My program solves it, but only by trial and error, which I'm trying to minimize. The program knows as much about solving Sudoku, as I do, so you see the problem.:D

The original grid:
Code: Select all
000|000|012
700|060|000
000|000|050
-----------
080|200|000
600|000|400
000|109|000
-----------
019|000|000
000|030|800
502|000|000



After some working out but no guessing yet, my program and I both get to this:
Code: Select all
. . . | . . . | . 1 2
7 . . | . 6 . | . . .
. . . | . . . | . 5 .
---------------------
. 8 . | 2 . 6 | . . .
6 . . | . . . | 4 . .
. . . | 1 . 9 | . . .
---------------------
8 1 9 | . . . | . . .
4 . . | . 3 . | 8 . .
5 3 2 | . . . | . . .



With pencil marks of:
Code: Select all
39    4569  34568 | 345789  5789  34578  | 3679
      2459  13458 | 34589         123458 | 39    3489   3489
1239  2469  13468 | 34789   12789 123478 | 3679         346789
--------------------------------------------------------------
139         13457 |         457          | 13579 379    13579
      2579  157   | 3578    578   3578   |       2789   15789
23    2457  3457  |         4578         | 23567 23678  35678
--------------------------------------------------------------
                  | 4567    257   2457   | 23567 23467  34567
       67   67    | 59            125    |       29     159
                  | 46789   1789  1478   | 1679  4679   14679



What solution method would you recommend to proceed with solving this?

Thanks in advance!
Adak
 
Posts: 10
Joined: 03 March 2008

Postby daj95376 » Tue Mar 18, 2008 5:32 am

You need to pick easier puzzles or else add a bunch of techniques to your solver.

Code: Select all
.......127...6...........5..8.2.....6.....4.....1.9....19..........3.8..5.2......

r8      -  67    Naked  Pair
    b5  -  3     Locked Candidate (1)
    b5  -  4     Locked Candidate (1)

Code: Select all
# you stop here
+--------------------------------------------------------------------------------------+
|  39       4569     34568   |  345789   5789     34578   |  3679     1        2       |
|  7        2459     13458   |  34589    6        123458  |  39       3489     3489    |
|  1239     2469     13468   |  34789    12789    123478  |  3679     5        346789  |
|----------------------------+----------------------------+----------------------------|
|  139      8        13457   |  2        457      6       |  13579    379      13579   |
|  6        2579     157     |  3578     578      3578    |  4        2789     15789   |
|  23       2457     3457    |  1        4578     9       |  23567    23678    35678   |
|----------------------------+----------------------------+----------------------------|
|  8        1        9       |  4567     257      2457    |  23567    23467    34567   |
|  4        67       67      |  59       3        125     |  8        29       159     |
|  5        3        2       |  46789    1789     1478    |  1679     4679     14679   |
+--------------------------------------------------------------------------------------+

Code: Select all
r258    -  1     222 Swordfish
r258    -  2     222 Swordfish
r3      -  12    Hidden Pair
  c6    -  12    Hidden Pair

Code: Select all
# SSTS stops here
 *-----------------------------------------------------------------------------*
 | 39      4569    34568   | 345789  5789    34578   | 3679    1       2       |
 | 7       2459    13458   | 34589   6       12      | 39      3489    3489    |
 | 12      469     3468    | 34789   12      3478    | 3679    5       346789  |
 |-------------------------+-------------------------+-------------------------|
 | 139     8       3457    | 2       457     6       | 13579   379     3579    |
 | 6       2579    157     | 3578    578     3578    | 4       2789    15789   |
 | 23      457     3457    | 1       4578    9       | 23567   3678    35678   |
 |-------------------------+-------------------------+-------------------------|
 | 8       1       9       | 4567    257     457     | 23567   3467    34567   |
 | 4       67      67      | 59      3       12      | 8       29      159     |
 | 5       3       2       | 46789   1789    478     | 1679    4679    4679    |
 *-----------------------------------------------------------------------------*

Code: Select all
[r3c1]=2 => [r4c1]=1,[r6c1]=3 => contradiction in [b4]; => [r3c1]<>2
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Adak » Tue Mar 18, 2008 8:15 am

It is a hellion isn't it?:)

In the Sudoku17 file of 99 games, my program spends about 1/3rd of the total solution time, JUST solving this ONE game.:( Only about 12 games require any guessing, at all.

I've added Locked1() and Locked2() functions just recently, and re-wrote my outside RuleOfPairs(), because it was found to be flawed.

I'm ready to code up my next solving function, as soon as I get a chance to get my head around the next solving technique.

Sometimes, reading over the list, I wonder just how much of what kind of spirits were needed to think these things up -- my my!:D:D Mad props to all of the originators, of course.:!:
Adak
 
Posts: 10
Joined: 03 March 2008

Postby eleven » Tue Mar 18, 2008 9:03 am

This is a strange puzzle. daj95376's 4 cell-chain solves it alone. Its there from the beginning, the rest is singles (no locked candidates, no pairs, no swordfish needed).
To rewrite it for the original grid:
Code: Select all
+--------------------------------------------------------------------------------------+
|  39       4569     34568   |  345789   45789    34578   |  3679     1        2       |
|  7        2459     13458   |  34589    6        123458  |  39       3489     3489    |
|  1239     2469     13468   |  34789    124789   123478  |  3679     5        346789  |
|----------------------------+----------------------------+----------------------------|
|  139      8        13457   |  2        457      6       |  13579    379      13579   |
|  6        2579     1357    |  3578     578      3578    |  4        23789    135789  |
|  23       2457     3457    |  1        4578     9       |  23567    23678    35678   |
|----------------------------+----------------------------+----------------------------|
|  8        1        9       |  4567     2457     2457    |  23567    23467    34567   |
|  4        67       67      |  5679     3        1257    |  8        2679     15679   |
|  5        3        2       |  46789    14789    1478    |  1679     4679     14679   |
+--------------------------------------------------------------------------------------+
r5c2=2 -> r4c1=9 -> r3c1=1 -> r6c1=2, so r5c2<>2 and r5c8=2
eleven
 
Posts: 1537
Joined: 10 February 2008

Meet My Nemesis!

Postby Cec » Tue Mar 18, 2008 9:46 am

daj95376 wrote:
Code: Select all
[r3c1]=2 => [r4c1]=1,[r6c1]=3 => contradiction in [b4]; => [r3c1]<>2

Hi daj95376,

I "read" your above notation as follows...

If r3c1=2 then
r4c1=1 then
r6c1=3

Why does this notation lead to a contradiction in box4 to conclude that r3c1 does not equal 2.

I have assumed [b4] means box4. Some members use alphabet letters a to j to identify the nine rows in lieu of using numbers 1 to 9 for the nine rows so that b4 means the cell in row2 column4)

Cec
Cec
 
Posts: 1039
Joined: 16 June 2005

Re: Meet My Nemesis!

Postby ronk » Tue Mar 18, 2008 10:34 am

Cec wrote:Why does this notation lead to a contradiction in box4 to conclude that r3c1 does not equal 2.
[edit: reduced quote]

Only possible location for both digits 2 & 9 is r5c2 or, alternatively, only three digits available for four cells.

Nice loop notation is more informative: r3c1 -2- r6c1 =2= r5c2 =9= r4c1 =1= r3c1, implies r3c1<>2
Last edited by ronk on Tue Mar 18, 2008 8:38 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Meet My Nemesis!

Postby Cec » Tue Mar 18, 2008 12:17 pm

ronk wrote:"...Only possible location for both digits 2 & 9 is r5c2 or, alternatively, only three digits available for four cells.

Thanks ronk. I was incorrectly looking at Adak's earlier grid rather than daj95376's later grid where the 2 was excluded from r6c2.

Cec
Cec
 
Posts: 1039
Joined: 16 June 2005

Postby Pat » Tue Mar 18, 2008 3:12 pm

Adak wrote:This is #8 from the Sudoku 17 file --

Code: Select all

.......127...6...........5..8.2.....6.....4.....1.9....19..........3.8..5.2......


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



In the Sudoku17 file of 99,
my program spends about 1/3rd of the total solution time
JUST solving this ONE


actually it is puzzle 11 in the list which has now reached 47693
    what's this list of 99 puzzles ??
User avatar
Pat
 
Posts: 3425
Joined: 18 July 2005

Re: Meet My Nemesis!

Postby daj95376 » Tue Mar 18, 2008 3:15 pm

Cec wrote:
daj95376 wrote:
Code: Select all
[r3c1]=2 => [r4c1]=1,[r6c1]=3 => contradiction in [b4]; => [r3c1]<>2

I "read" your above notation as follows...

If r3c1=2 then
r4c1=1 then
r6c1=3

[r3c1] forces both results concurrently. If [r3c1]=2 then [r4c1]=1 and [r6c1]=3.

Note: I haven't yet implemented chains in my new solver, so I do as best I can with the networks supported by my old solver. Thanks ronk and eleven for the nicer chains!
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Adak » Tue Mar 18, 2008 5:05 pm

Pat wrote:
Adak wrote:This is #8 from the Sudoku 17 file --

Code: Select all

.......127...6...........5..8.2.....6.....4.....1.9....19..........3.8..5.2......


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



In the Sudoku17 file of 99,
my program spends about 1/3rd of the total solution time
JUST solving this ONE


actually it is puzzle 11 in the list which has now reached 47693
    what's this list of 99 puzzles ??


I first became interested in Sudoku 2 years ago, and immediately wanted to program a solver, but didn't know anything about it. So I went on-line and visited a few sites explaining the basics, like using pencilmarks, etc., and wrote my first solver.

It was working well, so I wanted to try it out on some real hard one's. Went back on-line, and found out all Sudoku puzzles don't have to have at least 23 given digits as I had been informed earlier.:( That when I found this Sudoku 17.txt file.

Don't know how many puzzles it had, but I only have 99. Each has just 17 givens. This is the first 8 that I have from that file:
Code: Select all
000000010400000000020000000000050407008000300001090000300400200050100000000806000
000000010400000000020000000000050604008000300001090000300400200050100000000807000
000000012000035000000600070700000300000400800100000000000120000080000040050000600
000000012050400000000000030700600400001000000000080000920000800000510700000003000
000000012300000060000040000900000500000001070020000000000350400001400800060000000
000000012400090000000000050070200000600000400000108000018000000000030700502000000
000000012500008000000700000600120000700000450000030000030000800000500700020000000
000000012700060000000000050080200000600000400000109000019000000000030800502000000


Number 8, the last one from this short sample, is one of the toughest for my solver, (version 2, a major re-write), requiring a good deal of trial and error.

I tried it with Simple Sudoku, and another on-line solver, but they won't solve it. (Although SS did find two Swordfish patterns which my solver doesn't know about, yet).

I use these 99 games as a testbed for my solver. It tells me how many games were solved via logic, and how many were solved via trial and error. I'm trying to minimize the latter.

Thanks for your interest and info.
Last edited by Adak on Wed Mar 19, 2008 5:05 pm, edited 1 time in total.
Adak
 
Posts: 10
Joined: 03 March 2008

re: 17 clues

Postby Pat » Tue Mar 18, 2008 5:31 pm

Adak wrote:
I found this Sudoku 17.txt file

Don't know how many puzzles it had,
but I only have 99

This is the first 8 that I have from that file
Code: Select all
.......1.4.........2...........5.4.7..8...3....1.9....3..4..2...5.1........8.6...
.......1.4.........2...........5.6.4..8...3....1.9....3..4..2...5.1........8.7...
.......12....35......6...7.7.....3.....4..8..1...........12.....8.....4..5....6..
.......12.5.4............3.7..6..4....1..........8....92....8.....51.7.......3...
.......123......6.....4....9.....5.......1.7..2..........35.4....14..8...6.......
.......124...9...........5..7.2.....6.....4.....1.8....18..........3.7..5.2......
.......125....8......7.....6..12....7.....45.....3.....3....8.....5..7...2.......
.......127...6...........5..8.2.....6.....4.....1.9....19..........3.8..5.2......



the big list of 17-clue puzzles has now been updated to include 47621 puzzles
User avatar
Pat
 
Posts: 3425
Joined: 18 July 2005

Postby daj95376 » Tue Mar 18, 2008 6:00 pm

Pat, do you know if anyone has tested the latest 17-clue puzzles to see how many can't be solved with SSTS? It might be an interesting subset.

[Withdrawn: I managed to reduce the current Sudoku17 file to 924 (partially-solved) entries that require more than my solver can handle without resorting to chains/networks. This is too many entries to post!]
Last edited by daj95376 on Tue Mar 18, 2008 6:29 pm, edited 2 times in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: re: 17 clues

Postby ronk » Tue Mar 18, 2008 6:07 pm

Pat wrote:the big list of 17-clue puzzles has now been updated to include 47621 puzzles

It was 47,693 just a few posts ago. First time for everything, I guess.:D
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Adak » Tue Mar 18, 2008 8:29 pm

I ran this puzzle through Simple Sudoku, which could not find the solution. (Although it came closer to it than I did).

Today, I put the puzzle into Sudoku Explorer, which can not find a solution either, but gives a message that there are two solutions, before quitting.

Are there more than two solutions to any of the Sudoku 17 puzzles? Or did the hard puzzle just "bust" Sudoku Explorer?

Edit: Ran this just now through Sudoku Cracker 2008, and it found the Swordfish and removed a few more candidates than my program. It could not find any more answering digits, however.

It then stopped giving any more single steps or hints, when I clicked on "Solve", it found the answer very quickly, however. Obviously the last part was done by trail and error, very efficiently.
Adak
 
Posts: 10
Joined: 03 March 2008

Postby eleven » Wed Mar 19, 2008 9:00 am

This is a very moderate advanced puzzle, solvable by a single 4-cell chain and there should be many free solvers around, which do not have a problem with it. E.g. look at these links: http://forum.enjoysudoku.com/viewtopic.php?p=42972#p42972
eleven
 
Posts: 1537
Joined: 10 February 2008

Next

Return to Help with puzzles and solving techniques