Essentially different grids & group theory.

Programs which generate, solve, and analyze Sudoku puzzles

Essentially different grids & group theory.

Postby MartinCHarvey » Sun Mar 14, 2021 7:58 pm

Many thanks for previous assistance in this group. I get up to 12199113 isomorphisms with 11 givens, at which point, a small refactor to use less ram is necessary.

Save myself the computation time and disk space, is there a "Group theory for dummies" * textbook which I might find useful?

MH.

* Dummies = BSc math, but not a PhD ...
MartinCHarvey
 
Posts: 15
Joined: 22 February 2021

Re: Essentially different grids & group theory.

Postby Serg » Mon Mar 15, 2021 7:35 am

Hi, MartinCHarvey!
MartinCHarvey wrote:I get up to 12199113 isomorphisms with 11 givens, at which point, a small refactor to use less ram is necessary.
Save myself the computation time and disk space, is there a "Group theory for dummies" textbook which I might find useful?

Please, use more precise terminology. "Isomorphism" is some kind of transformation. But it seems you say about number of transformed objects (grids, puzzles, etc.). It looks like you are saying about essentially different patterns (9 x 9 binary matrices, where ones mark clue cells of 9 x 9 Sudoku puzzle).

Saying about textbook - I like textbook "An Introduction to the Theory of Groups" by Joseph J. Rotman (Springer series "Graduate Texts in Mathematics"). You should read chapters 1-3 only. Key theoretical concept - "Burnside's Lemma" (you can find it in Wikipedia too).

Serg
Serg
2018 Supporter
 
Posts: 858
Joined: 01 June 2010
Location: Russia

Re: Essentially different grids & group theory.

Postby MartinCHarvey » Mon Mar 15, 2021 2:12 pm

Serg wrote:Hi, MartinCHarvey!
Please, use more precise terminology.


Sorry, I'll learn the terminology and be more precise in future!

Serg wrote:"An Introduction to the Theory of Groups" by Joseph J. Rotman


Thank you, ordered, and I'll work my way through it.

MH.
MartinCHarvey
 
Posts: 15
Joined: 22 February 2021

Re: Essentially different grids & group theory.

Postby coloin » Wed Mar 17, 2021 6:40 pm

from number-of-non-equivalent-patterns-having-n-clues
Code: Select all
 0   1
 1   1
 2   5
 3   21
 4   109
 5   548
 6   3074
 7   16847
 8   92393
 9   489448
 10  2499689
 11  12199113
 12  56737622
 13  250632745
 14  1049547176
 15  4159131734
 16  15578997961
 17  55113078988
 18  184060159680
 19  580219975879
 20  1726649409444


Yes as Serg says It appears that you are counting patterns .....

If your patterns also had numbers ... they could be termed subpuzzles ... [having multiple solutions so not quite puzzles]...

A grid is a very loose term but the term solution grid is a better one - as in a complete 9*9 solution grid.
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Re: Essentially different grids & group theory.

Postby MartinCHarvey » Sun Aug 21, 2022 8:55 pm

Incidentally, I had a moment to put the 49 thousand known 17 clue sudokus through my grid checker, which determined that they had 33 thousand essentially different grids.

This would tentatively suggest that the 49 thousand known minimal sudokus are but the tip of the iceberg.
MartinCHarvey
 
Posts: 15
Joined: 22 February 2021

Re: Essentially different grids & group theory.

Postby denis_berthier » Mon Aug 22, 2022 3:12 am

MartinCHarvey wrote:Incidentally, I had a moment to put the 49 thousand known 17 clue sudokus through my grid checker, which determined that they had 33 thousand essentially different grids.
This would tentatively suggest that the 49 thousand known minimal sudokus are but the tip of the iceberg.

On pure abstract logical grounds, this is not what it may suggest. What it may suggest is only: these 33,000 complete grids have other minimals with more than 17 clues. Which wouldn't be a surprise, since most complete grids have lots of minimals with very different numbers of clues.
As for the 49,158 17-clue puzzles, extensive search has allowed to check (at least in 2 independent ways) that there are not more.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: Essentially different grids & group theory.

Postby Mathimagics » Mon Aug 22, 2022 8:39 am

The 49158 x 17-clue puzzles actually correspond to 46301 ED solution grids.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Essentially different grids & group theory.

