Vidar's Monster #3

Advanced methods and approaches for solving Sudoku puzzles

Vidar's Monster #3

Postby vidarino » Sat Feb 18, 2006 9:09 am

This went missing after the hacking incident, so I'm taking the liberty of reposting it.

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


As far as I can gather, it should be on par with the two from top1465 that were posted in the Monster #2 thread, if not a notch harder. Those two, as well as Monster #2, had the weakness that they had magic cells. This one does not.:) (It has several magic pairs, though.)

Good luck.:)

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Re: Vidar's Monster #3

Postby gsf » Sat Feb 18, 2006 11:19 am

vidarino wrote:As far as I can gather, it should be on par with the two from top1465 that were posted in the Monster #2 thread, if not a notch harder. Those two, as well as Monster #2, had the weakness that they had magic cells. This one does not.:) (It has several magic pairs, though.)

this one has 2 singleton backdoors (magic cells)
[2,4]=2 doesn't require coloring
[2,9]=3 does require coloring
9x9 puzzles with no singleton backdoors are rare
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: Vidar's Monster #3

Postby vidarino » Sat Feb 18, 2006 12:18 pm

gsf wrote:this one has 2 singleton backdoors (magic cells)
[2,4]=2 doesn't require coloring
[2,9]=3 does require coloring
9x9 puzzles with no singleton backdoors are rare


Ah, yes, sorry, I should have been more specific. It has no singleton backdoors that solves the rest of the puzzle using only singles and locked candidates. If I enable naked sets, it find one; R2C4.

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Re: Vidar's Monster #3

Postby ronk » Sat Feb 18, 2006 1:02 pm

vidarino wrote:It has no singleton backdoors that solves the rest of the puzzle using only singles and locked candidates. If I enable naked sets, it finds one ...

With that configuration, what's the largest naked set that might be found without finding a hidden set of any size?

TIA, Ron

BTW where is monster #1?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby tarek » Sat Feb 18, 2006 1:05 pm

hi Vidar,

My solver didn't like your puzzle (tough workout for a Saturday morning).

It is a toughie, it beats my solver 9 times.

Thisis the summary:

Difficulty Score: 722989 (Diabolical)
Non single moves: 28
Non Simple xy Chains: 0
Guesses: 9 (all simple) ---- that would be less if deep guessing is used

The interesting stuff about this to me are:

Double X wing in the same rows to start
No simple chains to use !
No ALS XY uncovered by my solver! (I need to check that)
It fell to uniqueness at the end !!!
Code: Select all
*--------------------------------------------------------*
| 5     26    139  | 8     13    27   | 4     67    139  |
| 26    8     13   | 24    9     247  | 67    5     13   |
| 4     19    7    | 5     13    6    | 139   8     2    |
|------------------+------------------+------------------|
| 8     15    4    | 29    27    3    | 15    279   6    |
| 27    3     156  | 2469  2467  58   | 129   2479  1589 |
| 9     27    56   | 1     2467  58   | 237   234   358  |
|------------------+------------------+------------------|
| 1     69    59   | 7     246   24   | 8     2369  359  |
| 36    4     8    | 236   5     9    | 26    1     7    |
| 367   5679  2    | 36    8     1    | 569   69    4    |
*--------------------------------------------------------*
Candidates 139 form a Quantum cell as Candidates 58 in r5c6,r6c6,r5c9 & r6c9 form a unique quadrangle which leads to:
r7c9 Must only have 5 as valid Candidates (139 is a Naked Triple in Column 9)


Tarek
User avatar
tarek
 
Posts: 2611
Joined: 05 January 2006

Re: Vidar's Monster #3

Postby vidarino » Sat Feb 18, 2006 1:30 pm

ronk wrote:With that configuration, what's the largest naked set that might be found without finding a hidden set of any size?


Any naked set will have a corresponding hidden set, AFAIK. But for this particular magic cell to "work", a naked pair is all that's needed.

