The New Sudoku Players' Forum

[RW]

Thank you gsf for the info, I'm still hoping that one day I'll be able to understand all of your program.

What i wonder is, how SE could solve puzzles 7 and 11 of Oceans gold list above (have no java here), when they need coloring.
My program could only solve nr 7 (23 steps), but i dont trace, if x-wing or UR1 have been used (thought SE only uses LC and subsets ?)

My solver used Templates for many coloring techniques. I ran puzzles #7 & #11 with it enabled and with it disabled. Short contradiction chains following Hidden Singles easily replaced all of the Templates eliminations. Is it possible that SE did something similar?

daj, ravel was refering to coloring within the forcing chains. I too think it's strange that gsf's program needs coloring... My first suspision was that SE would solve them with region or cell forcing chains, AFAIK both gsf and ravel use only contradiction forcing chains. But I just followed a step by step solution to both puzzles in SE that used only contradiction forcing chains, with nothing more than locked candidates or pairs... No uniqueness used at any point.

gsf, is it possible for you to get a pm grid of where your program gets stuck if you only allow locked candidates and subsets in the propositions? I'd be very interested to see what is the next SE move at that point.

RW

[gsf]

Thank you gsf for the info, I'm still hoping that one day I'll be able to understand all of your program.

me too (for me understanding)

gsf, is it possible for you to get a pm grid of where your program gets stuck if you only allow locked candidates and subsets in the propositions? I'd be very interested to see what is the next SE move at that point.

subsets meaning singles pairs triples quads?

[RW]

subsets meaning singles pairs triples quads?

I think pairs should be enough, couldn't spot any more than that in the SE solution, but you can include triples and quads also, if that reveals more eliminations but still no solution.

RW

[gsf]

gsf, is it possible for you to get a pm grid of where your program gets stuck if you only allow locked candidates and subsets in the propositions? I'd be very interested to see what is the next SE move at that point.

#7 solves with -q 'FNBTHP(FNBTH)-G' (box/line and tuples up to and including quads)
#11 requires the addition of order 2 and 3 x-wing (swordfish): -q 'FNBTHWP(FNBTHW)-G'

these options list the pm for the no-x-wing sticking point for #11:

Code: Select all

-E -q 'FNBTHP(FNBTH)-G' -f'%#ph'

which produces

Code: Select all

  478     489      1    |  3579    5789     2    |  3489     6      389
  2678     3      679   |  179      4      789   |  1289     5      1289
   5      2489     49   |   6      189     389   |   7      3489   12389
------------------------+------------------------+------------------------
  234     245      8    |1234579   579    34579  |  1349    3479     6
  3467     1      457   |  3459    5689  3456789 |  3489     2      3789
   9      246     347   |   12     1268    3478  |   5      3478    1378
------------------------+------------------------+------------------------
  368     5689     2    |  579     5679     1    |  389     3789     4
  468      7      4569  |  2459     3      4569  |  289      1      2589
   1      459     3459  |   8      279     4579  |   6      379    23579


[RW]

Very interesting... At that point there's two simple nishio contradictions:
If r5c4=5 => r4c2=5 => r7c5=5 => no 5 in row 1
If r5c5=5 => r4c2=5 => r7c4=5 => no 5 in row 1

Maybe there's even some modern fish for these. How come your program cannot find these, don't seem like very complex forcing chains to me...

Edit: Actually, it isn't even a modern fish, it's a finned swordfish:

Code: Select all

 *--------------------------------------------------------------------------------------*
 | 478      489      1        |*3579    *5789     2        | 3489     6        389      |
 | 2678     3        679      | 179      4        789      | 1289     5        1289     |
 | 5        2489     49       | 6        189      389      | 7        3489     12389    |
 |----------------------------+----------------------------+----------------------------|
 | 234     *245      8        |*1234579 *579     #34579    | 1349     3479     6        |
 | 3467     1        457      |-3459    -5689     3456789  | 3489     2        3789     |
 | 9        246      347      | 12       1268     3478     | 5        3478     1378     |
 |----------------------------+----------------------------+----------------------------|
 | 368     *5689     2        |*579     *5679     1        | 389      3789     4        |
 | 468      7        4569     | 2459     3        4569     | 289      1        2589     |
 | 1        459      3459     | 8        279      4579     | 6        379      23579    |
 *--------------------------------------------------------------------------------------*

RW

[gsf]