Postby JPF » Mon Aug 22, 2022 10:12 am

MartinCHarvey wrote:Incidentally, I had a moment to put the 49 thousand known 17 clue sudokus through my grid checker, which determined that they had 33 thousand essentially different grids.

You are probably speaking about ED patterns.
There are 33,884 of them.
The most common patterns are with # of 17s :
Hidden Text: Show
Code: Select all
................11..1.11........11.1.1.......11.1........1.......11..1..1........   36
................11..1.11.........1.1.1.......11.1........1...1...1...1...1...1...   34
........1.....1.....1....11.....11....1.1.....1......1...11.....1.......11....1..   34
................11..1.11........11...1.......11.1........1....1..1...1...1..1....   33
................11..1.11........11...1.......11.1........1....1..1...1...1...1...   28
..............1..1.11....1.........1..1.....1..111........1..1..1.......11...1...   26
................11..1.11.........1...1......111.1........1...1...1...1...1...1...   25
................11..1.11......1....1..1...1...1...1......1..1...1.......11.1.....   23
..............1..1.11....1......1.....1...11.1...11......1..1..1........1.......1   22
..............1..1.11....1.......1.1....1.....11.1.........1.....1....1.1..1.1...   22
..............1..1.11....1.........1..1.....1..111........1..1..1.......11.1.....   20
................11..1.11.........1.....1......1.1....1...1.1..11........1.1....1.   19
..............1..1.11....1..............1.11.1.1..1.............1.11....1.....1.1   19
........1.....1....11.....1.......1......1.1...1.1........1.1.11........11.1.....   19
..............1..1.11....1............1...1.1..111........1..1..1.......11.1.....   19
..............1..1.11....1......1.....1...11.1...11......1...1.1........1.......1   18
........1.......11..1..1.......1.......1.11...11...1......1.....1...11..1........   18
........1.......11..1..1.........1......111..11............1.....1...1...1.1....1   18
........1.......1...1..1........1....1......111....1......1..1...1...1..1..1...1.   18
................11..1..1........11...1.......11......1....1.1.....11......11..1..   18
................11..1..1..1.....11...1....1..11...........1.......11......1...11.   17
........1.......1...1..1........11...1.......11....1......1......1...1.1..11.1...   17
........1.....1..1..1.1........1.11..1.......11.1........1.......1....1..1.....1.   17
................11..1.11........11...1.......11.1........1..1.1..1...1...1.......   16
........1.....1....11.....1.......1.....1..1...11........1..1.11........11...1...   15
..............1..1..1.1..1........1....11..1.11.............1.1.....1..1..1.1....   15
...........1..1..1.1..1..1.........1......1.1.1..1.......1........11..1.1.1......   15
........1.......11..1..1.........1......1......11..1...1...11..1..1.....11.......   15
................11..1.11........11.1..1.......1.1........1.....1.....1..11.1.....   14
........1.......11....11........11....1........11........1...11.1.......11...1...   14
........1.....1.....1....11......1.....11....11....1......1...1.1........1...11..   14
..............1.11..111..........1...1.......11...1........1..1..1...1...1..1....   14
................11..1.11.........1.1.1.......11...1......1.......1...1..1.11.....   14
..............1.11..1.11.......1.1.1.1.......11.1........1.......1...1..1........   14
........1.....1..1..1.1..........11......1....11..1......11..1..1.......1...1....   14
..............1.11..1.11.........1...1.......11.1........1....1..1...1...1..1....   13
................11..1..1.........1.......11..11..1........1......1...1.1.1.11....   13
........1........1..1.11..........1.....11.1..1............111..1.......11.1.....   13
................11..1.11...............1.1..1..1...1...1...1...1...1.1..11.......   13
........1.....1....11.....1......11.....1......111.......11.....1.......11.....1.   13
................11..1.11.........1.....1......1.1.1......1.1..1..1......1.1...1..   13
...........1..1..1.1..1..1.........1......1.1.1.1............1....11..1.1.1......   13
........1.....1..1..1.1..........11...1....1..1...1.......1..1..1.......11.1.....   13
................11..1..1.........1.1....1.......111........11...1....1..11.1.....   13
........1.......11..1..1........1....1......11...11......1..1....1...1...1.1.....   13
................11..1.11.........1.1...1........111........11...1.......11.....1.   13
..............1..1..1.1..1.........1..1...11...111.......1...1..1.......11.......   13
..............1..1..1.1..1.........1..1.1.....1....1.1.......1....11..1.11.......   12
................11..1.11........1......1.11....1...1......1.....1......111..1....   12
..............1..1.11....1........1.1....1...1...1.......1..1....1.....11..1.1...   12
..............1..1.11....1.........1..1.....1..111........1..1..1...1...11.......   12
................11..1.11........11.1.1.......11..1.......1.......11..1..1........   12
........1.....1.....1....11....1........1...111..........1.1....1....1..1.....11.   12
..............1..1..1.1..1.........1.....11.1..1.1...........1....11..1.11.......   12
........1.......11....11........1.....1.......11...1......1.1..1..1.....1.1....1.   12
........1.......11..1.11...........1.1.1.1...1.1..........1........111...1.......   12
........1.....1.....1....11.....11....1.1.....1......1...11......1......11....1..   12
........1.....1.....1....11......1...1....1...1.11........1...1..1......1.1.1....   12
........1.....1.....1....11.....11....1.1.....1......1...11....1........11....1..   12
........1.......11....11........111...1.......11.1.......1.....1........11....1..   12
........1.....1.....1....11......1.....11....11....1......1...1.1.......11...1...   11
................11..1.11..............1..11...1.1.1.......1.1.1...1.....11.......   11
........1.......11..1..1.......1.......1..1.1.11...1......1.....1...11..1........   11
..............1..1.11....1.......1..1........1...11......1...1...1.....11..1.1...   11
..............1..1....1..1.........1..1.1.....1.1....1......11..1.....1.11.1.....   11
...............111..1.11...........1.1.......11.1........1...1...1.....1.1...1...   11
........1.......11..1..1........11...1.......11...........1.1....1...1...1.11....   11
........1.......11....11.........1....1..11...1.1..........11.11........11.......   11
........1.....1..1..1.1...........1...1....1..1...1.......1.....1....1.11..11....   11
..............1..1.11....1.......11.1........1...11........1......11....1.1.....1   11
................11..1.11...............1....1..11..1...1...1...1...1.1..11.......   11
........1.....1..1..1..1..........1......11..11..1........1..1...1.......1.11....   11
................11..1..1........1.......111..11......1.....11...1.......11.1.....   11
................11..1..1........11...1......111...........1.1.....11......11..1..   11
................11..1.11...........1.1.......1....11.....1...1...1...1...1.1.1...   11
................11....11.........1....1.....1.111........1.1..11........11....1..   11
..............1..1.11....1........1.1....1...1...1........1.......11.1..1.1.....1   11
........1.....1.....1....11.....11....1.1.....1.....1.....1......11.....11....1..   11
................11..1..1........11...1.......11....1......1......1...1.1.1.11....   11
........1.......11..1..1........11...1....1..11...........1.......11......11..1..   11
................11..1.11..1......1...1.......11.1........1....1..1...1...1...1...   11
........1.....1.....1....11.....11......1.1...11.........1....11.....1..1..1.....   10
..............1.11..1.11.......1.1.1.1.......11..........1.......11..1..1........   10
..............1..1.11....1.........1..111....11......1....1..1.1........1....1...   10
.................1..1..1.1..............11.1..1.1....1.....111..1.......11.1.....   10
................11..1.11.........1...11......11.1........1....1..1...1...1...1...   10
........1.....1..1..1.1...........1...1...1...1...1.......1.....1....1.11..11....   10
..............1..1.11....1........1.......11.1.1..1......11....1.......11...1....   10
..............1.11..1.11........11.1.1.......11.1........1.......1...1..1........   10
........1........1..1..1........1.1..1..1....11.....1....1.......1...11..1.1.....   10
................11..1.11........1......1.1..1..1...1......1.1.1.1.......11.......   10
..............1..1..1....1.......1.1...11.....1..1.......11..1.1........11......1   10
................11..1.11........11...1.......11.1........1....1..1.1.1...1.......   10
................11..1..1..1.....11...1......111...........1.......11......1...1.1   10
..............1..1..1....11...........111.....1....1.......1.......111..1.1.....1   10
..............1..1..1.1..1........1....11..1.11.............1.1..1.1.....1......1   10
..............1..1.11....1.......1..1....1...1...1.......1...1...1...1..1..1.1...   10
........1.....1..1..1.1...........1.....1..1.11..........11.1....1....1..1.1.....   10
..............1..1..1.1..1.........1..111.....11...1.....1...1..1.......11.......   10
..............1..1.11....1........1.1........1...11......1..1....1.....11..1.1...   10
..............1..1..1.1..1.........1....1.1....11............1....1.1.1.11...1...   10
........1.......11..1..1.........1.1....1......1111........11...1.......11.......   10
........1.......1...1.11........1......1.11...11..........1......1.1.1..1.......1   10
........1.......11..1..1.........1......111...1..1.......11...1..1......1.1......   10
..............1..1.11....1........1.1....1...1.1..........1.......11...111......1   10
................11..1.11........1.....1...1...1.1....1....1.1...1.......11.1.....   10
................11..1.11.........1...1.......11.1........1....1..1..11...1..1....   10
................11..1.11...............1....1.11...1.......111.1........11.1.....   10
................11..1.11.................11.111.1........1...1...1...1...1..1....   10
................11..1.11...............1.1..1.11.1..........1....11.....1..11....   10
..............1.11.11.1............1......1..1..1.1.......1.1....1..1...1......1.   10
................11..1.11.........1.....1......1.1.1......1....1..1.1.1..1.1......   10
................11..1.11.............1......11....11.....1...1...1...1...1.11....   10
........1.......11..1..1........11...1.......11...........1.1.....11......11...1.   10

