Question

Everything about Sudoku that doesn't fit in one of the other sections

Postby bennys » Fri Jan 06, 2006 11:58 pm

Are you sure about this one?

Code: Select all
+-------------------------+-------------------------+-------------------------+
| 145     25      3       | 12456   12456   16      | 7       8       9       |
| 459     259     24569   | 7       8       69      | 1       3       2456    |
| 145789  25789   1245689 | 124569  1234569 1369    | 2456    456     2456    |
+-------------------------+-------------------------+-------------------------+
| 2       3       59      | 1569    15679   4       | 56      5679    8       |
| 6       1       4589    | 2589    2579    789     | 2345    4579    23457   |
| 45789   5789    4589    | 3       25679   6789    | 2456    45679   1       |
+-------------------------+-------------------------+-------------------------+
| 138     6       7       | 148     134     5       | 9       2       34      |
| 13589   2589    12589   | 14689   134679  136789  | 34568   14567   34567   |
| 13589   4       1589    | 1689    13679   2       | 3568    1567    3567    |
+-------------------------+-------------------------+-------------------------+
In row 1 6 appear only in the second box so I can eliminate 6(that is elementary technic)
from r2c6 and i get using elementary technics.



+----------------+----------------+----------------+
| 1    2    3    | 4    5    6    | 7    8    9    |
| 4    5    6    | 7    8    9    | 1    3    2    |
| 78   78   9    | 2    3    1    | 5    4    6    |
+----------------+----------------+----------------+
| 2    3    5    | 19   19   4    | 6    7    8    |
| 6    1    8    | 5    2    7    | 34   9    34   |
| 79   79   4    | 3    6    8    | 2    5    1    |
+----------------+----------------+----------------+
| 38   6    7    | 18   14   5    | 9    2    34   |
| 589  89   2    | 6    479  3    | 48   1    57   |
| 3589 4    1    | 89   79   2    | 38   6    57   |
+----------------+----------------+----------------+

and here for example picking r4c4=1 solve it.
bennys
 
Posts: 156
Joined: 28 September 2005

Postby evert » Sat Jan 07, 2006 7:08 pm

My interpretation of the question is: you want an example of a valid puzzle in a stage where
-neither solving technics
-nore unnested single guesses combined with solving technics
can remove candidates or fill cells. Is that correct?

Of course the answer is related to the actually allowed solving technics.
Maybe we find an example for you today and tomorrow we invent a new solving technics that solves it.

Other question (just curious) why do you want what you want? What's your aim?
evert
 
Posts: 186
Joined: 26 August 2005

Postby bennys » Sat Jan 07, 2006 9:21 pm

Regarding the solving technics we can assume Pappocom-Hard technics.
About why I ask the reason is that I feel that there must be a puzzle like that but trying some of "Hardest known" and others I couldn't find any.
bennys
 
Posts: 156
Joined: 28 September 2005

Postby evert » Sat Jan 07, 2006 11:49 pm

The situation you look for is quite specific.
I think someone should write a program that looks for this situation.
But the chance to find it in existing puzzles will be almost zero I guess.

What's your experience in writing computer programs?
evert
 
Posts: 186
Joined: 26 August 2005

Postby Moschopulus » Sun Jan 08, 2006 2:05 am

I think gsf may only be assuming very basic techniques, when he answered.

Your technique in the above puzzle (to eliminate 6) is a further step than very basic elimination. I don't know the names of the techniques.

That may explain the difference between you. If we only allow very basic techniques then this puzzle is 2-constrained. I know that if we allow more techniques, there are no 2-constrained puzzles found yet, but I don't know the details of which techniques are allowed and which are not.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby ronk » Sun Jan 08, 2006 4:58 am

Hi bennys,

Assume that after exhausting "basic techniques", one sequentially guesses (T&E) as TRUE each candidate in each cell (on an unnested basis) ... and after each guess uses only techniques known as naked singles and hidden singles ... until an elimination based on a contradiction can be made.

Further assume that after each single T&E elimination, one returns to using "basic techniques" ... again until no further progress can be made ... and then repeats the T&E.

Repeating the above, the puzzle will either be solved, or the puzzle will remain unsolved because an elimination by the T&E method cannot be found.