BTW where is monster #1?


It was never labelled as such, just posted under the subject "A tough one". But here it is again:

Code: Select all
Vidar's Monster #1
+-------+-------+-------+
| . . 5 | 8 3 . | . . . |
| . 1 . | . . . | . 9 8 |
| . . 8 | 9 . . | . 4 . |
+-------+-------+-------+
| . . 9 | . 8 . | 6 . . |
| 7 . . | . . 4 | . . . |
| . 8 . | 1 . . | . 7 5 |
+-------+-------+-------+
| 5 . . | . . . | 2 . . |
| . . 3 | . 7 . | . . . |
| . . . | 6 2 . | . 5 1 |
+-------+-------+-------+


Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Re: Vidar's Monster #3

Postby ronk » Sat Feb 18, 2006 2:26 pm

vidarino wrote:
ronk wrote:With that configuration, what's the largest naked set that might be found without finding a hidden set of any size?

Any naked set will have a corresponding hidden set, AFAIK. But for this particular magic cell to "work", a naked pair is all that's needed.

The second backdoor (r2c9=3) of monster #3 requires only a hidden pair and singles to solve. So I was subtly suggesting that a hidden pair is not much more difficult to find (by a human solver) than the naked pair.

Indeed, I've seen posts implying some programmed solvers pass parameter N to their subset functions, meaning naked and hidden pairs are found at the "same time". Ditto for triples and quads too, I guess.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Vidar's Monster #3

Postby vidarino » Sat Feb 18, 2006 2:38 pm

ronk wrote:The second backdoor (r2c9=3) of monster #3 requires only a hidden pair and singles to solve. So I was subtly suggesting that a hidden pair is not much more difficult to find (by a human solver) than the naked pair.


Ah, OK. My solver has two different functions for naked and hidden sets, and I just enabled the naked set functions for the magic cell finder, since (IMHO) when looking at pencilmarks, hidden sets (of any size, but particularly triples and up) are generally harder to spot than the naked ones.

Speaking of which, is there a "rule" that decides when a magic cell is magic? Singles and locked candidates are fine, but which other strategies are "allowed"? If I enable the whole spectrum, there wouldn't be anything particularly magic about it.:)

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Re: Vidar's Monster #3

Postby gsf » Sat Feb 18, 2006 5:34 pm

vidarino wrote:Speaking of which, is there a "rule" that decides when a magic cell is magic? Singles and locked candidates are fine, but which other strategies are "allowed"? If I enable the whole spectrum, there wouldn't be anything particularly magic about it.:)

backdoor or magic cell should always be qualified by the techniques applied
something like "n backdooors of size b up to coloring" or
"n methods-applied-constraint backdooor (pair(s))"
since most 9x9 are constrained or only have singleton backdoors
"singelton" or "of size 1" can be omitted
e.g., (using the single letter constraint method names from the original magic cell post)
http://www.setbb.com/sudoku/viewtopic.php?p=1854&mforum=sudoku#1854
monster #3 has 1 FNBT-constraint backdoor [2,4]=2
monster #3 has 123 FN-constraint backdoor pairs

background: I learned of the constraint satisfaction term backdoor
after the magic cell post and have since used backdoor
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: Vidar's Monster #3

Postby ronk » Sat Feb 18, 2006 5:46 pm

gsf wrote:monster #3 has 1 FNBT-constraint backdoor [2,4]=2
monster #3 has 123 FN-constraint backdoor pairs

Is there an 'official' definition for 'F', 'N', 'B', 'T', etc. somewhere?

And if so, if there some easy way to commit their meanings to memory?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Vidar's Monster #3

Postby gsf » Sat Feb 18, 2006 6:26 pm

ronk wrote:
gsf wrote:monster #3 has 1 FNBT-constraint backdoor [2,4]=2
monster #3 has 123 FN-constraint backdoor pairs

