Number of possible 16x16 sudoku grids?

Everything about Sudoku that doesn't fit in one of the other sections

Number of possible 16x16 sudoku grids?

Postby yes_maybe » Thu Jan 09, 2020 2:26 pm

Has anyone found the exact number of possible 16x16 sudoku grids yet? Not according to wikipedia and OEIS, but that might have changed in the 15 (probably) years since they were last updated. I have also not been able to find anyone doing it online. I know there's a very good estimation out there of around 10^98 though.
yes_maybe
 
Posts: 3
Joined: 09 January 2020

Re: Number of possible 16x16 sudoku grids?

Postby Mathimagics » Fri Jan 10, 2020 12:39 pm

Not yet! (if anybody here had done so we would certainly have updated the wikipedia pages).

The methodology would, I expect, be along similar lines to the original Sudoku 9x9 case. See here for a relatively recent discussion with some useful links.

The Burnside's Lemma approach would seem to be only way forward, since it does not require enumeration of all the grids, but even with this method the numbers are still daunting. This was the method used to count the ED Sudoku 9x9 grids.

To begin with we would need to identify equivalence (conjugacy) classes. The only software for this is a group-theory package like GAP. The number of VPT's (Validity Preserving Transformations) involved, is, I believe, 2 x (12 ^ 10) = 123,834,728,448 for 16x16 Sudoku, compared with just 2 x 6^8 = 3,359,232 for 9x9 Sudoku.

With a group of that size, it's highly unlikely that any desktop PC is going to be able to accomplish even this first step! Some serious architecture would need to be thrown at the problem ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1532
Joined: 27 May 2015
Location: Canberra

Re: Number of possible 16x16 sudoku grids?

Postby Serg » Fri Jan 10, 2020 10:47 pm

Hi, Mathimagics!
I think, yes_maybe says not about essentially different 16 x 16 Sudoku solution grids, but about (simply) different 16 x 16 Sudoku solution grids. It were Bertram Felgenhauer and Frazer Jarvis, who published well-known number of different 9 x 9 Sudokus - 670903752021072936960 (6.671 × 10^21 appox.). Felgenhauer and Frazer Jarvis used as they said "brute force" method to count all 9 x 9 Sudokus, so their method cannot be used for 16 x 16 Sudoku counting. 10^98 is an estimate of different 16 x 16 grids, published at "Mathematics of Sudoku" page of Wikipedia.

As fas as I know, nobody at this forum ever discussed 16 x 16 Sudoku solution grids enumeration.

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

Re: Number of possible 16x16 sudoku grids?

Postby Mathimagics » Sat Jan 11, 2020 7:40 am

Hi Serg,

Serg wrote:As fas as I know, nobody at this forum ever discussed 16 x 16 Sudoku solution grids enumeration.


And we can see why!

For 16x16 Sudoku, assuming that the "different grids" estimate of 5.9584 x 10^98 is a good one, we can divide this by 12! (relabellings) x (2 x 12^10) (VPT's) and get a rough estimate of the number of ED grids, which is 2.3 x 10^74.

The computational challenges to obtaining exact counts (ED or total grids) are plain to see ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1532
Joined: 27 May 2015
Location: Canberra

Re: Number of possible 16x16 sudoku grids?

Postby coloin » Sun Jan 12, 2020 9:08 pm

It’s been done
Paxmandaddy and kjflp did it
In spades
I’m on holiday in Tenerife can’t find the link !!!!
coloin
 
Posts: 1900
Joined: 05 May 2005

Re: Number of possible 16x16 sudoku grids?

Postby yes_maybe » Mon Jan 13, 2020 12:05 am

Well, thanks for all that. I'm aware of the estimation and the insane computing power required... However, according to Felgenhauer and Jarvis,
Although our original method required a couple of hours of computer time, Guenter Stertenbrink and Kjell Fredrik Pettersen have subsequently developed a method which completes the entire calculation in less than a second!

and that's on a 2006 computer too... Maybe enumeration of 4x4 sudoku grids be doable on a modern computer in a week now?
(I've also found no mention of this method online anywhere except that paper and wikipedia, which did not cite a source)
yes_maybe
 
Posts: 3
Joined: 09 January 2020

Re: Number of possible 16x16 sudoku grids?

Postby yes_maybe » Mon Jan 13, 2020 1:04 am

Okay, I found the fast counting method... http://forum.enjoysudoku.com/fast-3x3-counting-t2995.html

While this does seem quick, I seem to have underestimated the increase in the amount of computation required from 9x9 to 16x16 way, way too much. I blame scientific notation for making giant numbers (almost a googol) seem insignificant...
I guess that's why no one has done this in 15 years.
yes_maybe
 
Posts: 3
Joined: 09 January 2020

Re: Number of possible 16x16 sudoku grids?

Postby Serg » Mon Jan 13, 2020 8:43 am

Hi, coloin!
coloin wrote:It’s been done
Paxmandaddy and kjflp did it
In spades
I’m on holiday in Tenerife can’t find the link !!!!

Do you mean the link http://forum.enjoysudoku.com/su-doku-s-maths-t44-525.html#p15909?
But PatmaxDaddy posted there an estimate only (formula) for the number of 16 x 16 Sudoku solution grids.

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

Re: Number of possible 16x16 sudoku grids?

Postby Mathimagics » Mon Jan 13, 2020 11:08 am

coloin wrote:Paxmandaddy and kjflp did it


My friend has let sunny (and hopefully, for him, suitably windy) Tenerife go to his head :lol:

Thanks to Serg for correctly identifying the correct name of the contributor (PatmaxDaddy) and the link.

Exact counts require grid enumeration, of some kind, and the numbers are simply too huge for this to be feasible!
User avatar
Mathimagics
2017 Supporter
 
Posts: 1532
Joined: 27 May 2015
Location: Canberra

Re: Number of possible 16x16 sudoku grids?

Postby coloin » Sat Jan 18, 2020 4:41 pm

Mathimagics wrote: counts require grid enumeration, of some kind, and the numbers are simply too huge for this to be feasible!

Yes , I apologize for my error, and yes the numbers are probably bigger than too big .

Its not as if we can repeat the 9*9 simulation estimate. [by averaging the no of solutions to a selection of random B1B5B9 and multiplying by 9!^3]

An attempt to do this for the 16x16 with box1,box6,box11,box16 filled in [16!]^4 = 1.9e53 , this would mean that each of these has ~2e45 solutions

Perhaps we could attempt to count the solutions of a completed B1/B6/B11/B16 plus a template of ? clues in the other empty boxes.

At least we could get some additional confirmation of the 5e98 number perhaps
coloin
 
Posts: 1900
Joined: 05 May 2005


Return to General