The New Sudoku Players' Forum

[tarek]

The method which IIRC Ruud uses in his solver. Canonicalizes the pattern then relabels the resulting canonical pattern in ascending order. So in the canonicalization process you are comparing strings of 0s & 1s only & not strings of 0,1,2,...9s. Therefore there is a chance to miss a more min-lex puzzle & If the min-lex pattern has pattern automorphisms then there is a chance to miss a more min-lex puzzle for that min-lex pattern.

[David P Bird]

I'm a spectator rather than a player on this topic and don't have the computing power of you guys, so these are only academic thoughts:

There seems to be an unwarranted obsession to find the minimal lexical order when canonicalising a puzzle grid. The requirement is that the process followed must always provide the same unique result and whether it is minimal or not is irrelevant.

As I see it, the canonical puzzle grid should solve to give the canonical form of the solution grid. This would then allow different clue sets for the same solution grid to be highlighted and explored when they exist.

Most puzzles are not automorphic and all that these require is for the solution grid to be canonicalised and members of the clue set to be identified say by underlining them. This would then identify which clues are common to different puzzles based on the same solution grid. Obviously, when presenting the puzzle only the clue set would be given.

Now if we used the minilex form knowing that row 1 will contain the digits in ascending order may detract from the solving pleasure. To avoid this once the minimal canonical form has been found it can be scrambled in a predetermined way that's dependent on the solution. One way of doing this using the Anchor-5 system is to use the mod 3 sum of the mini-rows containing digit 5 in boxes 1,5,9 to determine the right shifts of the columns in each parent stack and likewise with mini-columns in boxes 3,4,8 to determine the row shifts. A solver would only be able to reverse all these steps once the puzzle is effectively solved.

Automorphic puzzles present a problem. It's easy enough to select the canonical from of the solution grid, but the clues will appear in different cells depending on the transformation route needed to reach each automorphic form. This can be handled by examining where the clues will be positioned for each transformation route and using the one with the minimal lexical or positional value. However if the same automorphic puzzle grid appears with different clue sets, determining how many clues there are in common between them would require one set to be cyclically transformed through the different automorphic repeats for comparison purposes. That said, I can't see a way to overcome this whatever the canonicalisation system.

[dobrichev]

Hi David P Bird,
The subject was to find minimal lexical order when canonicalising a puzzle with non-givens represented with a smallest lexicographically ordered symbol. Not the solution grids. This allows puzzles having more than one solution to be normalized in this way. Whether it is minimal, maximal, or any other, there is no sense as you said.
Moreover, a pattern could be normalized in this way, where pattern is representation only of the geometry with all givens projected to "1".

Concerning automorphic grids/puzzles/patterns, the reverse process causes indeterminism. There are several ways to transform a source to the same indistinguishable target and respectively the reverse processes give more than one result.

[David P Bird]

Hi Dobrichev, thanks for your response.

tarek's post got me thinking about recognising when composers re-cycled solution grids by transposing interesting ones and setting alternative clue sets for them rather than generating and testing new ones.

I hadn't considered the question of easily recognising the geometrical pattern of the givens, or clue subsets having more than one solution.

Sorry for being off-topic.

[daj95376]

Code: Select all

. . . . . . . . 1
. . . . . . . 2 .
. . . . . 3 . . .
. . . . 4 . 5 . . 
. . 6 . . . 3 . .
. . 7 8 1 . . . .
. 1 . . 2 . . . 4
. 3 . . . . . 7 .
9 5 . . . . . . .


Code: Select all

. . . . . . . . 1
. . . . . . . 2 .
. . . . . 3 . . .
. . . . 4 . 5 . . 
. . 6 . . . 3 . .
. . 7 8 2 . . . .
. 3 . . . . . 7 .
. 2 . . 1 . . . 4
9 5 . . . . . . .


The latter has a lexicographically smaller pattern but the first is lexicographically smaller.

As an observer whose trying to understand which hairs are being split in the current discussion, it occurs to me that this isn't a suitable example because the first puzzle has one solution and the second puzzle has 71 solutions.

[Serg]

Hi, daj95376!

Code: Select all

. . . . . . . . 1
. . . . . . . 2 .
. . . . . 3 . . .
. . . . 4 . 5 . . 
. . 6 . . . 3 . .
. . 7 8 1 . . . .
. 1 . . 2 . . . 4
. 3 . . . . . 7 .
9 5 . . . . . . .


Code: Select all

. . . . . . . . 1
. . . . . . . 2 .
. . . . . 3 . . .
. . . . 4 . 5 . . 
. . 6 . . . 3 . .
. . 7 8 2 . . . .
. 3 . . . . . 7 .
. 2 . . 1 . . . 4
9 5 . . . . . . .


The latter has a lexicographically smaller pattern but the first is lexicographically smaller.

