superior plus puzzles

Everything about Sudoku that doesn't fit in one of the other sections

Postby gsf » Tue Aug 22, 2006 6:10 pm

ab wrote:your list shows the techniques that are in the puzzles but they're not all necessarily required. For instance the last puzzle solves with one quad only and the third last puzzle only requires the pairs and one of the swordfish.

this reminds me of the "what is a step" exchanges for the inferior thread
it took a while to reach consensus

my solver can select and order the techniques applied and apply the techniques when hit
or batch them by group -- there is an option combination to match "step counting" for
the { inferior superior ulterior } threads and I'd like to determine a similar characterization for this thread

submitting puzzles one by one to an oracle for a binary yes/no may be fun for some, but not me

could you post the techniques applied to arrive at the solution for the two puzzles you cited?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ab » Tue Aug 22, 2006 10:25 pm

well in the last puzzle you only need the naked quad in the top right corner. This eliminates the two ones in column 8 leaving only one 1 in that column, which is a backdoor single for the puzzle.

in the other puzzle locked candidates type 1 in column 4 and the top middle box account for one of the hidden pairs leaving two hidden pairs. Locked candidates type 2 in row 5 and the left middle box account for one of the jellyfish (sorry not swordfish as i said before), which leaves two jellyfish on 3s, which account for the same candidates, so only one of them is needed.
ab
 
Posts: 451
Joined: 06 September 2005

Postby gsf » Tue Aug 22, 2006 10:58 pm

ab wrote:well in the last puzzle you only need the naked quad in the top right corner. This eliminates the two ones in column 8 leaving only one 1 in that column, which is a backdoor single for the puzzle.

in the other puzzle locked candidates type 1 in column 4 and the top middle box account for one of the hidden pairs leaving two hidden pairs. Locked candidates type 2 in row 5 and the left middle box account for one of the jellyfish (sorry not swordfish as i said before), which leaves two jellyfish on 3s, which account for the same candidates, so only one of them is needed.

thanks, that helps a bit
did you solve with a speciific technique order? if so, what is it?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ab » Wed Aug 23, 2006 9:02 am

gsf wrote:did you solve with a speciific technique order? if so, what is it?

