The New Sudoku Players' Forum

by Pi » Wed Jan 04, 2006 7:49 pm

There are puzzles that meet that criteria yes, such as Papocom V.Hard

by **bennys** » Wed Jan 04, 2006 7:55 pm

No Way. Papocom V.Hard obviously can be solved by the Papocom V.Hard
techniques.

by **PaulIQ164** » Wed Jan 04, 2006 9:39 pm

Ah, but the Pappocom V.Hards use more tactics than the Pappcom Hards - well, one more tactic - the X-Wing. I would have thought they could be solved using judicious guesswork and Hard tactics though.

by **bennys** » Wed Jan 04, 2006 10:01 pm

If X wing is the only "advance" tactic that is needed it will not create any problem (put the value and get the contradiction to remove the candidate)

by **bennys** » Thu Jan 05, 2006 4:52 pm

Animator to me it looks that all your answer is dubious but it just me.

by Pi » Thu Jan 05, 2006 5:06 pm

the X wing may not create a problem for you but it would for a less experienced player.

A chain or swordfish may be a problem for you though

by **bennys** » Thu Jan 05, 2006 5:26 pm

Pi probably it’s my (bad) English but I feel that you don’t understand my Question.
I am looking for a sudoku in a specific stage including candidates in which
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.

by Pi » Thu Jan 05, 2006 5:47 pm

so you are looking for a puzzle where you will get to a atage where no move can be made

by **bennys** » Thu Jan 05, 2006 5:53 pm

Yes, using the Method described.

by Pi » Thu Jan 05, 2006 6:05 pm

what do you define as "No move can be made"

by **Moschopulus** » Thu Jan 05, 2006 6:15 pm

bennys wrote:Pi probably it’s my (bad) English but I feel that you don’t understand my Question.
I am looking for a sudoku in a specific stage including candidates in which
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.

I'm not sure if I understand. I think you are looking for a 2-constrained puzzle, as defined here:
http://www.setbb.com/phpbb/viewtopic.php?t=248&mforum=sudoku

A magic cell is a cell where, if you make the right guess for this cell, everything else can be solved with your "elementary techniques".

I think you are looking for a puzzle with 2 magic cells, called a 2-constrained puzzle. There are examples at the above link. Here is one.

1....6.8.45..9.1.2........5.....1.....76...2.9.....8..3........5..14.3....2..5..7

No 3-constrained puzzle is known.

by **bennys** » Thu Jan 05, 2006 11:01 pm

I think its close but it’s not the same thing.

Correct me if I am wrong but a magic cell exists for a sudoku if and only if the following algorithm will work.

Pick a cell, pick a value and start applying elementary techniques if you get to solve the puzzle you stop (and you did find a magic cell) if not (you get stuck or get a contradiction) you move to the next candidate or the next cell if you finished checking the candidates for that cell without changing the candidates list.

What I am talking about is similar but if I get a contradiction I remove that candidate from the candidates list and start all over again.

Regarding the example its not what I looking for because

Code: Select all: Using elementary technics we get +----------------------+----------------------+----------------------+ | 1 29 39 | 23457 2357 6 | 479 8 349 | | 4 5 368 | 378 9 378 | 1 367 2 | | 7 289 3689 | 2348 1 348 | 469 3469 5 | +----------------------+----------------------+----------------------+ | 2 346 45 | 345789 3578 1 | 45679 34679 3469 | | 8 134 7 | 6 35 349 | 459 2 1349 | | 9 1346 145 | 23457 2357 347 | 8 13467 1346 | +----------------------+----------------------+----------------------+ | 3 1489 14 | 789 6 789 | 2 5 1489 | | 5 7 89 | 1 4 2 | 3 69 689 | | 6 1489 2 | 389 38 5 | 49 149 7 | +----------------------+----------------------+----------------------+ now placing 7 in r2c8 will create a contradiction so we remove 7 from r2c8 now placing r4c8=6 solve the puzzle

by **gsf** » Fri Jan 06, 2006 6:48 am

bennys wrote:I think its close but it’s not the same thing.

Correct me if I am wrong but a magic cell exists for a sudoku if and only if the following algorithm will work.

Pick a cell, pick a value and start applying elementary techniques if you get to solve the puzzle you stop (and you did find a magic cell) if not (you get stuck or get a contradiction) you move to the next candidate or the next cell if you finished checking the candidates for that cell without changing the candidates list.

sudoku magic cells are equivalent to CSP backdoors
bennys, you might be thinking of "magic cell" as a single entity,
but magic cells, like backdoors, may come in tuples
for a given set of constraints ("elementary techniques" say)
an N-constrained puzzle has minimal backdoor set size N
meaning that there exists N cells, that when assigned the correct
value, trivially solve the puzzle using the constraints *and*
there exists no N-1 tuple of cells that trivially solves the puzzle

you seem to have requested a backdoor size of 2
(a 2-constrained puzzle)
this puzzle has 11 size 2 FN constraint (elementary technique) backdoors (and no size 1)

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

the backdoors are

Code: Select all: [1,1]=1[4,5]=9 [1,5]=5[5,7]=4 [3,3]=9[5,7]=4 [3,3]=9[9,1]=8 [3,6]=1[4,5]=9 [3,7]=5[8,5]=4 [3,9]=6[5,7]=4 [3,9]=6[5,9]=3 [3,9]=6[9,7]=3 [5,7]=4[6,1]=9 [6,1]=9[8,1]=5

and this one has 550

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

by **bennys** » Fri Jan 06, 2006 7:44 am

Its not what I am looking for .look at the example in my previous post where I show that using the method that I am talking about it can be solved
And that is because I allow removing candidates.

by **gsf** » Fri Jan 06, 2006 11:18 am

bennys wrote:Its not what I am looking for .look at the example in my previous post where I show that using the method that I am talking about it can be solved
And that is because I allow removing candidates.

your magic cell algorithm is not correct because it only considers singletons

for some 9x9 sudoku, like the one below, the elementary technique magic cells come in pairs

please illustrate how this puzzle does not meet your criteria:

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