Did I do this right?

Advanced methods and approaches for solving Sudoku puzzles

Did I do this right?

Postby EnderGT » Wed Mar 11, 2009 4:27 am

So, I was working an extreme puzzle today, one that the solver told me I would need to use 2 nice loops and 1 nishio process (which in my mind is nothing more than a guess, but that's another story)... and I solved it without any of these. I'm wondering, however, if one of my reductions was actually correct (I know it gave the correct answer, but was that just luck?)

The pattern is a winged fish, and it looked (in the puzzle I was working) like this (F denotes the fish pattern, W is the wing, A is the removal, little x's are other candidate positions unrelated to the pattern).

Code: Select all
. . . | x x . | A . .
. . . | . . . | . . .
. . . | . F . | F . W
------+-------+------
x . . | x x . | . . x
. . . | . F . | F . .
x . . | x x . | x . x
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .


Was this a valid elimination?
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby tarek » Wed Mar 11, 2009 4:35 am

It looks like a finned x-wing ....

It probably replaces the nishio you were referring to above

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

Postby Luke » Wed Mar 11, 2009 4:36 am

You have found a nice finned X-wing. I'm surprized the solvers didn't catch it, though.

(Woh. Simultaneous posts!)
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby EnderGT » Wed Mar 11, 2009 5:29 am

Luke451 wrote:You have found a nice finned X-wing. I'm surprized the solvers didn't catch it, though.

(Woh. Simultaneous posts!)


Yeah, the site I get my puzzles from, and its built-in solver, never seems to find those. Maybe the author just doesn't know about them? Even though he's implemented nice loops, forcing loops, nishio, etc.

Oh well, nice to get confirmation that I did it right:)
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby StrmCkr » Wed Mar 11, 2009 9:14 am

every solver is strickly limited to what is programed in it.

:)

nice catch
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 667
Joined: 05 September 2006

Postby PIsaacson » Wed Mar 11, 2009 2:06 pm

EnderGT,

Could you please post the PM at the point of interest? If the candidates are all present, then I believe the bi-local pair r5c57 forces r3c5 to always be "false" as well as r1c7, and both can be eliminated. I'd like to confirm that against the actual puzzle. But then that's coloring or X-cycles instead of fishing...

Thanks,
Paul
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby Pat » Wed Mar 11, 2009 7:28 pm

PIsaacson wrote:If the candidates are all present,
then I believe the bi-local pair r5c57 forces r3c5 to always be "false" as well as r1c7,
and both can be eliminated.

yes, if the posted diagram shows all possible cells for this digit, then r3c5 can also be excluded.

    for the finned X-wing, though,
    this is all the information needed --
    Code: Select all
    / -- the "hidden pattern"
      -- the digit is already known to be impossible in this cell

    # -- fin-cell -- should've been "/" for an (unfinned) X-wing

    * -- resulting exclusion



    . . . | . . . | * . .
    . . . | . . . | * . .
    / / / | / . / | . # #
    ------+-------+------
    . . . | . . . | . . .
    / / / | / . / | . / /
    . . . | . . . | . . .
    ------+-------+------
    . . . | . . . | . . .
    . . . | . . . | . . .
    . . . | . . . | . . .

User avatar
Pat
 
Posts: 3448
Joined: 18 July 2005

Postby EnderGT » Thu Mar 12, 2009 6:34 am

PIsaacson wrote:EnderGT,

Could you please post the PM at the point of interest? If the candidates are all present, then I believe the bi-local pair r5c57 forces r3c5 to always be "false" as well as r1c7, and both can be eliminated. I'd like to confirm that against the actual puzzle. But then that's coloring or X-cycles instead of fishing...

Thanks,
Paul


Actually, I can't, sorry. It's a daily puzzle site, and I don't have access to previous puzzles. I assure you, however, that all possible cells for this candidate are marked.

Could you explain why r3c5 is forced to be false? It becomes false after applying the finned X-wing, but you're suggesting that the X-wing isn't necessary to force it to be false?
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby Luke » Thu Mar 12, 2009 11:03 am

Code: Select all
. . . | x x . | A . .
. . . | . . . | . . .
. . . | . F . | F . W
------+-------+------
x . . | x x . | . . x
. . . | . F . | F . .
x . . | x x . | x . x
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .

If r5c7 contains F the only remaining possibilities for your digit in box 2 will be in row 1.
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby PIsaacson » Thu Mar 12, 2009 12:59 pm

Code: Select all
. . . | x x . | A . .    . . . | + - . | - . .    . . . | x x . | - . .
. . . | . . . | . . .    . . . | . . . | . . .    . . . | . . . | . . .
. . . | . F . | F . W    . . . | . - . | x . x    . . . | . - . | - . +
------+-------+------    ------+-------+------    ------+-------+------
x . . | x x . | . . x    x . . | - - . | . . x    x . . | x x . | . . -
. . . | . F . | F . .    . . . | . + . | - . .    . . . | . - . | + . .
x . . | x x . | x . x    x . . | - - . | x . x    x . . | x x . | - . -
------+-------+------    ------+-------+------    ------+-------+------
. . . | . . . | . . .    . . . | . . . | . . .    . . . | . . . | . . .
. . . | . . . | . . .    . . . | . . . | . . .    . . . | . . . | . . .
. . . | . . . | . . .    . . . | . . . | . . .    . . . | . . . | . . .