Is there an official definition for 'F', 'N', 'B', 'T', etc. somewhere?

And if so, if there some easy way to commit their meanings to memory?

these are method abbreviations from my command line solver
they can be enabled/disabled/listed by command line options
(-qFN => only use FN, -QX => don't use X, -f%q => list methods applied)
the --man option produces (among other things):
Code: Select all
The constraints are:
    F  Forced cell: only one value possible.
    N  Only cell: only one value in row/col/box.
    B  Box claim: only value in row/col within a box.
    T  Tuple: N exact or hidden N-tuples in row/col/box.
    X  Cycle: one or more weak or pair (Y) edges. Requires B.
    W  Row/col claim: classic N-row/col x-wing swordfish.
    Z  Experimental.
    G  Guess (pseudo constraint): guess with backtrack search (bifurcation.)

there's nothing official or consensus about these other than that's what I programmed
this is also the order that the methods are applied
when a method produces a change the solver goes back to F

F is a naked single, N is a hidden single, but S was taken for "solution" in the -v method trace
N comes from counting (numerating) occurrences for one candidate value in a row/col/box
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: Vidar's Monster #3

Postby ronk » Sat Feb 18, 2006 7:27 pm

gsf wrote:these are method abbreviations from my command line solver they can be enabled/disabled/listed by command line options
(-qFN => only use FN, -QX => don't use X, -f%q => list methods applied)

Since there is apparently no way to disable guessing ( - QG ), is there some other way to determine how far the solver would get without guessing?

In some of your posts, you've used the phrase "up to coloring". Does that mean x-cycles are disabled ( -QX )?

When using the backdoor listing option ( -f%#am ), is there a way to get the 'fill' values too?

TIA, Ron

P.S. I'm assuming "Box Claim" means either of:
  1. Candidates in a row/col are limited to one box, or
  2. Candidates in a box are limited to one row/col
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Vidar's Monster #3

Postby gsf » Sat Feb 18, 2006 9:08 pm

ronk wrote:
gsf wrote:these are method abbreviations from my command line solver they can be enabled/disabled/listed by command line options
(-qFN => only use FN, -QX => don't use X, -f%q => list methods applied)

Since there is apparently no way to disable guessing ( - QG ), is there some other way to determine how far the solver would get without guessing?

-e lists the puzzle after all constraints have been exhausted (before G)
so this will list the programmer's forum pencimark (hints) grid just before G
Code: Select all
sudoku -e -f%#ph

ronk wrote:In some of your posts, you've used the phrase "up to coloring". Does that mean x-cycles are disabled ( -QX )?

not very precise/accurate since my solver does not do explicit coloring
I believe the X method at least covers simple coloring, so I should have said
"up to and including simple coloring" or "FNBTXW"
ronk wrote:When using the backdoor listing option ( -f%#am ), is there a way to get the 'fill' values too?

this slipped --man: %#Am lists the backdoor cells with values, so
-f%q%,%#aM%,%#Am will list the methods applied, the number of backdoors, and the backdoor cells with values
ronk wrote:P.S. I'm assuming "Box Claim" means either of:
  1. Candidates in a row/col are limited to one box, or
  2. Candidates in a box are limited to one row/col

yes

thanks
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby vidarino » Mon Feb 20, 2006 8:48 am

I'm just going to give this one a bump back on track... Any other takers on solving it, except tarek (thanks!)?:)

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby ronk » Mon Feb 20, 2006 1:08 pm

vidarino wrote:I'm just going to give this one a bump back on track... Any other takers on solving it, except tarek (thanks!)?:)

Sorry I got off-topic there asking gsf about his solver. Actually thought about starting a thread, but figured that would be a bit presumptuous.

[edit: Sorry again, as I posted a puzzle solution to the wrong thread. It belonged here.]

Ron
Last edited by ronk on Mon Feb 20, 2006 9:58 am, edited 3 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Next

Return to Advanced solving techniques