## superior plus puzzles

Everything about Sudoku that doesn't fit in one of the other sections
ab wrote: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.

if I'm getting too tedious on this let me know ...

criteria which simply applies the all techniques in scope at the current
position as one batch move without checking if any are needed or not

when a puzzle is rejected because a technique is not required/needed
then there is an implied minimization -- I'm trying to get a handle on
that implied minimization, in particular, how to program it without
manually babysitting a solver

also, in order to be able to differentiate required vs. superfluous techniques
in a solution one needs a technique order or weighting at minimum
I'm still trying to figure out what kind of problem (algorithmically) we're
dealing with here, and what kind of search it implies

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

applying techniques in this order
Code: Select all
`H1BH2T1H3W2T2H4W3T3W4T4`

(Hn: hidden n-tuple, Tn: (naked) n-tuple, Wn: order n xwing, B: box-line)
in contrast to (my default) order
Code: Select all
`T1H1BT2H2W2T3H3W3T4H4W4`

which leads to a solution with a naked triple as the heaviest (hardest) technique

this also anwers one of my questions in a previous post:
different application order of lighter techniques can affect
required heavier techniques later in the solution
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

I don't think you can tell that a technique is required that way.......
The only way is:

1. The technique in question is the last in the order & was used to solve.

OR

2. The removal of The technique in question from the order would lead to an unsolvable puzzle.

You do not have to babysit the solver........
you need to solve the puzzle several times [equal to the number of techniques under focus]... to cover either point 1 or point 2 above. each time the result would give a YES or NO verdict.

This was the main reason why I went several times through The Superior list for Re-Ranking......

tarek

tarek

Posts: 2761
Joined: 05 January 2006

tarek wrote:I don't think you can tell that a technique is required that way.......
The only way is:

1. The technique in question is the last in the order & was used to solve.

OR

2. The removal of The technique in question from the order would lead to an unsolvable puzzle.

You do not have to babysit the solver........
you need to solve the puzzle several times [equal to the number of techniques under focus]... to cover either point 1 or point 2 above. each time the result would give a YES or NO verdict.

for one fixed order I agree
any will do
but without one conclusions on specific solutions will be arbitrary
the example in my previous post shows how technique order
can affect the weight and number of techniques required

put another way, without a technique order, the search for absolute minimal
required techniques to solve would involve checking multiple orders at each move
in a solution -- and my solver as it currently stands would require babysitting to do that
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

If you are talking about the Minimal path to solve the puzzle then that is a different issue......

knowing that a technique is required doesn't give information about where it is in the solution nor how many times it is needed. you have to go through a more elaborate re-ordering as you just mentioned.

I was after the fact that says "If A, B and C are needed then I have to use A, B and C to solve", it doesn't say how I use them to solve, because the 24 riddle pretty much gives you a picture of how tricky that can be , I'm sure that you'll find a decent Au pair

tarek
Last edited by tarek on Thu Aug 24, 2006 2:03 pm, edited 1 time in total.

tarek

Posts: 2761
Joined: 05 January 2006

Here are some thoughts / ideas for discussion ...

The set of allowed techniques may be divided into TWO groups: non-Splus and Splus techniques.
A puzzle that solves with non-Splus techniques only does not qualify.
A puzzle that does not solve with allowed techniques (non-Splus + Splus techniques) does not qualify.
All other puzzles are Splus puzzles (by definition).

A batch solver can sort out the Splus puzzles in two separate batches.
Opinion 1: Attempting to mix the two batches into one is a potential source for trouble. Such algorithms are possible, but it is required that these behave AS IF THE BATCHES WERE SEPARATE.

Opinion 2: Any attempt to rank (give priority to) the techniques WITHIN each group is nonsense, and only leads to confusion.

Conjecture: Attempting to solve an Splus puzzle with only non-Splus techniques leads to a partly solved puzzle, or a partly solved state. This state is identical for all possible move orders. Isomorphic puzzles have isomorphic 'partly solved states'.