Using X-coloring, apply parity to conjugate pair r5c57. Both r1c7 and r3c5 remain parity '-' regardless of which conjugate is true, so they can be eliminated.

I use this technique for manual solving because it's simple. You already know the propagation rules: Set something positive and all the peers become negative, any single remaining in a row/col/box becomes positive etc. And, you can easily view the two common outcomes - any candidate that is always negative can be eliminated and any candidate that is always positive can be assigned. A contradiction occurs when a row/col/box is colored entirely in '-'s or a row/col/box contains two or more '+'s. In that case, the starting candidate can be eliminated.

Technically, this isn't pure X-coloring, but it's close enough in spirit and pretty mechanical to execute using two copies of Simple Sudoku for tracking the 2 coloring passes.
Last edited by PIsaacson on Thu Mar 12, 2009 8:40 pm, edited 1 time in total.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby EnderGT » Thu Mar 12, 2009 5:38 pm

PIsaacson wrote:Using X-coloring, apply parity to conjugate pair r3c57. Both r1c7 and r3c5 remain parity '-' regardless of which conjugate is true, so they can be eliminated.


Interesting. I think I've used a technique similar to this on harder puzzles without knowing it had a name.
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby udosuk » Fri Mar 13, 2009 2:31 pm

PIsaacson wrote:If the candidates are all present, then I believe the bi-local pair r5c57 forces r3c5 to always be "false" as well as r1c7, and both can be eliminated.

Paul, your elimination @ r3c5 is based on another technique, which we call "Empty Rectangle (ER)".:idea:

http://www.sudopedia.org/wiki/Empty_Rectangle

Code: Select all
. . . | x x . | F / /
. . . | . . . | . / /
. . . | . - . | F . F
------+-------+------
x . . | x x . | . . x
. . . | . F . | F . .
x . . | x x . | x . x
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .

Empty Rectangle: no F @ r12c89 (/)
Strong Link of F @ r5c57
=> r3c5 (-) can't be F:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby PIsaacson » Fri Mar 13, 2009 3:22 pm

Yes! And the ER in box 2 accounts for the elimination in r1c7. It would be interesting to obtain statistics on the relative solving power of all the various single digit solving techniques. I recall seeing something like that posted before, somewhere... If I find the time, I'll try running some benchmarks using hobiwan's HoDoKu since it has a very comprehensive list of methods.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby udosuk » Sat Mar 14, 2009 1:14 pm

PIsaacson wrote:Yes! And the ER in box 2 accounts for the elimination in r1c7.

That's true but for the purpose of the discussion here it's making use of a different set of cells (r1c456+r23c5+r5c57 vs r3c579+r5c57) to make the same elimination, and I think you shouldn't mix them up.

To summarise, using the same strong link r5c57, we can eliminate digit F from r1c7 the following 2 ways:

Code: Select all
Grouped Turbot Fish/Finned X-Wing @ r35
F F F | F F F | - F F
F F F | F F F | F F F
/ / / | / F / | F F F
------+-------+------
F F F | F F F | F F F
/ / / | / F / | F / /
F F F | F F F | F F F
------+-------+------
F F F | F F F | F F F
F F F | F F F | F F F
F F F | F F F | F F F

ER @ b2
F F F | F F F | - F F
F F F | / F / | F F F
F F F | / F / | F F F
------+-------+------
F F F | F F F | F F F
/ / / | / F / | F / /
F F F | F F F | F F F
------+-------+------
F F F | F F F | F F F
F F F | F F F | F F F
F F F | F F F | F F F

And we can eliminate F @ r3c5 the following way.

Code: Select all
ER @ b3
F F F | F F F | F / /
F F F | F F F | F / /
F F F | F - F | F F F
------+-------+------
F F F | F F F | F F F
/ / / | / F / | F / /
F F F | F F F | F F F
------+-------+------
F F F | F F F | F F F
F F F | F F F | F F F
F F F | F F F | F F F

Hope it's clearer to you.:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby PIsaacson » Sat Mar 14, 2009 1:54 pm

udosuk wrote:That's true but for the purpose of the discussion here it's making use of a different set of cells

I think you miss my point. I was asking for the full PM to confirm the exact conformation of the candidate in question at positions {x,A,F,W} as given in the example. Even ER depends upon the absence of x in box 3, which is what I assumed the '.'s represent.

Various single digit methods, such as ER, Skyscraper, 2-String Kite, Turbot Fish, X-cycles, simple coloring, multiple fish patterns and POM can all be used to analyze the example position. I don't disagree with that and I fully understand how to produce the 2 eliminations that I found, using X-coloring with all the stated candidates.

I was merely questioning whether or not all the possible eliminations have been located, again assuming that all the candidates are represented in the example. I would like to submit the PM to templates to see if there is anything else, but my solver can't accept such single digit exemplar positions and I can't perform POM analysis accurately by hand.

Unfortunately, the full puzzle seems to no longer be available, so the question is moot. Meanwhile, I've been running benchmarks to compare the various single digit methods. I'll open a thread in the programming forum when I have all the data.

See you there if you're interested in continuing a single digit analysis discussion.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Next

Return to Advanced solving techniques