The New Sudoku Players' Forum

[ronk]

Code: Select all

.1...2...34.........2.57......3..1.7..9...4..1.5..8......69.3.........62...7...9. 1 5.0 1.2 1.2 1.5822ms

.3...1...14.........2.95......3..6.7..5...9..2.7..8......14.3.........69...7...2. 2 5.0 1.2 1.2 1.1845ms


Both puzzles scored 5.0 1.2 1.2 and produced nearly identical presentation of methods/techniques. I have tested using the -Jnnn option to generate multiple transformations, but it appears that I cannot guarantee identical scores without placing puzzles into a known minlex format.

After swapping given values <1> and <3>, do you still get ER=5.0?

Code: Select all

.3...2...14.........2.57......1..3.7..9...4..3.5..8......69.1.........62...7...9.
.1...3...34.........2.95......1..6.7..5...9..2.7..8......34.1.........69...7...2.

Some techniques, such as aligned pairs/triples, are highly sensitive to transformations that take a set of cells that are confined to a single chute (it was the only way I could get APE/ATE to find productive reductions), and then subsequently scatter them such that they are no longer confined to a single chute.

Similar to "What happens in Vegas, stays in Vegas" ... I think "what's in a chute, stays in a chute." If not, do you have an example?

Is there a list of techniques that are known to be either consistently stable or else not expected to be stable with regards to transformations?

Not really. However, I seem to recall denis_berthier writing about "convergence" of a rule set ... as long as uniqueness techniques weren't included. AFAIK that was lost with the site crash. Moreover, it may not even have applied.

[gsf]

Question for Glenn:

I've tried to use the subcanon.c code since it seemed fairly self-contained and it was easy enough to bind together with my other C++ code, but it doesn't generate minlex transformations that match the -f"%c" option.

I looked at the sudoku.c code and it looks like there is a "canon" function embedded in that source that provides minlex transforms as well. Is that the code I should be using if I want to exactly match the -f"%c"???

yes

it's canon() in sudoku.c

thanks Pat

canon() implements %c and is based on the row order minlex of the solution grid
subcanon() (by Michael Deverin) implements %#mc and is pure row order minlex

the --man option describes the difference between %c and %#mc in the #m section:

#m: Puzzle in subgrid row order minlex canonical order with
solution cells listed as 0. The default canonical form is
based on the solution grid; subgrid canonical does not
require the grid to have a solution. %.27#mc and %.54#mc
canonicalize the catenation of the first 3 and 6 rows
(1 and 2 bands) respectively.

canon() requires valid puzzles as input (that produce one solution grid)
and its performance is about the same over all clue counts

subcanon() does not require valid grids, but its performance degrades with increasing clue count
for the 17s catalog subcanon() is 30% faster than canon()
for ~30 clues subcanon() and canon() are about even
for 81 clues subcanon() is 98% slower than canon()

for solution grids canon() and subcanon() produce the same output

canon() has additional parameters to only canonicalize band 1 or band1&2 (when all 27 or 54 clues are present)
this is used by the -gb option that produces the catalog of all essentially different grids

[eleven]

Is there a list of techniques that are known to be either consistently stable or else not expected to be stable with regards to transformations?

Do i understand the question right ?
A technique, which is not applicable exactly the same way to all equivalent grids (those you get with the well known equivalence operations), is rubbish.

[PIsaacson]

Ron,

Short results from your swapped grids:

Code: Select all

.3...2...14.........2.57......1..3.7..9...4..3.5..8......69.1.........62...7...9. 1 5.0 1.2 1.2 1.2433ms
.1...3...34.........2.95......1..6.7..5...9..2.7..8......34.1.........69...7...2. 2 5.0 1.2 1.2 1.0466ms

Both produced nearly identical full logs with the naked quad presenting at step 43 being the cause of the 5.0 score.

Pat,

Thanks for the information and links. I guess I should always search the Programmer's Forum for coding questions, especially since I'm kind of encroaching on this thread.

Glen,

