Equivalence Sets for Completed Grids of 17 Clue Puzzles

Programs which generate, solve, and analyze Sudoku puzzles

Equivalence Sets for Completed Grids of 17 Clue Puzzles

Postby swb01 » Sun Mar 07, 2021 5:49 pm

Hello, I am new to this forum (or any Sudoku forum). Please let me know if this post is of interest.
As an exercise, I processed the completed grids from Gordon Royle’s list of 17 clue puzzles (the version with 49,157 entries) and derived a table of the essentially equivalent grids - those pairs that can be mapped from one to the other using validity preserving transformations – switching digits, rows and columns, along with possibly one transposition of rows to columns. The row and column transformations conform to inter-stack/inter-band movement rules – e.g. if one row goes to another band, its two band-partners must also go to the same other band.
I found that grids from 44,133 entries were singletons – exhibiting no essentially equivalent relationship with the other grids. 5,024 Grids participate in equivalence sets as summarized in the table below:

Code: Select all
    #Grids in Set  Cases Found  Total Grids
         2            1,778       3,556
         3              252         756
         4               83         332
         5               17          85
         6               21         126
         7                6          42
         8                4          32
         9                1           9
        11                1          11
        12                1          12
        14                1          14
        20                1          20
        29                1          29
                      -------     -------
                      2,167       5,024

Here: https://drive.google.com/drive/folders/12stWqlhXWVy9vLvvTLno7v4IqZCmkqEx?usp=sharing is a folder with the 2,167 17C completed grid equivalence sets. A readme file provides information about the table and two examples are provided for using the table entries to map from one grid to another within an equivalence set.
Last edited by swb01 on Thu Apr 22, 2021 3:00 am, edited 5 times in total.
swb01
 
Posts: 28
Joined: 07 March 2021
Location: Potomac, Maryland

Re: Equivalence Sets for Completed Grids of 17 Clue Puzzles

Postby denis_berthier » Mon Mar 08, 2021 6:05 am

swb01 wrote:Hello, I am new to this forum (or any Sudoku forum). Please let me know if this post is of interest.
As an exercise, I processed the completed grids from Gordon Royle’s list of 17 clue puzzles (the version with 49,157 entries) and derived a table of the essentially equivalent grids - those pairs that can be mapped from one to the other using digit, row, and column transformations and in some cases a row-to-column transposition. I found that grids from 43,133 entries were singletons – exhibiting no essentially equivalent relationship with the other grids. 5,024 Grids participate in equivalence sets


Hi swb01,
Welcome on this forum.
What you're saying about duplicate pairs in the 17-clue collection is surprising.
I've used this collection long ago (when I wrote my first book on sudoku solving, "The Hidden Logic of Sudoku" [HLS]) and, as far as I can remember, it has always been assumed that there were no isomorphism duplicates in this collection. But I never checked it myself.
Could you provide a precise example of a duplicate pair, with the corresponding isomorphism?
BTW, you are not mentioning towers/stacks or floors/bands transformations. Did you use these isomorphisms in your software?

swb01 wrote:apologies for the formatting):

If you want to have some formatting of some part of a post, you have to surround that part by "[code ]"......"[/code ]" tags, either manually or using the code button. This is a painful process to do manually, column after column. Do NOT use tabs within the "code" tags or the result is unpredictable (as below).
Code: Select all
   #Grids in Set;  Cases Found;   Total Grids
         2;               1,778;             3,556
         3;                  252;                756
         4;                   83;                332
         5;                   17;                  85
         6;                   21;                126
         7;                    6;                  42
         8;                    4;                  32
         9;                    1;                    9
        11;                    1;                  11
        12;                       1;                  12
        14;                    1;                  14
        20;                       1;                  20
        29;                       1;                  29
                       ;  -------            ; -------
                       ; 2,167            ; 5,024