No I have two pieces of software I use to analyse these puzzles, which are in my software package
( http://uk.geocities.com/aidan_001/software.html )
With one of them I can add or remove solving techniques and see if the puzzle is solved or not. The other steps through the solution. I think Tarek probably does a much more thorough analysis of the solutions.

These programs use my own wierd files - when I originally wrote them I wasn't thinking of distributing them - maybe I should make versions which read standard puzzle strings.
ab
 
Posts: 451
Joined: 06 September 2005

Postby gsf » Wed Aug 23, 2006 1:37 pm

ab wrote:
gsf wrote:did you solve with a speciific technique order? if so, what is it?

No I have two pieces of software I use to analyse these puzzles, which are in my software package

without an order I'm at a loss to describe your acceptance criteria

is it possible to meet your criteria looking at all of the moves at a given position?
or does it require recursion on all possible moves?

for example, suppose a puzzle can be solved in one move with one jellyfish or
two moves with a double this move which uncovers a triple for the next -- which solution gets rejected?

my point is that there is a big difference between a solver that looks at
all moves at the current position vs. one that looks at all moves at the current and future positions
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ab » Wed Aug 23, 2006 2:15 pm

gsf wrote:is it possible to meet your criteria looking at all of the moves at a given position?
or does it require recursion on all possible moves?

for a candidate puzzle I enter it into my program and it should find a solution (otherwise the puzzle is too hard or has multiple solutions!). Then I turn off quads, swordfish and jellyfish and if the puzzle still has a solution it's not superior plus.
That should also answer the follow up question:
gsf wrote:for example, suppose a puzzle can be solved in one move with one jellyfish or
two moves with a double this move which uncovers a triple for the next -- which solution gets rejected?

I guess the problem arises when you try to count the techniques required as you did. The further analysis I did there was computer aided, ie I looked at the puzzles with my software. I only did that for a couple of puzzles because you made certain claims of them which turned out to be not quite as you claimed. The puzzles *could* be solved using the techniques you described, but the puzzles could be solved using lesser techniques (techniques that solve superior puzzles for example) along with a subset of the techniques you uncovered. ie only some of them were *required* to solve the puzzles. I'm sure that's also true for other puzzles on your list.

In even the simplest puzzles that can be solved with singles you can find quads and jellyfish etc, but you don't *need* to use them to solve the puzzle.
ab
 
Posts: 451
Joined: 06 September 2005

Postby daj95376 » Wed Aug 23, 2006 4:28 pm

I should stay out of this, but I'm going to try and be helpful. Here's the hierarchy of my (limited) solver's techniques.

Code: Select all
/* naked  singles        */
/* hidden singles        */
/* naked  pair           */
/* naked  triple         */
/* locked candidates (1) */
/* locked candidates (2) */
/* naked  quad           */
/* hidden pair           */
/* hidden triple         */
/* hidden quad           */
/* X-Wing                */
/* Swordfish             */
/* Jellyfish             */
/* XY-Wing               */
/* XYZ-Wing              */
/* BUG+1                 */
/* Unique Rectangle 1    */
/* Templates (basic)     */
/* XY-Chain              */
/* Forcing Chain/Net     */
/* EBC -- Singles        */
/* EBC -- Multiple       */

Here's the most difficult technique employed in solving each of gsf's puzzles.

Code: Select all
Puzzle # 1:  Naked  Triple
Puzzle # 2:  X-Wing
Puzzle # 3:  Naked  Triple
Puzzle # 4:  Naked  Triple
Puzzle # 5:  X-Wing
Puzzle # 6:  X-Wing
Puzzle # 7:  X-Wing
Puzzle # 8:  X-Wing
Puzzle # 9:  Naked  Quad
Puzzle #10:  Naked  Triple
Puzzle #11:  X-Wing
Puzzle #12:  Naked  Quad
Puzzle #13:  Swordfish
Puzzle #14:  Naked  Quad
Puzzle #15:  X-Wing
Puzzle #16:  Swordfish
Puzzle #17:  Naked  Quad
Puzzle #18:  Swordfish
Puzzle #19:  Naked  Quad
Puzzle #20:  Naked  Triple
Puzzle #21:  Naked  Quad
Puzzle #22:  Naked  Triple
Puzzle #23:  Swordfish
Puzzle #24:  Naked  Triple
Puzzle #25:  Naked  Quad
Puzzle #26:  Swordfish
Puzzle #27:  Naked  Triple
Puzzle #28:  Naked  Quad
Puzzle #29:  Naked  Triple
Puzzle #30:  Swordfish
Puzzle #31:  Swordfish
Puzzle #32:  Swordfish
Puzzle #33:  X-Wing
Puzzle #34:  Swordfish
Puzzle #35:  Swordfish
Puzzle #36:  Naked  Quad
Puzzle #37:  X-Wing
Puzzle #38:  Naked  Quad
Puzzle #39:  Jellyfish
Puzzle #40:  Swordfish
Puzzle #41:  Jellyfish
Puzzle #42:  Naked  Quad
Puzzle #43:  Jellyfish
Puzzle #44:  Jellyfish
Puzzle #45:  Jellyfish
Puzzle #46:  Hidden Quad
Puzzle #47:  Jellyfish
Puzzle #48:  Naked  Quad
Puzzle #49:  Jellyfish
Puzzle #50:  Naked  Quad
Puzzle #51:  Naked  Quad
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby tarek » Wed Aug 23, 2006 4:41 pm

daj95376 wrote:Here's the hierarchy of my (limited) solver's techniques.
Code: Select all
...
/* naked  pair           */
/* naked  triple         */
/* locked candidates (1) */
/* locked candidates (2) */
/* naked  quad           */
/* hidden pair           */
/* hidden triple         */
/* hidden quad           */
...


Is there a reason why you arrange subsets in such a way (The hidden subset which you catch must be rare)?

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

Postby gsf » Wed Aug 23, 2006 4:53 pm

ab wrote:for a candidate puzzle I enter it into my program and it should find a solution (otherwise the puzzle is too hard or has multiple solutions!). Then I turn off quads, swordfish and jellyfish and if the puzzle still has a solution it's not superior plus.

In even the simplest puzzles that can be solved with singles you can find quads and jellyfish etc, but you don't *need* to use them to solve the puzzle.


aha
now we're getting somewhere
(my goal is to define your search algorithmically)
you are using some form of ordering and grouping

the situation in the last statement is probably never hit by most solvers
because looping constructs lead to inherent ordering and the tendency to
try easiest first

I'll take a first hack at the ordering and grouping and hope you can refine it
(1) naked and hidden singles
(2) box line
(3) naked and hidden pairs, x-wing
(4) naked and hidden triples, swordfish
(5) naked and hidden quads, jellyfish
(I really don't care about the specifics, I just care that there are specifics)

then your top level method would be to attempt to solve using only methods
1..k for k = 1 2 3 4 5, and stop at the k that leads to a solution

doing this would allow the assertion: this puzzle requires at least 1 application of method k

now, given an ordering and grouping you could set up a solution weight
that could be used in a minimization problem statement
this would also allow a fair solution ranking
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby daj95376 » Wed Aug 23, 2006 6:34 pm

tarek wrote:
daj95376 wrote:Here's the hierarchy of my (limited) solver's techniques.
Code: Select all
...
/* naked  pair           */
/* naked  triple         */
/* locked candidates (1) */
/* locked candidates (2) */
/* naked  quad           */
/* hidden pair           */
/* hidden triple         */
/* hidden quad           */
...


Is there a reason why you arrange subsets in such a way (The hidden subset which you catch must be rare)?

tarek

I really don't have much justification for my ordering. I'm not looking for speed and I find it easier to think in terms of subsets before other, higher techniques, so that's how I arranged my hierarchy. Often, Locked Candidates can mask the existence of concurrent Naked Pairs/Triples, so I place Locked Candidates after them because I want to know if they exist.

I should move the hidden subsets to a later position in my hierarchy, but I find it interesting how often they occur when not tackling the hardest puzzles.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby tarek » Wed Aug 23, 2006 7:16 pm

This does not sound like how A Human would solve........

Hidden subsets seems to be easier to spot than the naked counterpart:D for non PM solvers..........

I'm still with the opinion that for the technique to be "needed", you have to define a set of techniques (ex. Superior plus set of techniques), the puzzle is unsolvable within that set of techniques if that specific technique is removed.

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

Postby gsf » Wed Aug 23, 2006 9:27 pm

tarek wrote:This does not sound like how A Human would solve........

Hidden subsets seems to be easier to spot than the naked counterpart:D for non PM solvers..........

I'm still with the opinion that for the technique to be "needed", you have to define a set of techniques (ex. Superior plus set of techniques), the puzzle is unsolvable within that set of techniques if that specific technique is removed.

right -- and this can be expanded to a count of how many times each technique is required

could you provide a non-PM solver ordering/grouping using {...} for grouping techniques with the same weights:
B1 box line type 1
B2 box line type 2
T1 naked single
H1 hidden single
T2 naked pair
H2 hidden pair
W2 x-wing
T3 naked triple
H3 hidden triple
W3 swordfish
T4 naked quad
H4 hidden quad
W4 jellyfish

for example, the inferior thread ordering/grouping is {T1H1}
(naked and hidden singles treated equally)
and the ulterior thread is B2H1 and not {T1H1}
(box-line type 2 before hidden single and not solvable by singles)
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby daj95376 » Thu Aug 24, 2006 12:07 am

ab wrote:This thread is a sequel/homage to the superior puzzles thread. In that thread puzzles had to be solvable using hidden and naked sets up to triples, locked candidates and x wings and to qualify as superior they had to require triples or x wings from that list.

I suggest adding quads to complete the hidden and naked sets and also extending the idea of x wings to include swordfih and jellyfish. So to qualify as a superior plus puzzle a puzzle must be solved by hidden and naked sets up to quads, locked candidates, x wings, swordfish and jellyfish and must require one of the following techniques from that list: hidden or naked quads, swordfish or jellyfish.

tarek wrote:I'm still with the opinion that for the technique to be "needed", you have to define a set of techniques (ex. Superior plus set of techniques), the puzzle is unsolvable within that set of techniques if that specific technique is removed.

Rewording tarek's definition in terms of ab's lists:

Code: Select all
I) A puzzle must first be shown to be solvable using only the full list of techniques above. Then ...
II) The puzzle must be shown to be unsolvable if only the lesser list of techniques is used.

