## Did I do this right?

Advanced methods and approaches for solving Sudoku puzzles

### Did I do this right?

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------+-------+------. . . | . . . | . . .. . . | . . . | . . .. . . | . . . | . . .`

EnderGT

Posts: 69
Joined: 19 February 2008

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

It probably replaces the nishio you were referring to above

tarek

tarek

Posts: 2895
Joined: 05 January 2006

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

(Woh. Simultaneous posts!)

Luke
2015 Supporter

Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

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

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

nice catch
Some do, some teach, the rest look it up.

StrmCkr

Posts: 942
Joined: 05 September 2006

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

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. . . | . . . | * . .. . . | . . . | * . ./ / / | / . / | . # #------+-------+------. . . | . . . | . . ./ / / | / . / | . / /. . . | . . . | . . .------+-------+------. . . | . . . | . . .. . . | . . . | . . .. . . | . . . | . . .`

Pat

Posts: 3700
Joined: 18 July 2005

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

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.

Luke
2015 Supporter

Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

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

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

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

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
udosuk

Posts: 2698
Joined: 17 July 2005

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

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 @ r35F F F | F F F | - F FF 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 FF F F | F F F | F F FF F F | F F F | F F FER @ b2F F F | F F F | - F FF F F | / F / | F F FF 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 FF F F | F F F | F F FF F F | F F F | F F F`

And we can eliminate F @ r3c5 the following way.

Code: Select all
`ER @ b3F 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 FF F F | F F F | F F FF F F | F F F | F F F`

Hope it's clearer to you.
udosuk

Posts: 2698
Joined: 17 July 2005

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