The New Sudoku Players' Forum

[gurth]

G910 - my brightest pearl so far. Angusj's Simple Sudoku can't solve a single cell. nor can I, so far.
But then I don't like solving my own puzzles. Here is G910:

a: 042 009 100 / b: 010 080 030 / c: 500 100 004
d: 600 000 000 / e: 090 005 070 / f: 007 000 008
g: 400 001 006 / h: 030 060 000 / k: 000 700 240

All solutions offered will be awarded Acorns according to my subjective criteria.
Those Acorn awards will be recorded in the Hall of Fame.

[ronk]

Here is G910:

a: 042 009 100 / b: 010 080 030 / c: 500 100 004
d: 600 000 000 / e: 090 005 070 / f: 007 000 008
g: 400 001 006 / h: 030 060 000 / k: 000 700 240

Most on this forum prefer a format they can cut & paste into their favorite solver such as ...

042009100010080030500100004600000000090005070007000008400001006030060000000700240

OR

Code: Select all

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

With most clues on the diagonal within each 3x3 box, that could prove to be a difficult puzzle.

[udosuk]

It's difficult puzzle alright... But still there are backdoor cells...

For example, using Simple Sudoku, r3c2=7 or 8 will lead to contradiction, while r3c2=6 enable you to get to the solution...

If you call your type of puzzles a "pearl", what do you call those ones that have no backdoor cells whatsoever (if there is one such puzzle)?

[gsf]

If you call your type of puzzles a "pearl", what do you call those ones that have no backdoor singles whatsoever (if there is one such puzzle)?

puzzle #5 from ocean's first hardest sudoku post has backdoor size 2
up to (and including) multi-coloring (no als or uniqeness techniques)

Code: Select all

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


i.e., techniques up to multi-coloring will not yield a solution
(only a hidden single at [23]=2, so its (edit: not) a pearl-- I guess)
solve any one cell and techniques up to multi-coloring will still get stuck
solve any of these pairs and the techniques yield a solution
(the left cell and any one in {...} to the right, e.g., [11][57] is a backdoor pair up to multi-coloring):

Code: Select all

[11]4*{[36]8[46]2[56]3[57]2[87]1}
[12]9*{[36]8}
[13]8*{[29]1}
[14]5*{[29]1[46]2[56]3[79]8[95]2}
[15]7*{[36]8[54]6[69]6}
[21]7*{[36]8[87]1}
[24]9*{[69]6}
[26]6*{[99]9}
[27]8*{[44]4[56]3[62]4[64]7[84]8[92]8}
[38]9*{[64]7[69]6[87]1}
[48]1*{[64]7[69]6}
[65]1*{[69]6}


[udosuk]

Thanks gsf for the reference...

As an original it is not a pearl according to gurth I'm afraid (initial hidden single)...

But if you define r2c3=2 as an initial clue then it becomes an asymmetrical pearl... If you define r7c8=2 as well then it turns back a symmetrical pearl (though it might lose the backdoor size of 2)...

Well we could call these "diamonds" since they're much harder to crack than pearls...

[gsf]

As an original it is not a pearl according to gurth I'm afraid (initial hidden single)...

thanks -- that's what I meant to say -- typo in post edited

But if you define r2c3=2 as an initial clue then it becomes an asymmetrical pearl... If you define r7c8=2 as well then it turns back a symmetrical pearl (though it might lose the backdoor size of 2)...

23=2 preserves the size 2 backdoors, 23=2 78=2 leaves just one size 1 backdoor 64=7

[maria45]

Hi gurth,

at the moment I'm too busy to look more closely into your pearl, diamond, whatsoever, but since you used my favorite notation abcdefghk, it seems almost like an invitation...

with kind regards, Maria

[udosuk]

