GridChecker, an exhaustive puzzle enumerator

Programs which generate, solve, and analyze Sudoku puzzles

Re: GridChecker, an exhaustive puzzle enumerator

Postby tarek » Tue Nov 06, 2012 12:36 pm

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.
User avatar
tarek
 
Posts: 2575
Joined: 05 January 2006

Re: GridChecker, an exhaustive puzzle enumerator

Postby David P Bird » Wed Nov 07, 2012 11:46 am

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.
David P Bird
2010 Supporter
 
Posts: 938
Joined: 16 September 2008
Location: Middle England

normalization

Postby dobrichev » Wed Nov 07, 2012 2:07 pm

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.
dobrichev
2016 Supporter
 
Posts: 1302
Joined: 24 May 2010

Re: GridChecker, an exhaustive puzzle enumerator

Postby David P Bird » Wed Nov 07, 2012 3:18 pm

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.
David P Bird
2010 Supporter
 
Posts: 938
Joined: 16 September 2008
Location: Middle England

Re: GridChecker, an exhaustive puzzle enumerator

Postby daj95376 » Wed Nov 07, 2012 4:54 pm

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

Re: GridChecker, an exhaustive puzzle enumerator

Postby Serg » Wed Nov 07, 2012 7:49 pm

Hi, daj95376!
daj95376 wrote:
Afmob wrote:
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
Serg
2017 Supporter
 
Posts: 499
Joined: 01 June 2010
Location: Russia

pattern minlex

Postby dobrichev » Wed Nov 07, 2012 8:47 pm

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.
dobrichev
2016 Supporter
 
Posts: 1302
Joined: 24 May 2010

Re: pattern minlex

Postby ronk » Wed Nov 07, 2012 9:25 pm

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

Postby Afmob » Wed Nov 07, 2012 9:33 pm

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 . . . . . . .
Afmob
 
Posts: 130
Joined: 28 June 2011

Re:

Postby daj95376 » Thu Nov 08, 2012 3:08 am

{Withdrawn]
Last edited by daj95376 on Thu Nov 08, 2012 10:55 am, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Re:

Postby dobrichev » Thu Nov 08, 2012 9:02 am

daj95376 wrote:Is there a final objective of these discussions, because I missed it if it was mentioned earlier?
no
dobrichev
2016 Supporter
 
Posts: 1302
Joined: 24 May 2010

Re: GridChecker, an exhaustive puzzle enumerator

Postby Serg » Fri Nov 09, 2012 6:28 am

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 Derevin'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 Derevin'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
Serg
2017 Supporter
 
Posts: 499
Joined: 01 June 2010
Location: Russia

Postby Afmob » Fri Nov 09, 2012 7:08 am

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

Edit: The direct link does not work. :(
Last edited by Afmob on Fri Nov 09, 2012 8:33 pm, edited 1 time in total.
Afmob
 
Posts: 130
Joined: 28 June 2011

Re: GridChecker, an exhaustive puzzle enumerator

Postby coloin » Fri Nov 09, 2012 8:01 pm

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
Last edited by coloin on Tue Dec 17, 2013 12:20 am, edited 1 time in total.
coloin
 
Posts: 1575
Joined: 05 May 2005

Re: GridChecker, an exhaustive puzzle enumerator

Postby Afmob » Fri Nov 09, 2012 8:38 pm

coloin wrote: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.
Afmob
 
Posts: 130
Joined: 28 June 2011

PreviousNext

Return to Software

cron