denis_berthier wrote:As for the 49,158 17-clue puzzles, extensive search has allowed to check (at least in 2 independent ways) that there are not more.

To my knowledge, that is the first exhaustive search; it has to be confirmed in some way.
The 49,158 17s were already known, but found "randomly", that is to say without guarantee of completeness.

JPF
JPF
2017 Supporter
 
Posts: 6123
Joined: 06 December 2005
Location: Paris, France

Re: Essentially different grids & group theory.

Postby MartinCHarvey » Mon Aug 22, 2022 6:12 pm

Mathimagics wrote:The 49158 x 17-clue puzzles actually correspond to 46301 ED solution grids.


Oh jeez - I might have to do a bit of bughunting then.
MartinCHarvey
 
Posts: 15
Joined: 22 February 2021

Re: Essentially different grids & group theory.

Postby MartinCHarvey » Mon Aug 22, 2022 6:21 pm

Mathimagics wrote:The 49158 x 17-clue puzzles actually correspond to 46301 ED solution grids.


Ahha. Hang on - we're talking about different things. That's 46301 essentially different completed solution grids.

I'm saying those 49158 x 17 clue puzzles, with numbers removed, come from 33,877 unique initial placement configurations.

And the 17 clue list I have only has 49151 in it ...
MartinCHarvey
 
