Sudoku Explainer: Bugs, Quirks and Other Remarks...

Programs which generate, solve, and analyze Sudoku puzzles

Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

Postby ronk » Thu Oct 14, 2010 1:05 pm

PIsaacson wrote:
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.

PIsaacson wrote: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?

PIsaacson wrote: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.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re:

Postby gsf » Thu Oct 14, 2010 1:24 pm

Pat wrote:
PIsaacson wrote: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

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:
--man wrote: #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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

Postby eleven » Thu Oct 14, 2010 5:29 pm

PIsaacson wrote: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.
eleven
 
Posts: 1557
Joined: 10 February 2008

Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

Postby PIsaacson » Thu Oct 14, 2010 5:56 pm

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
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

Postby gsf » Thu Oct 14, 2010 9:51 pm

PIsaacson wrote: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!)
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

Postby daj95376 » Fri Oct 15, 2010 7:30 am

PIsaacson wrote: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.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

Postby lksudoku » Fri Oct 15, 2010 10:22 am

daj95376 wrote: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
lksudoku
 
Posts: 90
Joined: 06 October 2010

Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

Postby PIsaacson » Fri Oct 15, 2010 10:50 am

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
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

Postby daj95376 » Fri Oct 15, 2010 6:47 pm

PIsaacson wrote: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
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

Postby PIsaacson » Sat Oct 16, 2010 1:38 am

Danny,

The first APE example for SE at http://diuf.unifr.ch/people/juillera/Sudoku/InterestingSudokus.html#APE resolves to:
Image
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
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

Postby daj95376 » Sat Oct 16, 2010 2:56 am

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
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

Postby ronk » Sat Oct 16, 2010 7:41 am

PIsaacson wrote: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.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Sudoku Explainer: Bugs, Quirks and Other Remarks...

Postby eleven » Sat Oct 16, 2010 11:46 am

daj95376 wrote: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.

lksudoku wrote: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.
eleven
 
Posts: 1557
Joined: 10 February 2008

re: Sudoku Explainer corrected by lksudoku

Postby Pat » Tue Oct 19, 2010 8:57 am

on page 2, lksudoku (2010.Oct.10) wrote: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

elsewhere, lksudoku (2010.Oct.18) wrote:
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


thanks for posting the fixed version!!

* ran it from the command line,
couldn't get the GUI
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Re: re: Sudoku Explainer corrected by lksudoku

Postby lksudoku » Tue Oct 19, 2010 9:29 am

Pat wrote:* 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
lksudoku
 
Posts: 90
Joined: 06 October 2010

PreviousNext

Return to Software