G910 : A Pearl

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

Re: G910 : A Pearl

Postby udosuk » Thu Sep 14, 2006 9:09 am

Gurth, thanks for your explaination on pearls. I won't claim any marks regarding solving the puzzle because I'm never the same class as someone like Maria or Carcul who write great walkthroughs on diabolical puzzles...

gurth wrote:But if you did some work of your own to arrive at your testing of that specific cell, then it is another matter. That is why I have said (on another thread in Advanced Techniques) that it is of interest to know HOW a solution is reached, not just to be given a solution.

I just meant to state my observation (with the aid of a program) that your puzzle does contain a backdoor cell (or Ruby cell as nicely coined by you) that makes it susceptible to T&E solvers... But any pure logical solver vying for elegant solutions will find your pearl a delightful challenge to work on, I'm sure...:)

gurth wrote:While you are talking about "T&E/brute-force players/programs", I would like to know, what about "programs players"? What I mean is, how far is the assistance of programs legitimate? Programs can now solve any puzzle. Does that mean that a player can just submit his program solution as his solution? What would be the point? It really seems to me that there is not much point in people submitting solutions any more. Does that spell the death of Sudoku? Please, folk, I need reassurance on this one, if you can find any for me.

I'd never be concerned about the "death of sudoku", and won't hesitate to employ a program to help me solve them/find the answer... Because I'm interested more on killer sudoku puzzles, where the possibilities are endless and no machine/programs could tackle the truly difficult ones (what we call "Ruudiculous" in our community)...

gurth wrote:What are you going to call an ultra-difficult puzzle, if you have used up "diamond" already? Is not a diamond the ultimate?

I don't know... Is diamond the ultimately most precious stone in the universe? Anyway I'm sure the "diamond" puzzles I specify must be pretty close to the top of the pack here... Most of them should have a 9+ rating by Sudoku Explainer...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby JPF » Thu Sep 14, 2006 10:59 pm

gurth wrote:Here is G910:
Code: Select all
 . 4 2 | . . 9 | 1 . .
 . 1 . | . 8 . | . 3 .
 5 . . | 1 . . | . . 4
-------+-------+-------
 6 . . | . . . | . . .
 . 9 . | . . 5 | . 7 .
 . . 7 | . . . | . . 8
-------+-------+-------
 4 . . | . . 1 | . . 6
 . 3 . | . 6 . | . . .
 . . . | 7 . . | 2 4 .



Some observations on your puzzle.

Rating by Sudoku Explainer (SE) =8.9
Number of eliminated candidates by Simple Sudoku (SS) ->13

If you change r4c1=1 :
SE =9.0
SS -> 10

If you change r3c4=6, you get a very easy "singles".

You can also make r2c2=7 or r5c8=1 or r7c1=8 and get valid puzzles with various levels of difficulty.

I called the puzzles in which we can't change only one digit "untouchable".
They are rather uncommon.
For me, it is an important concept as it shows the "solidity" (consistency) of a puzzle.

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby gsf » Fri Sep 15, 2006 2:30 am

JPF wrote:I called the puzzles in which we can't change only one digit "untouchable".

interesting concept
help me parse the definition though
an untouchable puzzle allows how many cells to change?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby JPF » Fri Sep 15, 2006 6:44 am

The concept was given here :

P is a puzzle with the given cells (C1,...,Cn); Ci=ai
[The cell Ci has the digit ai]

For 95% of the puzzles : by changing only 1 digit in a cell Ck (Ck=bk ; bk#ak) we get a new valid puzzle.

If we need to change more than 1 digit to get a new valid puzzle, the puzzle is "untouchable".

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


JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

G910 : A Pearl

Postby gurth » Fri Sep 15, 2006 8:24 am

udosuk,

regarding "ruby" cells, (" re a special term for a backdoor cell where inputting any incorrect candidate will lead to contradiction under a certain technique set"), referring to the specific case of 678c2 (G910) where 7c2 leads to a contradiction, and so does 8c2, we can go a step further with this concept!

You don't need to test both 7c2 and 8c2 separately. Just remove the 6 from c2! That will lead to a contradiction under SSTS, so you have proved both candidates 7c2 and 8c2 false in one hit! (If even one of them had been true, you couldn't have reached a contradiction).

I now wish to reserve the term ruby for a case like this : where more than 2 possibilities (in the case of cell c2 in G910 there are three) may be resolved by simply removing one of them, and then proving that a contradiction will ensue, using only a limited set of techniques. The puzzle must also be solvable from that point on, under the same set of techniques. The value of the ruby increases with the SIMPLICITY of this set of techniques, and also with the number of possibilities for the cell (or other unit, see below), which should be at least 3.

