The New Sudoku Players' Forum

by **daj95376** » Tue May 16, 2006 4:21 pm

Clear this as well.

by **gsf** » Tue May 16, 2006 4:41 pm

daj95376 wrote:When I started my solver, I knew there was a long list of techniques ahead for me to implement. I wrote the basics -- Naked/Hidden Singles/Pairs/Triples/Quads and Locked Candidates (1&2). Then I stopped and took a deep breath before implementing X-Wing, Swordfish, and Jellyfish.

At this point, I stopped again to consider the increasingly complex (and often convoluted) techniques that lay ahead.

its good to stop and ponder at this point
so many techniques with so many cute names pop up here that
we need to stand back a bit and think about some unifying properties

by **Pyrrhon** » Wed May 17, 2006 5:56 am

Looking at daj95376's points which increases the difficulty of a sudoku (it seems to be a generalization of the magic points) with brute force could be an interesting approach for those programers which are interested to find a short and human-understandable proof of a solution rather than to install a human-like method to find such a proof. With other words: It could be a method to simplify the deductive proofs of a solution.

Another way to simplify proofs would be simply to check whether we can skip one of the more complicated techniques and use a later one instead getting a stage where the first one is not further necessary (and so having a less number of complicate steps).

By the way statistics about the methods with which we can catch these semi-magic points deductively (after finding them with brute force) could be improve the order of techniques in a sudoku program which is aimed to get fast sudoku solutions and does not use brute force techniques.

Pyrrhon

by **tarek** » Wed May 17, 2006 10:49 am

daj95376 wrote:When I encounter an invalid candidate in a cell with two candidates, then I report the valid candidate as leading to a solution -- instead of the invalid candidate leading to a contradiction.

Hi there daj,

What is the purpose of the above statement ? .......& how do you choose the VALID candidates from the INVALID candidates?

When you report INVALID candidates you automatically use the VALID candidates because they will lead to the solution.

tarek

by **Karlson** » Wed May 17, 2006 1:26 pm

Here is another very tough one for you:
#5:

Code: Select all: .3.8.....1.5.......4...952.....9...28.1..5.7.....1...4...5.724..9.2..8..4........

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

Solve it without guessing and have fun

by **ravel** » Wed May 17, 2006 3:30 pm

This one is not so hard:

Code: Select all: 29 3 2679 | 8 5 246 | 467 16 167 1 2678 5 | 346 23467 2346 | 3467 9 3678 67 4 678 | 1 367 9 | 5 2 3678 ---------------------------------------------------------------------------- 3567 567 4 | 367 9 368 | 1 58 2 8 26 1 | 346 2346 5 | 9 7 36 29 2567 23679 | 367 1 2368 | 36 58 4 ---------------------------------------------------------------------------- 36 1 368 | 5 368 7 | 2 4 9 3567 9 367 | 2 346 1346 | 8 136 1567 4 25678 23678 | 9 368 136 | 67 136 1567

r3c5=7 => r3c1=6 => r7c1=3 => r6c3=3 => r6c7=6 => r2c7=3 => r3c5=3
=> r2c5=7

by **Karlson** » Wed May 17, 2006 3:46 pm

Yea, you are right - I posted the false one
This one is it:
#6:

Code: Select all: ...........16394..8.......94...9...5.6...8.2...7..31.42.......1..94213...........

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

by **daj95376** » Wed May 17, 2006 3:53 pm

Another invalid reply.

by **ravel** » Thu May 18, 2006 2:10 pm

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

This puzzle (again 3 steps for my program) for a long time looks easier than it is. With a swordfish, 2 type4 URs, 2 short chains (r4c3<>8 and r6c8<>9), a longer one, that ended in a 6-cell uniqueness pattern (r4c2<>1) and an xy-chain (r8c2=5 -> r2c1=7) i came here. It looks easy with all the pairs, but i could not finish it without a monster chain (e.g. r1c1<>3). Maybe i missed another uniqueness trick ?

Code: Select all: 357 9 2346 | 8 17 24 | 2567 13 267 57 25 1 | 6 3 9 | 4 58 278 8 234 2346 | 5 17 24 | 267 13 9 ---------------------------------------------------------- 4 23 23 | 1 9 6 | 8 7 5 1 6 5 | 7 4 8 | 9 2 3 9 8 7 | 2 5 3 | 1 6 4 ---------------------------------------------------------- 2 3457 348 | 39 68 57 | 567 49 1 56 57 9 | 4 2 1 | 3 58 678 356 1 348 | 39 68 57 | 2567 49 267

by **Karlson** » Thu May 18, 2006 4:23 pm

there is an empty rectangle of 5s:

Code: Select all: 357* 9 2346 | 8 17 24 | 2567 13 267 57* 25* 1 | 6 3 9 | 4 58* 278 8 234 2346 | 5 17 24 | 267 13 9 ---------------------------------------------------------- 4 23 23 | 1 9 6 | 8 7 5 1 6 5 | 7 4 8 | 9 2 3 9 8 7 | 2 5 3 | 1 6 4 ---------------------------------------------------------- 2 3457 348 | 39 68 57 | 567 49 1 56- 57 9 | 4 2 1 | 3 58* 678 356 1 348 | 39 68 57 | 2567 49 267

