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 ...
Essentially different grids & group theory.
13 posts
• Page 1 of 1
Essentially different grids & group theory.
by MartinCHarvey » Sun Mar 14, 2021 7:58 pm
- MartinCHarvey
- Posts: 15
- Joined: 22 February 2021
Re: Essentially different grids & group theory.
by Serg » Mon Mar 15, 2021 7:35 am
Hi, MartinCHarvey!
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
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: 890
- Joined: 01 June 2010
- Location: Russia
Re: Essentially different grids & group theory.
by 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.
by coloin » Wed Mar 17, 2021 6:40 pm
from number-of-non-equivalent-patterns-having-n-clues
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.
- 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: 2497
- Joined: 05 May 2005
- Location: Devon
Re: Essentially different grids & group theory.
by 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.
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.
by 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: 4214
- Joined: 19 June 2007
- Location: Paris
Re: Essentially different grids & group theory.
by Mathimagics » Mon Aug 22, 2022 8:39 am
The 49158 x 17-clue puzzles actually correspond to 46301 ED solution grids.
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: Essentially different grids & group theory.
by 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
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: 6139
- Joined: 06 December 2005
- Location: Paris, France
Re: Essentially different grids & group theory.
by 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.
by 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.
by 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.
by 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.
by 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: 7458
- Joined: 02 August 2007
- Location: France Brittany
13 posts
• Page 1 of 1