AFAIK there are only two known puzzles that do not fall to the above method. So if, after each guess, you allow more advanced techniques than naked singles and hidden singles ... I doubt a puzzle exists that would not be thusly solved.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby gsf » Sun Jan 08, 2006 7:28 am

ronk wrote:AFAIK there are only two known puzzles that do not fall to the above method. So if, after each guess, you allow more advanced techniques than naked singles and hidden singles ... I doubt a puzzle exists that would not be thusly solved.

do you have a pointer to these two?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gsf » Sun Jan 08, 2006 7:37 am

Moschopulus wrote:I think gsf may only be assuming very basic techniques, when he answered.

correct, thanks M
here is the only known FNBT-2-constrained 9x9 (elementary + box + tuple constraints allowed)
Code: Select all
.2.|...|6..
...|1..|...
7..|.3.|.5.
---+---+---
..8|.4.|9.3
3..|...|..8
...|.2.|4.6
---+---+---
63.|5..|...
..5|..9|..2
.1.|.84|...
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby bennys » Sun Jan 08, 2006 9:27 am

I dont think i can write a computer program.
I think the technic is what gsf call box
again I dont think its a good example.
Code: Select all
+-------+-------+-------+
| . 2 . | . . . | 6 . . |
| . . . | 1 . . | . . . |
| 7 . . | . 3 . | . 5 . |
+-------+-------+-------+
| . . 8 | . 4 . | 9 . 3 |
| 3 . . | . . . | . . 8 |
| . . . | . 2 . | 4 . 6 |
+-------+-------+-------+
| 6 3 . | 5 . . | . . . |
| . . 5 | . . 9 | . . 2 |
| . 1 . | . 8 4 | . . . |
+-------+-------+-------+

+----------------------+----------------------+----------------------+
| 14589  2      1349   | 4789   579    578    | 6      134789 1479   |
| 4589   45689  3469   | 1      5679   25678  | 2378   234789 479    |
| 7      4689   1469   | 24689  3      268    | 128    5      149    |
+----------------------+----------------------+----------------------+
| 125    567    8      | 67     4      1567   | 9      127    3      |
| 3      45679  124679 | 679    15679  1567   | 1257   127    8      |
| 159    579    179    | 3789   2      13578  | 4      17     6      |
+----------------------+----------------------+----------------------+
| 6      3      2479   | 5      17     127    | 178    14789  1479   |
| 48     478    5      | 367    167    9      | 1378   134678 2      |
| 29     1      279    | 2367   8      4      | 357    3679   579    |
+----------------------+----------------------+----------------------+


from here we get


+-------------------+-------------------+-------------------+
| 14589 2     1349  | 479   579   78    | 6     3489  1479  |
| 4589  45689 3469  | 1     5679  2678  | 2378  3489  479   |
| 7     4689  1469  | 2469  3     268   | 128   5     149   |
+-------------------+-------------------+-------------------+
| 12    67    8     | 67    4     5     | 9     12    3     |
| 3     467   2467  | 679   1679  167   | 5     27    8     |
| 159   579   179   | 8     2     3     | 4     17    6     |
+-------------------+-------------------+-------------------+
| 6     3     2479  | 5     17    127   | 178   489   1479  |
| 48    478   5     | 367   167   9     | 137   346   2     |
| 29    1     279   | 2367  8     4     | 37    369   5     |
+-------------------+-------------------+-------------------+


now trying r4c2=7 lead to contradiction and we get


+-------------------+-------------------+-------------------+
| 14589 2     1349  | 49    579   78    | 6     3489  1479  |
| 4589  4589  3469  | 1     5679  2678  | 2378  3489  479   |
| 7     489   1469  | 2469  3     268   | 128   5     149   |
+-------------------+-------------------+-------------------+
| 12    6     8     | 7     4     5     | 9     12    3     |
| 3     47    247   | 69    169   16    | 5     27    8     |
| 159   579   179   | 8     2     3     | 4     17    6     |
+-------------------+-------------------+-------------------+
| 6     3     2479  | 5     17    127   | 178   489   1479  |
| 48    478   5     | 36    167   9     | 137   346   2     |
| 29    1     279   | 236   8     4     | 37    369   5     |
+-------------------+-------------------+-------------------+