Very interesting... At that point there's two simple nishio contradictions:
If r5c4=5 => r4c2=5 => r7c5=5 => no 5 in row 1
If r5c5=5 => r4c2=5 => r7c4=5 => no 5 in row 1

Edit: Actually, it isn't even a modern fish, it's a finned swordfish:

so the nishio gets you [54]^5?

anyway, don't do nishio or fins
probably won't do nishio, thinking about fins

[RW]

so the nishio gets you [54]^5?

anyway, don't do nishio or fins
probably won't do nishio, thinking about fins

Yes, both r5c4<>5 and r5c5<>5. To me nishio is just a contradiction forcing chain that works with a single digit. The eliminations as forcing chains:

[r5c4](-5-[r7c4])-5-[r5c3]=5=[r4c2]-5-[r7c2]=5=[r7c5]-5-[r1c5]=5=[r1c4]-5-[r5c4]
[r5c5](-5-[r7c5])-5-[r5c3]=5=[r4c2]-5-[r7c2]=5=[r7c4]-5-[r1c4]=5=[r1c5]-5-[r5c5]

If I understood your program correctly it makes propositions and finds contradictions based on that. Isn't this a contradiction that comes from a proposition? What's the difference to the eliminations your program normally does with the propositions, other than that this only use a single digit?

RW

[gsf]

If I understood your program correctly it makes propositions and finds contradictions based on that. Isn't this a contradiction that comes from a proposition? What's the difference to the eliminations your program normally does with the propositions, other than that this only use a single digit?

I had to stand back and think on this
with FNP(...)-G, the solver is restricted to use only the constraints in ... to resolve propositions
and -G means no guessing
so solutions may only progress when propositions provide eliminations or placements
all propositions are tried at each board position, so nothing is missed
so with a given P(...) its not that the solver isn't capable of solving per se
its that with the given propositions constraints it is not possible to solve

so the puzzle isn't solved because fish (with or without fins) are not in the proposition constraint set

now the nishio at that position may provide some eliminations
but those don't progress the puzzle with the given P(...) proposition constraints

that's the whole idea behind P(...) w.r.t rating
the more constraints required in P(...) => the harder the puzzle

[RW]

so with a given P(...) its not that the solver isn't capable of solving per se
its that with the given propositions constraints it is not possible to solve

so the puzzle isn't solved because fish (with or without fins) are not in the proposition constraint set

But I can't see why fish would be required in the proposition constraint set. Using finned fish, this doesn't require any proposition at all, the pattern with eliminations is already there. Without finned fish, the proposition r5c4=5 or r5c5=5 does reach a contradiction with only hidden singles in the proposition constraint set. I believe that for all fish and Nishio contradictions, a proposition on the deducable candidate should lead to a contradiction with nothing but hidden singles and locked candidates in the proposition constraints.

Apart from these eliminations, your solver has found all eliminations SE can find without using X-wing and Swordfish in the chains at this stage of the puzzle.

RW

[gsf]

with propositions there are two constraint sets in scope: basicP(proposition)
from experimentation I keep the basic constraints weaker that the proposition constraints
since I haven't come across a puzzle where basic > FN solved when basic == FN didn't
when basic <= proposition also holds

this puzzle shows that there are some finned fish that cannot be solved by X and/or Y cycles (known)
and that finned fish are somehow related to x-wings (classic order n fish) in the proposition constraints

the last point makes sense because finned fish are analyzed by both eliminating and setting the fins cells

anyway, it boils down to: my solver doen't do fins, so for some hard puzzles
will require stronger proposition constraints to solve (without pure guessing)

[RW]

I'm sorry that this discussion gets a bit repetitive... Have I got something wrong about the way your solver uses propositions? The way I understood it: When none of the basic constraints lead to further eliminations, it makes a proposition, then continues to solve from that proposition using the given proposition constraints. IOW it sets the proposition candidate to true and continues to solve from that point. If it finds a contradiction, the proposition candidate can be eliminated. Is this true?

If it is, then candidate 5 from r5c4 and r5c5 should be eliminated with nothing but hidden singles in the proposition constraints. You keep saying that it requires x-wing, but I can see with my own eyes that it doesn't, at the point where your solver stopped:

Code: Select all

  478     489      1    |  3579    5789     2    |  3489     6      389
  2678     3      679   |  179      4      789   |  1289     5      1289
   5      2489     49   |   6      189     389   |   7      3489   12389
------------------------+------------------------+------------------------
  234     245      8    |1234579   579    34579  |  1349    3479     6
  3467     1      457   |  3459    5689  3456789 |  3489     2      3789
   9      246     347   |   12     1268    3478  |   5      3478    1378