As an observer whose trying to understand which hairs are being split in the current discussion, it occurs to me that this isn't a suitable example because the first puzzle has one solution and the second puzzle has 71 solutions.

I think afmob's example is correct, because both published puzzles have the equivalent (or "essentialy the same") patterns. It is quite possible to see 2 puzzles having the same pattern, provided that one puzzle has unique solution and another puzzle has multiple solutions. (It is usual thing when someone is doing exhaustive search, for example.)

I think canonicalization algorithms should be applicable to invalid puzzles (or pseudo-puzzles) too. It can be very useful during searhing code cross-check, for example.

But afmob could be express his idea in more evident way, I think. He could exchange rows r7/r8 of the first puzzle and obtain lexicographic less puzzle, but lexicographic more pattern.

Serg

[dobrichev]

Here is an example by Patrice where puzzle minlex beats pattern minlex

Code: Select all

.....1..2..3....4..5..6.1....63...5..7..2.8..8....6.....9.4.....6.7..9..7....2..1 #pattern
.....1..2..1.3..4..5.2..6.....7...8...7.2.3..9....3..4..9.5..2..8.6.....4.......9 #puzzle

.....1..2
..3....4.
.5..6.1..
..63...5.
.7..2.8..
8....6...
..9.4....
.6.7..9..
7....2..1

.....1..2
..1.3..4.
.5.2..6..
...7...8.
..7.2.3..
9....3..4
..9.5..2.
.8.6.....
4.......9


The trick is the repeating value (1) at the beginning of the first and the second rows.

[ronk]

Here is an example by Patrice where puzzle minlex beats pattern minlex

Comparing the results of pattern canonicalization to that of puzzle or sub-puzzle canonicalization makes no sense to me. What is the basis for such a comparison?

[Afmob]

Sorry for the confusion, I messed up the 2nd puzzle. It should be an isomorph of the first puzzle. Here is the correct version (lexicographically smaller pattern but still not lexicographical minimal):

Code: Select all

. . . . . . . . 1
. . . . . . . 2 .
. . . . . 3 . . .
. . . . 4 . 5 . . 
. . 6 . . . 3 . .
. . 7 8 2 . . . .
. 3 . . . . . . 7
. 2 . . 1 . . 4 .
9 5 . . . . . . .


[daj95376]

{Withdrawn]

[dobrichev]

Is there a final objective of these discussions, because I missed it if it was mentioned earlier?

no

[Serg]

Hi, all!
Current discussion in this thread started with Afmob's remark about gridchecker's canonicalization algorithm. Afmob stated that canonicalization algorithm used in gridchecker differs from Michael Deverin's canonicalization algorithm, because the last canonicalizes pattern first, and then canonicalizes puzzle using possible pattern's automorphisms. It was experimentally observed that gridchecker don't canonicalizes pattern first, so minlex forms of puzzles having equivalent (isomorphic to each other) patterns can have not coinciding patterns. To my mind we are discussing several questions:

1. Can gridchecker run in the mode when puzzle's pattern is canonicalized first, and then the puzzle will be canonicalized using possible pattern's automorphisms?
2. Does Michael Deverin's canonicalization algorithm for puzzles canonicalization includes puzzle's pattern canonicalization at the first stage? (Is this algorithm published elsewhere?)
3. Is there available puzzles canonicalization tool which canonicalizes pattern first, and then canonicalizes puzzle using possible pattern's automorphisms?
4. Should any puzzles canonicalization algorithm canonicalize pattern first?

As to me, it would be useful to be sure canonicalization will produce the same output patterns for puzzles having equivalent patterns (question 4), but I'am afraid such algorithms are slower because they should canonicalizes pattern first.

Serg

[Afmob]

You can find Michael Deverin's algorithm in the programmer's forum. The direct link is this.

Edit: The direct link does not work.

[coloin]

The problem was mentioned here

Have we got an example where the isomorphic puzzles from automorphic grids give different [minlex puzzles] and different [minlex pattern puzzles with minlexed clues]. ???

Also the puzzle from the minlex grid solution is also not a format which a solver can ignore easily.

We have seen in the above post that the minlexpattern wih minlex clues can be but frequently isnt different fom the minlex puzzle.

For me a puzzle having the same pattern as another is an important distinction.

I have long thought that the maxlex pattern with maxlex clues is the more useful format in terms of puzzle creation. I think that is why champagne does it this way.

Most puzzles will start with

Code: Select all

+---+---+---+
|98.|7..|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+

and the clues will be more compressed towards the beginning of the string
C

[Afmob]

Have we got an example where the isomorphic puzzles from automorphic grids give different [minlex puzzles] and different [minlex pattern puzzles with minlexed clues. ???]

Such an example can not exist. If we use some kind of canonicalization method, we choose the smallest or largest puzzle from a finite number of isomorphic puzzles and only one puzzle can be the smallest/largest. But if a puzzle has automorphisms there might be multiple, different transformations which lead to the same canonical puzzle.