The set of Splus techniques may be divided into the folloing types:
1. NQ/HQ (row/col): Naked quad in row or column, with hidden quad counterpart.
3. NQ/HV (row/col): Naked quad in row or column, with hidden quint counterpart.
4. NQ/HV (box): Naked quad in box, with hidden quint counterpart.
5. HQ/NV (row/col): Hidden quad in row or column, with naked quint counterpart.
6. HQ/NV (box): Hidden quad in box, with naked quint counterpart.
7. Swordfish
8. Jellyfish

The Swordfish and Jellyfish may be further divided into subtypes, according to their type of cell pattern.

The Splus puzzles may be classified according to what kind of Splus technique(s) that solve them. The simplest case is when one particular technique solves the puzzle, and no other does. More complicated cases are: 1. Puzzles that solve with alternative techniques. 2. Puzzles that need more than one Splus technique. Combination of (1) and (2) is also possible.

Opinion: Any classification system should be independent of the particular order moves are applied.

OK - only some thoughts... if there are errors, please correct them. if there are different opinions, please express them.
Ocean

Posts: 442
Joined: 29 August 2005

very nice Ocean, this is what I was doing in the Superior thread......

Is there a way to optimise it.......

to me it looks like at least (nonSplus +(1,2,3,4,5,6)*2 + (7,8)) = 15 algorithms

tarek

tarek

Posts: 2761
Joined: 05 January 2006

Ocean wrote:Here are some thoughts / ideas for discussion ...

The set of allowed techniques may be divided into TWO groups: non-Splus and Splus techniques.
A puzzle that solves with non-Splus techniques only does not qualify.
A puzzle that does not solve with allowed techniques (non-Splus + Splus techniques) does not qualify.
All other puzzles are Splus puzzles (by definition).

A batch solver can sort out the Splus puzzles in two separate batches.
Opinion 1: Attempting to mix the two batches into one is a potential source for trouble. Such algorithms are possible, but it is required that these behave AS IF THE BATCHES WERE SEPARATE.

thanks for spelling this out
I'm able to specify this in one pass by filtering puzzles that solve with one set of techniques
but do not solve with another
Ocean wrote:Conjecture: Attempting to solve an Splus puzzle with only non-Splus techniques leads to a partly solved puzzle, or a partly solved state. This state is identical for all possible move orders. Isomorphic puzzles have isomorphic 'partly solved states'.