------------------------+------------------------+------------------------
  368     5689     2    |  579     5679     1    |  389     3789     4
  468      7      4569  |  2459     3      4569  |  289      1      2589
   1      459     3459  |   8      279     4579  |   6      379    23579

If r5c4=5 => r7c4<>5, r1c4<>5, r5c3<>5 => r4c2=5 (hidden single in box) => r7c2<>5 => r7c5=5 (hidden single in row) => r1c5<>5 => no 5 in row 1 = contradiction.

Where's the x-wing? I guess my main question is: Which part of this chain does something different than your program does when using propositions with hidden singles?

I suspect that this has nothing to do with x-wings in proposition constraints. My guess is that when you allow x-wings, your solvers next move is r5c6<>4, r8c6<>4, r5c3<>4 and r1c7<>8, not any of these finned swordfish eliminations...

RW

[gsf]

I'm sorry that this discussion gets a bit repetitive... Have I got something wrong about the way your solver uses propositions? The way I understood it: When none of the basic constraints lead to further eliminations, it makes a proposition, then continues to solve from that proposition using the given proposition constraints. IOW it sets the proposition candidate to true and continues to solve from that point. If it finds a contradiction, the proposition candidate can be eliminated. Is this true?

discussion is good

I think this may be where the confusion lies

I formulated propositions to act independently:
for each candidate in the cell under consideration
set the cell to that value and apply the proposition constraints
(singles in this example)
there can be one of three outcomes
(1) contradiction -- the cell cannot have this value
(2) solution -- the cell has this value and the proposition constraints solve the puzzle
(3) inconclusive

there is another step that can be taken, and my solver does this when guessing,
but not when applying propositions:
for each cell retain the pm's for each candidate proposition that does not lead to a contradiction
and use the union pm when evaluating subsequent propositions
some cells in the union will have only one value, as you noted above

I'll see about adding a batched variant of this as an alternative proposition constraint
in the guessing form its labelled L (for learning)
alluding to some tree search techniques that combine data gained
from guesses that may constrain future guesses

you can manually check how the propositions progress by limiting the solver
to singles and applying each candidate value for cell r5c4
for this puzzle each candidate assignment is inconclusive when limited to singles

[tarek]

I'm not sure where the minimum RMS now stands..... with all of these ultra ultra hard now creeping up .... Anyway here are 2 puzzles which were interesting

Code: Select all

Fluid Drive #8
 9 . . | . . 1 | 8 . . 
 . 6 . | . 3 . | . . . 
 . . 2 | 5 . . | . . 7 
-------+-------+------
 . . 9 | . . . | . . 6 
 . 5 . | . . . | . 2 . 
 4 . . | . . . | 3 . . 
-------+-------+------
 3 . . | . . 8 | 1 . . 
 . . . | . 4 . | . 8 . 
 . . 7 | 9 . . | . . 5      SE=10.5, gsfr=99789,Suexr=930

The following is not a pearl - so it can't be a fluid drive

Code: Select all

Gyroscope #1
 . 6 . | 9 . . | . . 3 
 5 . . | . . 4 | . 2 . 
 . . . | . 8 . | 4 . . 
-------+-------+------
 8 . . | . . . | . 5 . 
 . . 3 | . . . | 7 . . 
 . 9 . | . . . | . . 1 
-------+-------+------
 . . 1 | . 5 . | . . . 
 . 7 . | 3 . . | . . 9 
 9 . . | . . 2 | . 4 .      SE=N/A, gsfr=99960,Suexr=830

[gsf]

=> no 5 in row 1 = contradiction

well I'll be
it looks like my solver restricted to singles neglects to look for 'zeros'
this is a flaw in the model that splits each constraint into individual functions
the current return is '#moves', 0 for no moves
it must also allow constraints to detect invalid state
in particular the hidden single constraint must be allowed to return "not under bozo's big top"
fixing this will have the effect of changing some "indeterminant" proposition returns to "contradiction"
more later ... thanks

[gsf]

subsets meaning singles pairs triples quads?

I think pairs should be enough, couldn't spot any more than that in the SE solution, but you can include triples and quads also, if that reveals more eliminations but still no solution.

after fixing the proposition logic to validate at least one of each candidate for each row/col/box
this puzzle solves with singles/box-line/hidden-pair proposition constraints
so it now agrees with your observations
thanks for pointing this out
I'll repost the solver in a day or so