For instance, if a cell contained 7 candidates, and the omission of one of them led to a contradiction under SSTS, that would be an enormous ruby, immediately proving the truth of the missing candidate, as well as maintaining uniqueness. Of course the puzzle would still have to be solvable from that point on by SSTS alone, or whatever other set of techniques you specify.

To go further, I see no reason why this concept should be limited to the case of n candidates in a cell. Why shouldn't it apply equally to n candidates in a row, column or box ? For instance, you might have just four 6s in a row, where removing one of them leads to a contradiction, proving the removed 6 to be true, and if placing that leads to a solution under the defined technique set, then why not call that a ruby too?

So you will possibly have rubies in cells, rows, columns or boxes.

Just seen your full reply to my last post. Thanks a lot! I must look into Killer.


JPF, That's a very interesting concept, re the Untouchable, it will definitely give me food for thought.
gurth
 
Posts: 358
Joined: 11 February 2006
Location: Cape Town, South Africa

Re: G910 : A Pearl

Postby maria45 » Fri Sep 15, 2006 8:55 am

Hi gurth,
gurth wrote:Maria, it might interest you to know that on my "home" forum, by which I mean simply the forum on which I have posted most, I have already embraced your k9 notation on the grounds of its superior readability amongst other things. I learnt this from perusing your solution to Ocean's puzzle. But I've gone further than you. Where you write "e4=3, e9!=3, ef8=12, " , I write, even more briefly, " 3e4, -3e9, 12ef8, ".
that's nice. I will think about using your notation, although it could get a bit too cryptic. But, as we are talking about the "upper league" of sudoku solving, a nice short notation should pose no real obstacle. In chess, the ultimately short notation for a pawn capturing another pawn is "dc:" instead of "dxc5" or "d4xc5".

"untouchables": I encountered some of them. When I have a bit more time, I will post them.

with kind regards, Maria
maria45
 
Posts: 54
Joined: 23 October 2005

Postby gsf » Fri Sep 15, 2006 12:02 pm

JPF wrote:The concept was given here :

P is a puzzle with the given cells (C1,...,Cn); Ci=ai
[The cell Ci has the digit ai]

For 95% of the puzzles : by changing only 1 digit in a cell Ck (Ck=bk ; bk#ak) we get a new valid puzzle.

thanks for the pointer
what is the 95% relative to?
also, to be untouchable does the property have to hold for only one clue cell or all clue cells?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Red Ed » Fri Sep 15, 2006 1:32 pm

"Untouchables" might be rare in the grand scheme of things, but there are lots of examples amongst Gordon's list of 17-clue puzzles. (It seems obvious that low-clue puzzles should be more likely to be untouchable.)
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby udosuk » Fri Sep 15, 2006 1:49 pm

Gurth, your ruby concept sounds really great!:)

Remember we can test for all backdoors cells/pairs with the puzzle and the unique solution... Now we could test them for all ruby cell/set of cells too!

Just do a "propositional elimination", and test for contradiction... If you get one you can fix that cell... Which could be a really efficient way to solve a puzzle by brute force!

Now to see if gsf or other programming gurus would implement this "technique" in their solver...:idea:

And we could check if there is any "ruby-free" puzzle too!
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby gurth » Sat Sep 16, 2006 11:02 am

Maria,

regarding my notation, I have just posted a solution of Ruud's #2/50000 in the Advanced Solving Techniques section, where you will be able to see what the notation looks like in print. Check it for readability and comprehensibility.

A full description of my notation appears at http://www.sudoku.org.uk/discus/messages/29/2488.html?1158050577
gurth
 
Posts: 358
Joined: 11 February 2006
Location: Cape Town, South Africa

Postby tarek » Sun Sep 17, 2006 10:12 am

With the PEARL, DIAMOND terms........

it seems that it is the 1st move that counts.......I have several examples of these pearls or diamonds where SSTS fails to find the desired first move but after that 1st advanced (step/backdoor) it becomess SSTSiable:D .

I guess that if all backdoors/steps were superior to SSTS & the final tail is SSTSiable, then that would be a more demanding puzzle........

I'm not sure if ravel has been using the number of non SSTSiable backdoors to describe the difficulty of a puzzle or not, but the level of that 1st step seems to be the factor here. The biggest 1st hurdle....

The ultimate would be a 1st step theat leaves my solver requiring a complex guess (Contradiction elimination superior to singles) followed by similar or simpler contradiction eliminations leaving only the shortest SSTSiable tail.............

As the SE is a common reference.....then a general rating + a 1st move rating can be used to define these pearls , diamonds.....


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

Previous

Return to General