I wasn't certain of this but the conjecture holds with puzzles scraped from the forums
it does rely on properly coded techniques (I wasn't certain of that either)
Ocean wrote:The Splus puzzles may be classified according to what kind of Splus technique(s) that solve them. The simplest case is when one particular technique solves the puzzle, and no other does. More complicated cases are: 1. Puzzles that solve with alternative techniques. 2. Puzzles that need more than one Splus technique. Combination of (1) and (2) is also possible.

(1) and (2) are what I'm wrestling with
determining splus membership as you laid it out is straightforward
figuring out how to minimize the splus techniques applied is not
e.g., is it sufficient to look at the splus moves available at one level to determine the required ones
or must you look recursively at future levels too
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

thanks for all the comments on ordering etc.
it sunk in enough that I can filter puzzles that require at least n superior plus techniques

I believe each of these requires at least 2 superior plus techniques
if others concur then I'll explain the comment numbers and how they
relate to tarek's inferior thread steps and ocean's recent post
these are the only requires at least 2 splus puzzles found
all the rest require at least 1
Code: Select all
`#13.2.11-C25.m/S2.d/F7.27/N7.26/B7.29.3.6/T12.50.5.7/H6.16.6/W3.13.2.1.1. . . | . 4 1 | . . .. 8 . | . 9 . | . . .2 . 4 | 5 . 3 | . . .------+-------+------. . . | . 1 . | 6 . 4. . . | 9 . 2 | . 5 7. . . | . 7 . | 1 . .------+-------+------9 6 1 | . . . | 4 . .. . 7 | . . . | . 9 .. . 5 | . . . | 2 . .#14.2.12-C28.M/S2.a/F9.24/N10.27/B5.28.3.5/T12.34.5.7.1/H5.9.2.2.1/W2.5.4.0.1. . 8 | . . . | . . 7. 1 . | . . . | 5 . .9 . . | . . . | . 3 4------+-------+------. . . | . . 2 | . . .. . . | . 3 8 | 4 . .. . . | 9 4 . | 8 2 5------+-------+------. 6 . | . 2 5 | . 1 .. . 2 | . . 3 | 6 . 93 . 5 | . . 6 | . 4 .#15.2.13-C26.M/S2.p/F6.24/N11.29/B6.16.5.3/T8.36.4.5/H7.16.5.2/W6.18.5.1.1. . 2 | 6 . 3 | . . 8. . 9 | . . 1 | 2 . .. . . | . 7 . | . 3 .------+-------+------6 . . | . . 8 | 9 . .. 5 . | . . . | . 7 .. . 3 | 7 . . | . . 4------+-------+------. 3 . | . 5 . | . . .. . 5 | 1 . . | 8 . .2 . . | 9 . 6 | 1 . .#17.2.15-C27.M/S2.v/F9.29/N9.25/B8.20.6.6/T15.33.5.10/H7.11.4.3/W5.16.6.2.1. . 3 | . 7 . | 9 . .. . 1 | 5 . 9 | 6 . .5 . . | 6 . 3 | . . 7------+-------+------. . . | . . . | . . .. 1 8 | . . . | 2 5 .4 . . | 1 . 5 | . . 9------+-------+------1 . . | 9 . 6 | . . 4. . . | . . . | . . .. 5 . | 7 . 1 | . 8 .#17.2.15-C18.m/F11.32/N11.31/B9.37.8.7/T14.65.8.10.2/H5.9.4.1. 7 . | . 4 . | . . .. . . | . 3 . | . . 5. . . | 8 . . | 1 . .------+-------+------4 . 3 | . . . | . 2 .. . . | 5 . 1 | 9 . .6 . . | . . . | . . .------+-------+------. 5 . | 9 . . | 7 . .2 . . | . . . | . 4 .. . . | . . . | . . .`
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Fantastic gsf, I particularly liked puzzle #2,#3

tarek

tarek

Posts: 2761
Joined: 05 January 2006

I think it was well worth all the arguing given the result

Nice collection of puzzles gsf
ab

Posts: 451
Joined: 06 September 2005

gsf wrote:it sunk in enough that I can filter puzzles that require at least n superior plus techniques
I believe each of these requires at least 2 superior plus techniques

Nice puzzles, gsf! A few comments:
Code: Select all
`puzzle #1: First: Swordfish (cell pattern 2+2+2; 3+1+0 eliminations).  Later: Jellyfish (cell pattern 3+2+2+2; 2+1+1+0 eliminations).  No alternative paths (only one instance available each time).puzzle #2: First: Two alternative quads (naked or hidden; same box; quint counterparts). A. Naked quad: Later Jellyfish (one choice, and solves the puzzle). B. Hidden quad: Later Jellyfish (one choice, and solves the puzzle).puzzle #3: First: Swordfish (cell pattern 3+2+2; 2+2+1 eliminations) (one choice).  Later: Jellyfish (cell pattern 4+4+3+2; 3+2+2+1 eliminations) (one choice).puzzle #4: First:Swordfish (cell pattern 2+2+2; 3+2+1 eliminations) (one choice).  Later:Another Swordfish (cell pattern 3+2+2; 3+2+0 eliminations) (one choice).puzzle #5: First: Naked quad (in box, hidden quad counterpart. One choice). Later: Naked quad (in row, hidden quad counterpart. One choice).`

The second puzzle (#2) is characterized by a branching solution path, since there are two alternative quads available, and both lead to solution without needing the other.
For the other four puzzles there is only one superior plus technique available at each crucial state.
Puzzle #1 and #3 are similar (first Swordfish, later Jellyfish), but they differ by the cell patterns and eliminiation patterns for their respective fishes.

#---
Also: Thanks for testing the conjecture (about all possible move orders leading to the same partly solved state) on puzzles. I believe the conjecture is valid and can be proved, but don't know how.
Ocean

Posts: 442
Joined: 29 August 2005

Ocean wrote:Nice puzzles, gsf! A few comments:

thanks for the analysis
there are some positions where my solver finds more than one order
n x-wing (n=3 swordfish n=4 jellyfish) and I don't think they are duals
typically one is for columns, the other for rows, both on the same cell value,
but involving different cells
I'll annotate your analysis with my solver -v2 x-wing trace that lists the
cell value, rol/col orientation, the order, and the cells
Code: Select all
`puzzle #1: First: Swordfish (cell pattern 2+2+2; 3+1+0 eliminations).  Later: Jellyfish (cell pattern 3+2+2+2; 2+1+1+0 eliminations). 8:r/4:[13][14][16][18]/[43][44][46][48]/[63][64][66][68]/[73][74][76][78]8:c/4:[31][51][81][91]/[35][55][85][95]/[37][57][87][97]/[39][59][89][99] No alternative paths (only one instance available each time).puzzle #2: First: Two alternative quads (naked or hidden; same box; quint counterparts). A. Naked quad: Later Jellyfish (one choice, and solves the puzzle).7:r/4:[23][24][25][28]/[43][44][45][48]/[53][54][55][58]/[83][84][85][88]7:c/4:[31][61][71][91]/[32][62][72][92]/[36][66][76][96]/[37][67][77][97] B. Hidden quad: Later Jellyfish (one choice, and solves the puzzle).puzzle #3: First: Swordfish (cell pattern 3+2+2; 2+2+1 eliminations) (one choice). 7:r/3:[22][23][29]/[42][43][49]/[92][93][99]7:c/4:[31][51][71][81]/[34][54][74][84]/[36][56][76][86]/[37][57][77][87] Later: Jellyfish (cell pattern 4+4+3+2; 3+2+2+1 eliminations) (one choice).4:r/4:[12][13][15][18]/[22][23][25][28]/[42][43][45][48]/[92][93][95][98]4:r/4:[31][51][71][81]/[34][54][74][84]/[36][56][76][86]/[37][57][77][87]puzzle #4: First:Swordfish (cell pattern 2+2+2; 3+2+1 eliminations) (one choice).8:r/3:[32][35][37]/[62][65][67]/[72][75][77]8:c/4:[11][21][41][81]/[14][24][44][84]/[16][26][46][86]/[19][29][49][89] Later:Another Swordfish (cell pattern 3+2+2; 3+2+0 eliminations) (one choice).`

if the doubles are duals then my code (and brain) certainly missed that

now I'll comment on how I coaxed the solver to filter superior-plus
please don't take this as a plug for my solver per-se
the main point is that there is a concise notation that can be used to describe
superior+ and other similar puzzle collections

first, the techniques are labeled by a letter and a digit for order (size)
T=naked-tuple H=hidden-tuple B=box-line W=x-wing G=backtrack-guess
T1=naked-single W4=jellyfish etc.

the -q option controls the techniques in scope and the application order
{...} groups techniques to be applied as a batch, batch meaning all techniques
within a group are first identified at the current position, and then they are applied in one batch

in batch (-B) mode: at each position the solver starts with the left most group
and checks if any techniques progress the puzzle,
if so then all techniques that progress the puzzle are identified,
and then applied as a batch, and the solver restarts with the first group again
if the current group does not progress the puzzle then the next group
is attempted, and so on
if no groups progress the puzzle then it is rejected

group application is directly related to step counting
each application of a group counts as one step
(this matches the inferior/ulterior step counts)

here are the (-q) ordering expressions for some of the *erior threads
'-' before a technique in the order disables that and subsequent techniques
so -G means 'no guessing / backtracking'
finally, ':' within a group means 'commit the moves to this point'
but continue with the rest of the group (and still only count the
entire group as one step)
Code: Select all
`inferior     {T1H1}-Gulterior     {B2:H1}-Gsuperior     {T1H1BT2H2W2T3H3}-Gsuperior+    {T1H1BT2H2W2T3H3}{W3T4H4W4}-G  `

this is why I kept bugging this thread with minutiae
the next *erior thread can post a similar expression and (bonus) I won't ask any questions

so the superior+ has two groups as outlined by ocean
the first contains the non-plus techniques, the second the plus techniques,
(and then the -G because my solver requires backtacking to be explicitly disabled)

the filtering part involves expression on statistics gathered by the solver
these are named by singles letters with order digits, just like the techniques,
with extras like V:puzzle-is-solvable, In:#steps-for-group-n
so this (-e) expression was used to filter the recent 5 puzzle submission
Code: Select all
` V && I2>1`

i.e., puzzle solvable with given constraints and the second group was applied
(required) in at least 2 steps

finally, since we can formulate superior+ in a manner to the other *eriors
the step counting is already done -- those are the n.n.n numbers in the
puzzle commentary -- <#steps>.<#plus-steps>.<#non-plus-steps>
so we can have a taxonomy of superior+ steppers

note that we haven't seen any >2 plus-steppers yet
Last edited by gsf on Sat Aug 26, 2006 7:57 am, edited 1 time in total.
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

I tried configuring my puzzle generator for superior plus puzzles. Did I come close?

Code: Select all
`# Swordfish (207 -- not listed but available)# Swordfish + Singles only.....2.599....81...8419.....1.85.3..8.......5..5.14.8.....3159...72....149.5.......4...1.7.7.5...6..2.1.74..4329...................5293..13.4.2..6...9.1.3.7...9....8..7...7..9.......2.5.9.645...6..2....4....1..2...589.6.1.5.......2..9...4..2...4.8..6.279..6...3..81.3..9.1.........7.4.3.........6.3..4.71..1...8..374.9..1.2..7...81.....9.178....37..69.36..5...5.7.8.2.3...7..65.25..39....198.7.....31...9..8.254....5...79..4.6...5..7...2.8..6.......3..3.4...7..5...6.8..48...7....569.4..8.6.2.5..71...3...2.73...4.3.2.....2.8...5.6.....8.3.3...75.4...5...17..6.4.3.2..938...158..5......1..9.2..9.5.4...1.7.....5.2...1.9.7..9.5..8......2..332...459.39.5.78....7..8....8.....75..324....4.27.96.3....832..67.....2....8..3....59.6.484.7..9....3...29..5...1...69...75.....52.34.....49...16...4...3..25...6....3..1.45....49...28..17...4..7...2.8.4....5..5.6.1..4....5.2.6...9..8...27..56...48....154..96...1.8.....6.76.5.....1.5.....7.4...6.1.....8.7.....4.96.9.....7.4...27..156..1.52.7.12.7..3.7..9..6...2.6....8.........3....7.5...9..2..3.3..1.57.1.87.9..27.....8.6....5.43...34...2..6.27....5..1.6..4....84.7..8...73...56.4....1.4.....87..682.9..........98.7..2...4.2..7..6.1.7.5.2..7..1.8...8..6.49..........2.954..876.35.2..59...7......9.21....8.....1.3.....8.2.....6....91.3......2...37..3.75.168...6.....2.34.9....92.8.3..84.....3.91.2.86.7.....21..7.4.16....8.79.4.....3...78..1...2..15....96..4.865....264.9.............9.782....832.6..94....38..2...9..59.36..1..87..425...5.....47...264...2...7...6...915...71.....5...459..81..9..12.4# Jellyfish.....154..4.7.82.15.1..3...3....687.....4.....258....4...1..3.68.65.2.1..326........2.17..2.35.....7.9.3...5.....62...5.....6...28.....8...2.5.9.....51.8..19.7.....4.1.2.716...7.3...3..5.........3152...8...6516.........3..7...2.6...417.8.5.6....6..82...2.1....41.4....38...43.79.....6.....63.82...29....8.36....9.7...78..6....9..281..7..8....8....3..6.81....2....297....2....34.1..4....9....2..8..348..6...1729...889..1......2...1.4.384....2.4..5..3.2....194.7.3...4......3..299...4578..2.7..15..5..8...9..73..8....96...81.........31...87....2..35..8...2..9..65..7.1..4....19.....42..7.....75....24....8.6.291.5.4....82....95.....8..67.....75....8..829..7...19..3..56...7..9.2.....51....237....96.....2.6..8...73..1..95...5..683.1..9.3..2...2...14..5.8....758.2..4...........1..9.835....7.3..98...5...4..8.9..12..4.5..9.7..6......8.2.53.8.97...6.7..3.6..8.3...97.4.57.3.9......7..8.3..2.4..74.6.5.1.825...16.......6..2.....9721....6....5971.....9..4.......29...658.5.7.4.96.5..8..7.......8...7459....4..2...6.1.7.6.9.5...8..7....8652...6.......8..2..1.98....9.....4.6...17.631...8.3.4...17..1...8..24...6.3.1...274.64...3.9.....6....38.7..139.1..49..2......6.81.3...48..6.......2..13...6.97.8......2..17..9.169..2.8# Jellyfish + Singles only..5.2..7.41....2.9.7.4.......2.3...4...1.5...5...4.6.......3.6.9.6....32.5..6.9..3....9...41..7..59...45..8.8...3.5.4..7...8..5.1.4...7.2..83...98..1..32...7....8# Swordfish + Swordfish...7.13.8.7....21......6.97...18...2.9.....8.5...69...73.2......81....2.9.28.7.....45.89168....2.....54......2.3..1.4.........7.3..1.2......32.....1....96482.93....6.5........2785..2.9....78..6.9.7.6...4...3.5.2.8..17....2.4..6519........7.1....71....515..2....8.273..6.2....7.8...4.1.5...8.6....7.2..734.6....6..714....18...64.1.....295.6..47...23...6....7..3..3.6.5..9..3....7...19...64..7.293.....3.71.17...34...4...73....6.9..1.2..8.91.6....6....8.73.1..4.9..1.7....37...9...19...42# Swordfish + Jellyfish.....827..2......38...31...2568......3.....5......3982...67...51......2..623.......826.7...1.....2.4.6..7.8.164...8......8......9...417.9.6..2.5.8.....4...2.159..# Naked Quad..3.4..829.52..13..8.3.....5.........2.5.9.4.........8.....2.1..31..64.584..1.6..5...1.42...4.3..1921.9....3.9.3....1.........8....1.9.3....7.4292..4.5...48.5...76...7.2.4.7......6..91.4...4.53........427........13.9...9.27..5......6.3.7.5...27...6..3935......8..43..7.....7.4.2.....5.....8.2.9.....8..72..5......8623..4...5`
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

Yes they're all good

I think I'll add the 8 of them for requiring two splus techniques to the list. Any requests to add some of the jellyfish or naked quad puzzles will be considered.
ab

Posts: 451
Joined: 06 September 2005

gsf wrote:if the doubles are duals then my code (and brain) certainly missed that

Why are they not duals? (Every fish has a dual, which eliminates exactly the same candidates. Where are the duals here, if not the listed doubles?)
Ocean

Posts: 442
Joined: 29 August 2005

PreviousNext