Posts: 15
Joined: 22 February 2021

Re: Essentially different grids & group theory.

Postby MartinCHarvey » Mon Aug 22, 2022 6:23 pm

denis_berthier wrote:As for the 49,158 17-clue puzzles, extensive search has allowed to check (at least in 2 independent ways) that there are not more.


Oh? This has changed since I last showed an interest! Who showed that there are no more than that?

MH.
MartinCHarvey
 
Posts: 15
Joined: 22 February 2021

Re: Essentially different grids & group theory.

Postby MartinCHarvey » Mon Aug 22, 2022 6:39 pm

JPF wrote:You are probably speaking about ED patterns.
There are 33,884 of them.
JPF


Ah, yes, when I add the few more solutions to my incomplete list, my numbers agree with yours. OK, makes sense.
MartinCHarvey
 
Posts: 15
Joined: 22 February 2021

Re: Essentially different grids & group theory.

Postby champagne » Mon Aug 22, 2022 7:06 pm

MartinCHarvey wrote:
denis_berthier wrote:As for the 49,158 17-clue puzzles, extensive search has allowed to check (at least in 2 independent ways) that there are not more.


Oh? This has changed since I last showed an interest! Who showed that there are no more than that?

MH.


see here
champagne
2017 Supporter
 
Posts: 7336
Joined: 02 August 2007
Location: France Brittany


Return to Software