then a few dual implication chains and nice loops solve it

by **tarek** » Fri May 19, 2006 6:56 am

daj95376 wrote:My emphasis was on finding cell candidates that produced invalid puzzles if used.

However, to keep my solver from printing out two equivalent statements for a cell with two candidates when one is removed, I only report the assignment of the final cell value. Thus, my solver's output would seem to conflict with the statements I made about finding invalid cell candidates. I added this statement to explain this contradiction.

I'm sorry if it was confusing!

PS: I'm in the process of updating my solver so that it lists the chain associated with an invalid cell candidate. Without validation, my results seem to lack acceptability.

That seems fine, you have to keep in mind that contradiction elimination is considered by most of us as Guessing & therefore should be in the outermost loop in your solver......

having said that, any other technique [although more complex] which does not have contradiction elimination takes preference in our discussions in the advanced techniques, & a better solver or solution would have fewer contradiction eliminations IMO.

tarek

by **ravel** » Fri May 19, 2006 7:34 am

Karlson wrote:there is an empty rectangle of 5s:
then a few dual implication chains and nice loops solve it

Thanks, in fact i had seen the ER, but it did not help much and i forgot to save the candidate list.
Could you please spell out the chains and loops, then i could write down an overall solution.

PS: Looking at it again now, this chain (of "acceptable" length) plus the ER would solve it:
r9c1=5 => r1c1=3 => r1c8=1 => r1c5=7
r9c1=5 => r2c1=7,r2c2=5 => r2c8=8 => r2c9=2 => r1c7=2 (=> r9c9<>2)
r9c1=5 => r9c6=7 => r9c9=6
=> r1c9 is empty

by **Karlson** » Fri May 19, 2006 12:10 pm

After the ER we arrive here:

Code: Select all: 357 9 2346 | 8 17 24 | 2567 13 267 57 25 1 | 6 3 9 | 4 58 278 8 234 2346 | 5 17 24 | 267 13 9 ----------------+----------------+---------------- 4 23 23 | 1 9 6 | 8 7 5 1 6 5 | 7 4 8 | 9 2 3 9 8 7 | 2 5 3 | 1 6 4 ----------------+----------------+---------------- 2 3457 348 | 39 68 57 | 567 49 1 6 57 9 | 4 2 1 | 3 58 78 35 1 348 | 39 68 57 | 2567 49 267

chain 1:
R8C2=5 => R7C2=7 => R7C6=5 (5 in R7)
R8C2=7 => R8C8=5 => R2C8=8 => R1C7=5 (5 in C7)
=> R7C7 <> 5
nice loop:
R1C7=6 => R9C7=5 => R9C9=2 => R1C9=6 => R1C7<>6

Code: Select all: 357 9 2346 | 8 17 24 | 257 13 267 57 25 1 | 6 3 9 | 4 58 278 8 234 2346 | 5 17 24 | 267 13 9 ----------------+----------------+---------------- 4 23 23 | 1 9 6 | 8 7 5 1 6 5 | 7 4 8 | 9 2 3 9 8 7 | 2 5 3 | 1 6 4 ----------------+----------------+---------------- 2 3457 348 | 39 68 57 | 67 49 1 6 57 9 | 4 2 1 | 3 58 78 35 1 348 | 39 68 57 | 2567 49 267

Does anyone find a simple nice loop here because I can only find a long dual implication chain here...

by **tarek** » Fri May 19, 2006 12:26 pm

Code: Select all: *--------------------------------------------------------* |^357 9 2346 | 8 17 24 | 257 13 267 | |^57 *25 1 | 6 3 9 | 4 58 278 | | 8 -234 2346 | 5 17 24 | 267 13 9 | |------------------+------------------+------------------| | 4 *23 23 | 1 9 6 | 8 7 5 | | 1 6 5 | 7 4 8 | 9 2 3 | | 9 8 7 | 2 5 3 | 1 6 4 | |------------------+------------------+------------------| | 2 3457 348 | 39 68 57 | 67 49 1 | | 6 57 9 | 4 2 1 | 3 58 78 | | 35 1 348 | 39 68 57 | 2567 49 267 | *--------------------------------------------------------* Eliminating 3 from r3c2(ALS-XZ A=235 in r4c2, r2c2 B=357 in r2c1, r1c1 x=5 z=3)

Then there is a Type 4 UR

tarek

by **ronk** » Fri May 19, 2006 1:00 pm

You guys are waay out in front with #6. Would someone please tell me how to get past this point?

Code: Select all: 35679 234579 23456 | 8 157 24 | 2567 13567 2367 57 257 1 | 6 3 9 | 4 578 278 8 23457 23456 | 57 157 24 | 2567 13567 9 ---------------------+------------------+------------------ 4 123 238 | 17 9 67 | 68 37 5 135 6 35 | 157 4 8 | 9 2 37 59 589 7 | 2 56 3 | 1 68 4 ---------------------+------------------+------------------ 2 3457 34568 | 39 678 567 | 5678 49 1 567 578 9 | 4 2 1 | 3 5678 678 13567 13457 34568 | 39 678 567 | 25678 49 267

The New Sudoku Players' Forum

Some nice toughies...