now puting r8c2=8 or r8c2=4 lead to contradiction and we get



+-------------+-------------+-------------+
| 15  2   13  | 4   59  78  | 6   389 179 |
| 4   58  36  | 1   59  678 | 2   389 79  |
| 7   89  169 | 2   3   68  | 18  5   4   |
+-------------+-------------+-------------+
| 12  6   8   | 7   4   5   | 9   12  3   |
| 3   4   27  | 9   6   1   | 5   27  8   |
| 159 59  179 | 8   2   3   | 4   17  6   |
+-------------+-------------+-------------+
| 6   3   4   | 5   7   2   | 18  89  19  |
| 8   7   5   | 6   1   9   | 3   4   2   |
| 29  1   29  | 3   8   4   | 7   6   5   |
+-------------+-------------+-------------+

now puting r1c1=1 solve it
bennys
 
Posts: 156
Joined: 28 September 2005

Postby gsf » Sun Jan 08, 2006 10:59 am

bennys wrote:again I dont think its a good example.
Code: Select all
now trying r4c2=7 lead to contradiction and we get
now puting r8c2=8 or r8c2=4 lead to contradiction and we get
now puting r1c1=1 solve it

you solved this puzzle using three guesses
that's one more than you asked for:
bennys wrote:I will not be able to make any progress (progress is finding placement or removing candidate) using elementary techniques.
And for any pick of candidate in any cell if I move foreword using
Elementary techniques I will get stucked again.

btw, how is it that all your guesses were the correct ones?
suppose you had tried r4c2=6 first?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ronk » Sun Jan 08, 2006 12:40 pm

gsf wrote:
ronk wrote:AFAIK there are only two known puzzles that do not fall to the above method. So if, after each guess, you allow more advanced techniques than naked singles and hidden singles ... I doubt a puzzle exists that would not be thusly solved.

do you have a pointer to these two?

Puzzle #2 of the top1465.
Code: Select all
 7.8|...|3..
 ...|2.1|...
 5..|...|...
 ---+---+---
 .4.|...|.26
 3..|.8.|...
 ...|1..|.9.
 ---+---+---
 .9.|6..|..4
 ...|.7.|5..
 ...|...|...


 7       126     8       | 459     4569    4569    | 3       1456    125
 469     36      3469    | 2       3456    1       | 4679    45678   578
 5       1236    123469  | 78      346     78      | 12469   146     129
-------------------------+-------------------------+---------------------
 189     4       1579    | 3579    59      3579    | 178     2       6   
 3       1267    12679   | 479     8       24679   | 147     1457    157
 268     25678   2567    | 1       2456    24567   | 478     9       3   
-------------------------+-------------------------+---------------------
 128     9       12357   | 6       125     2358    | 127     1378    4   
 12468   12368   12346   | 3489    7       23489   | 5       1368    1289
 12468   1235678 1234567 | 34589   12459   234589  | 12679   13678   12789

Puzzle #77 of the top1465.
Code: Select all
 7..|...|4..
 .2.|.7.|.8.
 ..3|..8|..9
 ---+---+---
 ...|5..|3..
 .6.|.2.|.9.
 ..1|..7|..6
 ---+---+---
 ...|3..|9..
 .3.|.4.|.6.
 ..9|..1|..5


 7      1589   568    | 1269   13569  23569  | 4      125    123
 14569  2      456    | 149    7      3459   | 156    8      13 
 1456   145    3      | 1246   156    8      | 12567  1257   9   
----------------------+----------------------+--------------------
 2489   4789   2478   | 5      1689   46     | 3      1247   12478
 358    6      457    | 18     2      34     | 1578   9      1478
 234589 4589   1      | 489    39     7      | 258    245    6   
----------------------+----------------------+--------------------
 12568  1578   25678  | 3      568    25     | 9      1247   12478
 1258   3      2578   | 2789   4      259    | 1278   6      1278
 2468   478    9      | 2678   68     1      | 278    3      5   

Results may vary depending upon your own definition of "basic techniques". For example, Bob Hanson has added 'almost locked sets' to his 3D-Medusa solver ... which now solves these two puzzles without T&E IIRC.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby tarek » Sun Jan 08, 2006 3:36 pm

