Talk:Mathematics of Sudoku

New Grid-Counting Method (25 Jan 2006)

Just a quick note that Kjell Fredrik Pettersen has invented a new method for calculating the number of 3x3 Sudokus which is competitive with, and may turn out to be better than, the "band generators" method outlined below. — Preceding unsigned comment added by 81.159.21.159 (talk) 22:03, 25 January 2006 (UTC)[reply]

Overview of Felgenhauer/Jarvis Calculation

I don't think it's appropriate to have a long discussion of a now outdated enumeration method in what is supposed to be a quite general and wide-reaching web page. It might be okay to outline the current fastest-known method (that of Stertenbrink[1] and Pettersen[2][3]), since that is not currently documented elsewhere. But anything more detailed than an outline would, IMHO, unbalance the article. Why don't you ask Kjell Fredrik ("kjellfp") to contribute a page or paper of his own? --Ed.

FWIW, here's my take on the current best method (as of February 2006).

-=-=-=-=-

We work with what you might call band generators. A band generator is the result of taking a valid Sudoku band and permuting the contents of each minicolumn so that smaller values are stacked above larger values. Each band generator, $g$ , represents a collection of some ${\mbox{Bands}}(g)$ valid Sudoku bands (typically ~200); though the generator itself is emphatically not a valid band.

We loop over all compatible generators $(g_{1},g_{2},g_{3})$ representing the top, middle and bottom bands of the Sudoku grid. Three generators are compatible if, when placed into the grid, no column contains a repeated value. Then the number of Sudoku grids is easily seen to be $N=\sum _{g_{1}}{\mbox{Bands}}(g_{1})\sum _{g_{2},g_{3}{\mbox{ compat with }}g_{1}}{\mbox{Bands}}(g_{2})\times {\mbox{Bands}}(g_{3})$

The calculation is made fast by partitioning the $1680^{3}=4741632000$ band generators into just 44 equivalence classes defined by the orbits of the group action generated by the following operations:

relabelling the digits
permuting the order of the 3x3 boxes within the band generator
permuting the order of the minicolumns within the 3x3 boxes

Each equivalence class has a unique value of ${\mbox{Bands}}(g)$ and a unique number of completions to a full grid (the $g_{2},g_{3}$ part of the sum above). So, with the following terminology ...

B[c] is the unique value of ${\mbox{Bands}}(\cdot )$ for class c
S[c] is the number of band generators in class c (i.e. the size of the class)
G[c] is any band generator in class c
${\mbox{Class}}(g)$ maps a band generator, g, to its class number, 1 to 44

... we have: $N=\sum _{c=1}^{44}{\mbox{S}}[c]\times {\mbox{B}}[c]\sum _{g_{2},g_{3}{\mbox{ compat with G}}[c]}{\mbox{B}}[{\mbox{Class}}(g_{2})]\times {\mbox{B}}[{\mbox{Class}}(g_{3})]$

Whilst the symbolic form of the calculation is simple enough, the full power of this method requires very careful coding to allow the various loops and lookups to execute efficiently. The best implementations can finish the job in substantially less than one second.

-=-=-=-=-

Hope that helps ...

Set terse vs. Accessible to all

Ed, (I assume Russell) thanks for the comments and write-up, which certainly does help. I'm split between trying to keep the article terse and abstract (for math folks) and trying to make it accessable for 'recreational mathematicians' with less formal background. I realized it was long when I put it in. The Felgenhauer/Jarvis approach was so straightforward and an excellent segue into other math concepts, that I decided to put it in and see what the wiki concensus was. I had started writing it up before the kjell/dukuso approach solidified.

I'm also trying to provide enough 'readable' material so that people joining the (Sudoku Math's) discussion will have somewhere to look/be directed when they're interested in how we got where we are. I hoping that pushing the bulky detail descriptions down a level or two in the headings will allow us to address both audiences. If not, there's always wikibooks.

I was planning to cover the band generation approach, after developing the Unique Solutions Nr. with pointers to Burnside, which was part of the reason for introducing eq.classes for the total Sudoku count. The F/J description may demote to an historical reflection at that point. I will be writing more,

comments always welcome. -- LarryLACa 02:03, 22 November 2005 (UTC)[reply]

I think I still favour a terse description on this page (which I had originally wanted to be little more than a summary of results) with more detailed write-ups of enumeration and Burnside methods elsewhere. But I'm not going to argue this very hard, and I do like your funky graphics! Good luck, Ed. (Russell)

I'm split between trying to keep the article terse and abstract (for math folks) and trying to make it accessable for 'recreational mathematicians' with less formal background. Wikipedia articles are explicitly not "written for math folks" as the audience, so that should settle any debate in your head.207.237.14.175 (talk) 18:33, 30 March 2024 (UTC)[reply]

links to crashed sudoku.com

Links on this page to the crashed Players' Forums (original www.sudoku.com) updated to reconstructed Players' Forums (forum.enjoysudoku.com. — Preceding unsigned comment added by Ronk9x9 (talk • contribs) 16:31, 27 August 2010 (UTC)[reply]

Symmetries

In the introduction, it states that "there are 26 types of symmetry, but they can only be found in abut 0.005% of all filled grids". No source is given for this, and it is not mentioned again. What does this mean? What are the "26 types" of symmetry, and how was it determined that only .005% of filled grids are one of these 26 types? — Preceding unsigned comment added by 24.62.225.169 (talk) 12:42, 4 October 2022 (UTC)[reply]

Exact results and estimates for larger grids

The main article statement “No exact results are known for Sudokus larger than the classical 9×9 grid” is misleading. Exact results for some larger grids have been reported online in various places, including older versions of the main article, but do not meet Wikipedia’s reliable sourcing requirements. This is particularly true of 12x12 grids with 4x3 boxes, where independent verification of the original result is extensively documented in a GitHub repository.

The main article statement, “there are estimates which are believed to be fairly accurate” is true. However, these estimates no more meet Wikipedia’s reliable sourcing requirements than the exact results that the main article claims are not known.

It is reasonable for Wikipedia to apply whatever reliable sourcing requirements it deems appropriate, but perhaps this should not result in misleading statements being published in main articles.

A true main article statement might read, “Exact results have been reported for some Sudokus larger than the classical 9×9 grid, as have been estimates for larger grids that are believed to be fairly accurate, but these results are self-published and do not meet Wikipedia’s reliable sourcing requirements.” PatmaxDaddy (talk) 18:36, 5 December 2023 (UTC)[reply]

I removed the statement since it was unsourced, thanks for pointing that out. MrOllie (talk) 18:39, 5 December 2023 (UTC)[reply]