I gotta admit that reading your code makes me realize just how much I don't know about the topic of grid transformation - let alone the implementations of various solving techniques. Thanks for shedding light and leading me gently on the correct path...

Cheers all,
Paul

[gsf]

Glenn,
I gotta admit that reading your code makes me realize just how much I don't know about the topic of grid transformation - let alone the implementations of various solving techniques. Thanks for shedding light and leading me gently on the correct path...

a few things about my solver code
little code has been deleted from it since 2005
when a good idea appears on the forums it may end up as another part of the solver (with attribution)
counter to good coding practice its all in one monolithic executable
this makes it easy for me to control versions and posting
and also avoids an explosion of tiny executables (and the maintenance headaches associated with that)
but
it makes it tough on the (code and man page) reader (including me!)

[daj95376]

I'm still in the process of debugging the last couple of dynamic forcing chains, but these lower level tests are good for seeing whether or not a transposed puzzle should score identically - using Ron's two puzzles listed above here's my full log output: ...

Both puzzles scored 5.0 1.2 1.2 and produced nearly identical presentation of methods/techniques. I have tested using the -Jnnn option to generate multiple transformations, but it appears that I cannot guarantee identical scores without placing puzzles into a known minlex format. Some techniques, such as aligned pairs/triples, are highly sensitive to transformations that take a set of cells that are confined to a single chute (it was the only way I could get APE/ATE to find productive reductions), and then subsequently scatter them such that they are no longer confined to a single chute. URs seem less sensitive since the 4 corners still exist regardless of transformations. ULs also seem to be fairly stable, but I don't have a sufficient numbers of test cases to be confident of that statement.

Wait a minute!!!

I ran all four puzzles through my (batch) solver and it returned identical solutions -- adjusted for transformations. Although I don't have APE/ATE as techniques in my solver, I do have XYZ-Wing and numerous URs implemented, and these techniques are confined to a chute, and none of them had any problem surviving the transformations!!! In fact, I can't recall any transformation that would not maintain the cells in a box and the boxes in a chute.

Given a single-step approach and concurrent URs of the same type that overlap, then I believe it may be possible for different ratings to occur. However, I doubt that concurrent and overlapping APEs/ATEs can interfere with each other.

[lksudoku]

I ran all four puzzles through my (batch) solver and it returned identical solutions

I believe that in a batch solver were all current technique moves are found before they are applied simultaneously, the rating and solution moves should be identical for all transposed puzzles

For a step solver which finds one move and then tries a different technique move, I have a conjecture that if no technique that is based on uniqueness of solution is incorporated by the solver, the rating should be the same for all transformations

[PIsaacson]

Daj,

When I restrict the aligned triples to a single chute, I'm getting much better results, although there are still some edge cases that I am investigating. Prior to today, I allowed the 3 cells A B C to be spread across 2 different chutes with AB in a tower for example and BC in the intersecting floor. That produced many additional ATEs, but at the cost of running much slower and with problems in handling transformations. I suspect that patterns (ALS chains come to mind) that span multiple chutes may experience problems with transformations??? I lack the math to express this as a proper problem let alone a proof of confirmation or confutation, but I plan on doing lots of additional testing. Trying to duplicate SE's scoring is, in and of itself, a monumental pain in the butt even with methods that locate the exact same patterns/chains.

Cheers,
Paul

[daj95376]

When I restrict the aligned triples to a single chute, I'm getting much better results, ...

Paul,

I must admit that my understanding of APE/ATE is limited to what I read in Sudopedia. From its description, it appeared that the APE/ATE were limited to using the 15 cells contained in a line and box the line intersects. To me, this would limit the APE/ATE to a subset of a chute.

Furthermore, I was able to derive the eliminations in the examples by using forcing chain logic -- ala Kraken cell -- on one of the three intersecting cells.

Regards, Danny

[PIsaacson]

Danny,

The first APE example for SE at http://diuf.unifr.ch/people/juillera/Sudoku/InterestingSudokus.html#APE resolves to:

As you can see, the 2 cells defining the APE are in the same floor, but otherwise un-aligned by row/col/box. There are only 6 peer cells between these 2, yet SE manages to find the APE exclusions!!! But, it's not 100% consistent and I'm finding APEs/ATEs that it mysteriously skips for some reason(s).

Cheers,
Paul

[daj95376]

Paul,

The problem with definitions is that they change over time and their implemention is at the whim of the person writing the software. I've researched the original definitions and everything is restricted to a line and box that intersect. That's what's presented in Sudopedia. However, Ruud's thread on APE almost immediately jumps off onto a discussion of any two cells being used in an APE scenario. It would appear that SE is playing by its own set of rules. A set of rules that appear to work with the way I would perform an APE/ATE.

I'd use a forcing chain on the candidates in a Kraken cell. I'd also restrict every chain's stream cells to those in a line and a box intersecting the Kraken cell. This logic works for the original definition ... and the way SE appears to perform its APE elimination. The only difference is that the original definition restricts the elimination cell to be in the intersection of the line and the box.

Now, let's consider the APE example you cited. I select [r8] as the line, [b8] as the box, and r8c5 as the Kraken cell present in both. Except for the elimination cell, the following streams are restricted to the line and box.

Code: Select all

r8c5=2 => r8c7=6 => r7c7<>6
r8c5=4 => r8c9=6 => r7c7<>6
r8c5=5 => r7c4=6 => r7c7<>6


Note: In the ATE example in Sudopedia, a multi-valued cell is used and reduced to a single value through a network effect from other assignments. This is a wrinkle that I didn't notice in the few APE examples I examined.

Regards, Danny

[ronk]

it's not 100% consistent and I'm finding APEs/ATEs that it mysteriously skips for some reason(s).

Paul, if you posted a couple of those, someone here would likely see the reason for that.

[eleven]

Given a single-step approach and concurrent URs of the same type that overlap, then I believe it may be possible for different ratings to occur.

For a step solver which finds one move and then tries a different technique move, I have a conjecture that if no technique that is based on uniqueness of solution is incorporated by the solver, the rating should be the same for all transformations

If you can get different ratings in a single step solver using uniqueness techniques depends on your implementation and rating of these steps. A main point here is, if your program can distinguish between given and derived numbers.
For a manual player its obvious, what was there and what he filled in. But (unfortunately) thats not the case for posted candidate grids. This means, that often you cant say, if there is a uniqueness elimination or not.

If e.g. you would not use a UR

Code: Select all

 12 12+3 .
----------
 12 12   .

and later get there

Code: Select all

 1  2+3  .
-----------
 2  1    .

you of course still can eliminate the 2. This is just a subpattern compareable to

Code: Select all

  12 123 23

being a subpattern of

Code: Select all

 123 123 123

But if one of 1 or 2 in the second pattern were a given, the elimination would not be possible.

[Pat]

I managed to find and correct the bug in the source code for finding unique loops in SE

In short, there is a recursive method for finding loops, when trying to find a loop and getting to the situation where the loop cannot continue, there is backtracking to the previous loop prefix; however when returning to that prefix, some information is not reset and therefore sometimes the prefix is continued with invalid state

The invalid state can result in some cases that the prefix will not continue to another loop which would have existed if the prefix state was valid

I also managed to provide a fix to the problem locally, and my version finds the transformed unique loop of the isomorphism bug example

Is there a way to provide the bug solution to the creator of SE? what are the ways for publishing a fixed version while maintaining the original license, and where should such a fix be placed?

i have never encountered Nicolas Juillerat on the SuDoku forums -- he's too busy

Current SE has a bug in the UL/UR code causing it not to find some UL that exist

I have created a fixed version of SE that should find all UL/UR

You can download the fixed jar file from
http://sites.google.com/site/sefixshare/files/FIXED1SudokuExplainer.jar

thanks for posting the fixed version!!

* ran it from the command line,
couldn't get the GUI

[lksudoku]

* ran it from the command line,
couldn't get the GUI

To run the GUI, simply type

Code: Select all

java -cp FIXED1SudokuExplainer.jar diuf.sudoku.gui.SudokuExplainer