All of gsf's puzzles meet condition (I). I ran them again to see if they met condition (II). Here's my results.

Code: Select all
No : Puzzles 1-12,14,15,17,19-22,24,25,27-29,33
Yes: Puzzles 13,16,18,23,26,30-32,34-51


This does not seem to agree with some of ab's comments on gsf's puzzles. What is the correct list of acceptable and unacceptable puzzles?
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby gsf » Thu Aug 24, 2006 4:26 am

daj95376 wrote:
Code: Select all
No : Puzzles 1-12,14,15,17,19-22,24,25,27-29,33
Yes: Puzzles 13,16,18,23,26,30-32,34-51


I get the same results
also note that I posted a spectrum of puzzles showing the number of quads.triples.pairs used
using the inferior thread method of applying and counting techniques
and expected that some of them would not be superior plus

ab has added a minimization requirement not present in that thread
and I'm just trying to flesh out the details of the minimization to see
how it affects solving algorithms -- there are a couple of questions I
don;t know the answer to or even if the answers are tractable,
for example, could the greedy application of lighter techniques cause
a solution to require more heavy techniques -- maybe one less light
technique could lead to one less required heavy technique -- if so how
do you quantify that? how do you search for that? how do you specify
it so that more than one person/program can reproduce results?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ab » Thu Aug 24, 2006 10:33 am

guess what I get the same results, which shows that the requirements are easy to replicate.

gsf wrote:ab has added a minimization requirement not present in that thread

I don't remember adding any minimization requirements, remind me what they were.
ab
 
Posts: 451
Joined: 06 September 2005

PreviousNext

Return to General