swb01 wrote:Except for the size limitation of 256KB, I would like to attach the results table (1,157KB) with 5,024 entries is attached in comma-separated-variable format with the following columns: Reference Number from the list of 49,157 17 Clue Puzzles; Completed Grids; Digit Order; Row Order; Column Order; Set Count (1 to number of equivalent grids); Identical Grid Count; Set Identifier (1 to 2,167); Transposition Indicator (“Base” for first entry in a set; “T” if Transposition required relative to the Base; otherwise “D” for Direct).

This forum is not a good place for publishing large collections. If you are not allergic to Google, you can use google sites: https://sites.google.com/ I've personally used GitHub to publish a very large collection, but that was because I already had another project there and it also included the software I used to generate the collection.
denis_berthier
2010 Supporter
 
Posts: 2678
Joined: 19 June 2007
Location: Paris

Re: Equivalence Sets for Completed Grids of 17 Clue Puzzles

Postby Mathimagics » Mon Mar 08, 2021 7:05 am

denis_berthier wrote:What you're saying about duplicate pairs in the 17-clue collection is surprising.

swb01's table is about grid isomorphisms - the 17C puzzle set involves some cases where the same ED grid has more than one 17C puzzle (and indeed there is one grid with 29 puzzles).

His table is correct (wrt the Royle set, anyway. I think we have found one or two more puzzles since then). So his method must have correctly handled all valid transformations.

The number quoted for "singletons", 43133, should be 44133 ...

Cheers
MM
User avatar
Mathimagics
2017 Supporter
 
Posts: 1812
Joined: 27 May 2015
Location: Canberra

Re: Equivalence Sets for Completed Grids of 17 Clue Puzzles

Postby denis_berthier » Mon Mar 08, 2021 8:19 am

Mathimagics wrote:
denis_berthier wrote:What you're saying about duplicate pairs in the 17-clue collection is surprising.

swb01's table is about grid isomorphisms - the 17C puzzle set involves some cases where the same ED grid has more than one 17C puzzle (and indeed there is one grid with 29 puzzles).

Hi Mathimagics.
Thanks for the answer.
Do you know any reason why this collection was not reduced to an isomorphism-free one, as is usually the case with any collection ?
Is there an isomorphism-free version of the collection somewhere?
denis_berthier
2010 Supporter
 
Posts: 2678
Joined: 19 June 2007
Location: Paris

Re: Equivalence Sets for Completed Grids of 17 Clue Puzzles

Postby Mathimagics » Mon Mar 08, 2021 11:03 am

Puzzle collections are usually isomorphism-free with respect to the puzzles. So the 17C collection is actually isomorphism-free, in that sense.

Counting the number of ED solution grids in a puzzle collection is less common. I'm usually interested, of course - there's my LCT project (Low Clue Threshold) - and of course swb01 has registered some interest with this thread.

If you solve the 17C puzzle collection, then canonicalise the solution grids, you can then easily count the number of grids with 17C puzzle(s), and also easily derive swb01's table.

Or you can just download Mladen's "17grids46300.zip" (located here)

PS: since these collections were built, a new puzzle (#49158) has been found, on a distinct grid, so there are now 49158 17C puzzles on 46301 grids.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1812
Joined: 27 May 2015
Location: Canberra

Re: Equivalence Sets for Completed Grids of 17 Clue Puzzles

Postby denis_berthier » Mon Mar 08, 2021 12:15 pm

Mathimagics wrote:Puzzle collections are usually isomorphism-free with respect to the puzzles. So the 17C collection is actually isomorphism-free, in that sense.

Mystery explained.
I thought swb01 was talking of puzzles. When solving, that's what counts.
denis_berthier
2010 Supporter
 
Posts: 2678
Joined: 19 June 2007
Location: Paris

Re: Equivalence Sets for Completed Grids of 17 Clue Puzzles

Postby coloin » Mon Mar 08, 2021 11:13 pm

Code: Select all
........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8.......#49158

Yes the solution grid with the 29 puzzles was termed the SF grid .... [Strangely familiar !]
coloin
 
Posts: 2083
Joined: 05 May 2005


Return to Software