My solver has no colouring/tabling
& when making simple guesses (requiring single elimination) it solves all puzzles with a unique solution. The only exception was the #77 from the top1465 (mentioned in the post just above) which required deep guessing to eliminate candidates (techniques higher than singles) to establish the contradiction.

I hope that was what you were after bennys.
User avatar
tarek
 
Posts: 3531
Joined: 05 January 2006

Postby ronk » Mon Jan 09, 2006 1:04 am

tarek wrote:My solver has no colouring/tabling
& when making simple guesses (requiring single elimination) it solves all puzzles with a unique solution. The only exception was the #77 from the top1465 (mentioned in the post just above) ...

Assuming your solver tags each elimination with the technique used, would you please post the sequence of eliminations for puzzle #2?

TIA, Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby bennys » Mon Jan 09, 2006 1:14 am

Code: Select all
For some reason I am still not clear.
in an example we must arrive to a step where I cant make any progress
(progresses define as eliminating candidate or find placement)
using a 'guess' and then elementary technics.
for that to happened we need to be in a stage where for ALL guesses we will stuck again. 

The order is not imported because in each stage you can try all cells for all the current candidates for elimination or finding a solution


for #2 R6C3=2 solve the puzzle.

 
 
 
for #7


+-------+-------+-------+
| 7 . . | . . . | 4 . . |
| . 2 . | . 7 . | . 8 . |
| . . 3 | . . 8 | . . 9 |
+-------+-------+-------+
| . . . | 5 . . | 3 . . |
| . 6 . | . 2 . | . 9 . |
| . . 1 | . . 7 | . . 6 |
+-------+-------+-------+
| . . . | 3 . . | 9 . . |
| . 3 . | . 4 . | . 6 . |
| . . 9 | . . 1 | . 3 5 |
+-------+-------+-------+

+----------------------+----------------------+----------------------+
| 7      1589   568    | 1269   13569  23569  | 4      125    123    |
| 14569  2      456    | 149    7      3459   | 156    8      13     |
| 1456   145    3      | 1246   156    8      | 12567  1257   9      |
+----------------------+----------------------+----------------------+
| 2489   4789   2478   | 5      1689   46     | 3      1247   12478  |
| 358    6      457    | 18     2      34     | 1578   9      1478   |
| 234589 4589   1      | 489    39     7      | 258    245    6      |
+----------------------+----------------------+----------------------+
| 12568  1578   25678  | 3      568    25     | 9      1247   12478  |
| 1258   3      2578   | 2789   4      259    | 1278   6      1278   |
| 2468   478    9      | 2678   68     1      | 278    3      5      |
+----------------------+----------------------+----------------------+

R1C2<>5 R1C3<>5 and R5C5<>5


+----------------------+----------------------+----------------------+
| 7      189    68     | 1269   1369   23569  | 4      125    123    |
| 14569  2      456    | 149    7      3459   | 156    8      13     |
| 1456   145    3      | 1246   156    8      | 12567  1257   9      |
+----------------------+----------------------+----------------------+
| 2489   4789   2478   | 5      1689   46     | 3      1247   12478  |
| 358    6      457    | 18     2      34     | 1578   9      1478   |
| 234589 4589   1      | 489    39     7      | 258    245    6      |
+----------------------+----------------------+----------------------+
| 12568  1578   25678  | 3      568    25     | 9      1247   12478  |
| 1258   3      2578   | 2789   4      259    | 1278   6      1278   |
| 2468   478    9      | 2678   68     1      | 278    3      5      |
+----------------------+----------------------+----------------------+



now R6C8=5 solve it
bennys
 
Posts: 156
Joined: 28 September 2005

Postby ronk » Mon Jan 09, 2006 1:57 am

bennys wrote:For some reason I am still not clear.

You apparently didn't see my explanation relative to puzzles #2 and #77 from the top1465. I said they were unsolvable if only naked single and hidden single techniques were used during the guessing stage ... at least until an elimination was found.

I also said that if other techniques *were* used, pairs, triples, locked candidates, etc. ... I believed *every* puzzle could be progressed to a solution.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to General