A clarification on terms (hope I haven't made a mistake):

First we have to define a certain set of techniques as our "technique set"... For example, Simple Sudoku employs subsets, locked candidates, x-wing, swordfish, colors, multi-colors & xy-wing... But no larger ALS, Nice Loop, Uniqueness, etc... Call this the SSTS (Simple Sudoku Technique Set)...

Pearls : puzzles which initially the player cannot fill in any cell using SSTS (eliminations could be made, but no cells could be filled in directly)

Diamonds : puzzles which do not have any "backdoor cells" (A backdoor cell is a cell where if you put in the correct value, with or without any logical reason, would lead to the whole puzzle being solved by further moves under SSTS)

These 2 properties are independent to each other...

For "pure logic and no T&E" players, a pearl is probably more alluring because it's a challenge right from the start to spot the advanced technique to allow you to place the first value...

For T&E/brute-force players/programs a diamond should pose as a tougher challenge...

[daj95376]

[Edited] backdoor single appears to be an inappropriate phrase that I coined awhile back. It's led to much confusion in this thread. I apologize profusely for my mistake!!!

[gsf]

Do others agree with udosuk's definition of a backdoor single?

I've been using a more restrictive definition and need to know if I should update it. TIA!!!

backdoors (or magic cells) must always be qualified by the techniques in scope like udosuk did
the confusion here might be the choice of backdoor single
where single means one cell vs. the singles technique
when I'm thinking and typing at the same time I try to distingush the two by saying
backdoor of size 1 (or 2, no 3 found for any 9x9 sudoku)
also implicit in a backdoor assertion is that there exists no backdoor of smaller size
e.g., the puzzle in this thread has backdoor size 2 upto and including multi-coloring
(and doesn't have a backdoor of size 1 upto and including multi-coloring)

[daj95376]

I'm sorry gsf, but your explanation is as clear as mud. Searching with Google for backdoor single and magic cell didn't produce any better definitions.

What I've been using as the definition of a backdoor single is: A cell candidate that leads to a solution by creating a cascade of singles -- naked or hidden.

In udosuk's definition, many more techniques are acceptable in obtaining a solution.

[gsf]

I'm sorry gsf, but your explanation is as clear as mud. Searching with Google for backdoor single and magic cell didn't produce any better definitions.

sudoku magic cell or backdoor must be qualified by the constraints in scope

from my solver --man or sudoku(1)

A constrained puzzle is solvable by constraint propagation alone (pure logic / no guessing).

A backdoor or magic cell set is the smallest set of moves that lead to a
constrained solution. A puzzle with backdoor size N (magic cell set size N)
for constraint set C is C-N-constrained. A conjecture is that all puzzles
are FN-0, FN-1 or FN-2-constrained.

where move is a cell placement and FN are the naked and hidden single constraints

[udosuk]

Sorry guys... I've displayed my ignorance by assuming a backdoor single was the same as a single magic cell... I've edited all my post to use the term "backdoor cell" instead...

So, does gurth's G910 contain any backdoor single? I know it has at least 1 backdoor cell under SSTS (r3c2)...

Also, do we have a special term for a backdoor cell where inputting any incorrect candidate will lead to contradiction under a certain technique set?

For example, in G910, r3c2 can only be 6 or 7 or 8. We have a 3-way branch here: entering 7 or 8 would lead to contradiction while entering 6 would lead to the correct solution (under SSTS of course)...

Compared to the following modified puzzle from Ocean:

Code: Select all

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

Here, r6c4=3|4|5|6|7. Entering 7 will lead to the final solution. Entering 3,5,6 will lead to contradiction. But entering 4 SSTS would be stuck after a few moves...

[gsf]

Also, do we have a special term for a backdoor cell where inputting any incorrect candidate will lead to contradiction under a certain technique set?

the constraint satisfaction literature only uses the term backdoor for valid solution values

[gurth]

Sorry, guys, I should have told you to read my "Aesthetics of Sudoku" which I posted simultaneously with this one, thinking you would all read it. A serious miscalculation on my part, obviously! There you will find a proper definition of what I mean by pearl. As it is, you have got hold of the wrong end of the stick.

Those who have read it should read it again : I have just added another posting on the subject.

Specifically:

Ronk,
thanks for the tip re format.

udosuk,
if your statement re r3c2 being 7,8 or 6 is true, then I feel inclined to state that you have already solved the problem. MY problem is this : how much credit do you deserve for that solution? If your program pointed it out to you, then I would say you get no marks for the solution, but plenty of marks for all the interesting points re magic and backdoor cells that you have raised.

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 like your definitions for "pearl" and "diamond", but please bear in mind (as I explained in my "Aesthetics...") that a pearl MUST have no redundant clues, so you can't convert any puzzle into a pearl simply by adding a clue or two. That would cheapen the value of pearls too much!

Also, pearls can be small, i.e. allow "advanced" methods for solving the first cell, as long as these methods are more "advanced" than subsets and locked candidates.

Another point I would like to make here is that it is not all that important that a puzzle be a pearl anyway. It's just an aesthetic gloss. Far more important is the difficulty of the puzzle as a whole. What are you going to call an ultra-difficult puzzle, if you have used up "diamond" already? Is not a diamond the ultimate?

The point you ask : re a special term for a backdoor cell where inputting any incorrect candidate will lead to contradiction under a certain technique set, is I think something worth thinking about. Because an ordinary backdoor cell may not acceptably be used to solve a puzzle (as ravel drummed into me!), whereas there can be no objection to using a cell such as you describe, if the contradictions are also proved. I suggest a "ruby cell". Then we can say that G910 has a ruby cell.

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.

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, ".