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)

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)

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)

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)

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)

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)

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

Revert on minimal number of different clues

@Dobrichev would you please elaborate on why this aspect, concerning vanilla Sudoku, did violate the scope of the article in your opinion? 90.167.51.170 (talk) 16:33, 24 November 2024 (UTC)

Sudoku game requires a puzzle to have unique solution.

You can compose a multiple-solution puzzle with less than 8 differnt clues so that all solutions can be transformed to each other using the validity preserving transformations. At least this was my reading of your addition.

OK, but this is a Sudoku extension. The game has hundreds more or less popular extensions and adding information for them polutes the article. For example, we know a 16-given puzzle which is valid according to this extension. A more brutal example is the comparison of Megaclue to Zettaclue here. Do you think such information is worth adding?

The touching point is that the minimal number of different clues for vanilla Sudoku is 8 and I am OK such information to exist. (Note that some editors are very strict and already erased much content not referenced by reliable sources. Validity preserving transformations definition has been erased too.) Dobrichev (talk) 16:34, 25 November 2024 (UTC)

Also, additions will meet WP:NOR and WP:RS - those are two of Wikipedia's core content policies. Note in particular that the stackexhcange link used as a citation isn't a usable source for Wikipedia. MrOllie (talk) 16:45, 25 November 2024 (UTC)

Actually other rules allow for many exceptions. @MrOllie, I wonder if а major cleaning of an article based solely on a single keyword, leaving the original research intact, improves its quality. Dobrichev (talk) 21:38, 25 November 2024 (UTC)

WP:NOR is one of Wikipedia's core policies. Wikipedia:Ignore all rules means that we should follow a policy's spirit and not its letter - not set it aside entirely. Removing material which is completely out of step with this project's goal of writing a verifiable encyclopedia based on solid sources absolutely does improve quality. - MrOllie (talk) 22:05, 25 November 2024 (UTC)

The reference to math.stackexchange pointed to an example of a 5-different-clue puzzle with a unique solution pattern. It was presented as de-facto proof that such thing exists and is in no way related to the site's reputation. 90.167.42.120 (talk) 20:43, 28 November 2024 (UTC)

Our article's introduction reads

Mathematics can be used to study Sudoku puzzles to answer questions such as "How many filled Sudoku grids are there?", "What is the minimal number of clues in a valid puzzle?" and "In what ways can Sudoku grids be symmetric?" through the use of combinatorics and group theory.

I still think that the question "what is the minimal number of different clues that lead to a single solution?" is a perfect fit here. Especially since neither combinatorics nor group theory alone forbid me to regard a single possible distribution of symbols as being satisfyingly unique.

Mustn't one at least accept that there is a strong distinction between puzzles that really have multiple, entirely different looking solutions and those 'underdetermined' ones who dont?

I have seen this question appear often enough to believe that the persons who put it up, share the same view as described. And isn't it an interesting question? For me at least, it came as a genuine surprise that puzzles with only 5 different clues had been discovered. Plus, I'am feeling sorry for all these people been put away with a snorty '8 of course'.

Definitions of uniqueness and properness must be unanimous in all circumstances. I don't intend to question them in any way. Still I think its permissable to venture from the school book when an interesting new characteristic lies at hand and if the deviation gets clearly stated. 90.167.42.120 (talk) 20:43, 28 November 2024 (UTC)