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.

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)

latin squares

Shouldn't it be RxR (and SxS) in the intro instead of the Rx1? --MarSch 13:18, 20 October 2005 (UTC)

Updated the wording to make this clearer. For regions of size 1 (either row or column) the region constraint overlaps with the row or column constraint and disappears through redundancy. What's left are the Latin Square row/column contraints: that each number appear once in each row/column.LarryLACa 03:01, 25 October 2005 (UTC)

it is clearer, but can Latin squares be non-square? Can a RxC sudoku with R is not C be a Latin square?--MarSch 10:00, 25 October 2005 (UTC)

Since every row and col must contain each digit exactly once, Latin squares and Sudoku must be square. The regions of Sudoku like puzzles are not constrained to be rectangular. See Go Duko which uses pentomino shaped regions. [4] -- LarryLACa 17:59, 7 November 2005 (UTC)

Okay, I think I finally understand what this sentence is saying:

A rectangular Sudoku is one with rectangular regions of row-column dimension RxC. For Rx1 (and 1xC), i.e. where the region is a row or column, Sudoku becomes a Latin square.

Isn't it so that in Sudoku rows and columns already must contain one of each number. That is a Sudoku without regions or with one big square region is a Latin square. The other way around: a Sudoku is a Latin square which may also contain some regions with the same number of squares as the sides of the Latin square, such that each region also contains one of each number, just like each row and each column.--MarSch 12:25, 8 November 2005 (UTC)

Template:Sudoku 9x9 grid available

Sudoku 9x9

5 3   6       9 8	7   1 9 5	6
8     4     7	6   8   3   2	3     1     6
6	4 1 9   8	2 8       5   7 9

I've created a template for displaying Sudoku grids/puzzles Template:Sudoku 9x9 grid. This example is based on the puzzle shown on the Sudoku main page, with some arbitrary colors added.

To see the example's parameter list, edit this topic. The diagram can float left or right, cellsize is variable, background colors can be set for the diagram, boxes or individual cells. For usage details see Template_talk:Sudoku 9x9 grid. -- LarryLACa 09:02, 8 November 2005 (UTC)

To Do

Style

In the main Sudoku article, Sudoku is italicized, as it's a proper name. Here it's not. Should follow lead article style? -- LarryLACa 22:09, 15 November 2005 (UTC)

;list bolding?

I had been (mis)using this format

;line1 citation
;line2 citation

e.g.

line1 citation

line2 citation

to produce, what on my browser (IE V6 SP1 ) looks like
line1 citation
line2 citation

User:Shreevatsa removed the leading ';' with the comment 'remove bolding'. On my browser, the lines now run together, i.e..
line1 citation line2 citation

I now see (in m:Help:Editing) that the form ';term:def' is intended for use in definition lists. My guess is, on some browsers, the ';' causes the first part to be bolded.

Capitalization

Beware: although the Wikipedia general convention for links and section titles is lower case, there are times when the item (and link) is also a formal noun, as in 'Group Theory', or 'Combinatorics', where capitalization should be retained, since the term is a formal noun.

Thanks User:Michael_Hardy for fixing these 11/28. I'll go with the general consensus. LarryLACa 01:41, 1 December 2005 (UTC)

Math notation

In the RxC refs, it is not entirely appropriate to use ×, since no multiplication is implied, but it probably looks better with times.

Using × is preferable to &mdot;. The times symbol is not required for expressions like 9! 2222.

Since the 3^3 and e21 notation is common elsewhere (in the discussion forums), but obviously not pretty, it will probably creep in here occasionally.

Again, thanks User:Michael_Hardy for fixing these 11/28. I'll go with the general consensus. LarryLACa 01:41, 1 December 2005 (UTC)

A Step Back (5 Mar 06)

Here is yet another method that relies on simplicity. To avoid confusion, we’ll call the larger blocks "blocks" and their subsidiaries "squares". Each will be referred to as the numbers on a touchtone phone, with 1 at top left and 9 at bottom right. We’ll let a simple program and a scientific calculator do all the busy work for us.

We begin with 3 blocks (1, 5, & 9) that can legally have their total allotted combinations without affecting each other, since they share no axes. Each of these blocks has 9! possibilities (9*8*7*6… or 362,880). Thus, our calculation begins with (9!^3). (I’ve used parenthesis to make our final equation easier to read.)

Blocks 2 and 4 function alike, yet their possible combinations are independent of each other, so we’ll solve block 2 and factor its answer into our equation twice (once for block 2 and once for block 4). These will be our most difficult blocks, so we’ll use our simple program. Our program goes through all 362,880 combinations and tells us how many follow all rules for block 2 given a set combination for blocks 1 and 5. Such a program takes only minutes to write and less time to run, and tells us there are 448 legal combinations. Factor this into our equation twice and we get (9!^3)*(448^2).

Blocks 6 and 8 will be much easier. They also function alike yet independently. Each number has two possible locations. Block 6 has two other blocks solved along its horizontal axis and one vertically, so selecting any number in a single row forces the other two numbers in that row. This gives us 2 possibilities for each row and 3 rows for 8 total. Block 8 has 2 possibilities for each column and 3 columns for another total 8. Factor these into our equation to get (9!^3)*(448^2)*(8^2).

Blocks 3 and 7 have only a single combination, being determined by 2 blocks along each axis.

Using this method gives us (9!^3)*(448^2)*(8^2) or (9!^3)*(7^2)*(2^18) legal Sudoku combinations. That's 613,797,479,357,802,872,832,000 with our scientific calculator (over 613 sextillion).

Explanation of the Program / Block 2

Whether working with rows or columns, this will function the same. Start with the top row. Each of the 6 numbers appears in 9 normal combinations of 3 squares in the row. Since each square has 4 possible values, 4*9=36. These are normal combinations because each of them allows for 6 combinations in the next row and 2 in the last. 36*6*2=432.

Now, each number in the top row also appears in two abnormal combinations. These are abnormal because all three digits in the row will be the same as all three digits in either of the other rows of the adjacent block. This forces both the other rows in this block to function like the bottom row beneath a normal first row combination. Both the other rows will only have 2 combinations, with 4 total abnormal combinations of the top row, for 2*2*4=16.

432+16=448, so we have our 448 combinations for block 2.

--Weaselgrip 05:38, 6 March 2006 (UTC)

The number of solutions was calculated 5/05 as ~6.67e21, and has been confirmed independently numerous times. See the main article. The Weaselgrip value of 6.13e23 reflects a mostly valid approach but does not reflect all the constraints. -- LarryLACa 04:55, 16 March 2006 (UTC)

Bottom of List, Please insert comments above

This topic added to facilitate adding new topics at end -- LarryLACa 22:09, 15 November 2005 (UTC)

Numbers Not Numerically Significant

As with a Latin Square (other Latin Squares) the numbers (numerals) are not numerically significant. Letters A,B,C,D,E,F,G,H,I could be used, for instance. The symbols do not need a collating sequence for the puzzle to be solvable. E.g. Perhaps the elements of { . O - | = + X [ ] } could be used for 9x9/3x3, or arbitratry shapes or pictures. In "classic" Sudoku the collating sequence helps the solver enumerate their givens and possiblities, but without a natural collating sequence, you could just choose one. (The sequence in my set is reasonably natural; ordering by the number of lines, with some arbitration). In short, should the fact the numbers/numerals are not numerically significantly be mentioned very close to the beginning of this article? Or perhaps around about the map colouring suggestion?--SportWagon 16:47, 12 October 2006 (UTC)

Okay, I see that point is mentioned fairly early in the main Sudoku article. I'll contemplate expectations that the reader has digested that before reading this, etc. before perhaps reiterating early but briefly in this article.--SportWagon 19:11, 12 October 2006 (UTC)

I am happy to see my intuition confirmed in Sudoku preserving symmetries however.--SportWagon 16:47, 12 October 2006 (UTC)

I modified the lead paragraph appropriately. It is a little unweildy for those unfamiliar with Mathematics of Sets, however.--SportWagon 21:50, 13 October 2006 (UTC)

Sum number place ("Killer Sudoku") describes variants which do require the symbols to be numbers. Perhaps that should be noted? On a related note Relabeling symbols (9!) in Sudoku preserving symmetries uses the word symbols, whereas numbers is used in most places in the article. Having received no feedback on my other comments, I will not change/supplement numbers to/with symbols throughout the article. At least not yet.--SportWagon 21:50, 13 October 2006 (UTC)

Sudoku Preserving Symmetries

Can someone explain how row permutations within a band preserve sudoku validity? --18.209.1.137 16:34, 20 October 2006 (UTC)

I think it's obvious to most people with mathematical background, so don't expect the proof to be complicated. It simplicity can be convincing, but, yes, it did make me wonder if I was thinking too simply. Anyway... The rows remain valid because you don't change them. The columns remain valid because you don't change the elements they contain (but merely rearrange their order), and similarly for the three block regions in the band. The permutations must be constrained within one band, however. (Otherwise, you would be switching elements between different block regions). Alternatively, perhaps try to explain how such permutations would break the sudoku validity, and you won't be able to explain such.--SportWagon 18:57, 20 October 2006 (UTC)

Eventually I realized that the confusion might come from thinking that a "row permutation" might mean "permutations of the elements within the row", which would not be preserving. But, "Within a band", does help suggest that complete rows are being swapped, without being changed. I can't think of a succinct improvement to the wording to remove the possible confusion.--SportWagon 18:11, 23 October 2006 (UTC)

And, being succinct is certainly not a strong point of mine, in any case.--SportWagon 21:22, 8 November 2006 (UTC)

perhaps try to explain how such permutations would break the sudoku validity, and you won't be able to explain such. - Though you couldn't call that a proof :) --CompuChip 19:53, 18 December 2006 (UTC)

Add Something about Set Analysis? Here, or in Main Article?

Neither the main Sudoku article nor this one seem to say much about set analysis, which can (and should?) be used to solve Sudoku? Initial constraints restrict values in obvious ways. (Elimination of possible values for cells). Anytime a the union of all sets of values for some subset of some region has the same number of elements as the number of elements in that subset, that creates an additional constraint--specifically, the elements of that set cannot occur elsewhere in the region. In fact, the initial constraints are a specific case of that type of constraint. The subset size is one, and the list of possible values is one. It seems to me, this is how one solves Sudoku. (Well, you combine these constraints on value with constraints on position; if only one cell in a region has a particular value in its list of remaining possible values, that cell must have that value). Trivial to Mathematicians, but perhaps complex for the general public (what used to be called a "lay person"). (And then one also needs to avoid making mistakes!) Does such a discussion belong in wikipedia? Can we find sources for such?--SportWagon 19:15, 27 October 2006 (UTC)

Number of problems

Anyone knows anything about the number of proper problems? (A presumably extremely hard problem) 129.67.2.79 00:31, 2 December 2006 (UTC)

This is easy to do by simulation if you have an unbiased grid generator. I have produced one such generator myself, from which I got the 95% confidence interval (5.88e45,5.95e45) for the number of proper puzzles. Reference: here. 81.159.212.3 19:20, 10 January 2007 (UTC)

Sudoku is really NP-complete?

In the article there is the sentence "The general problem of solving Sudoku puzzles on n2 × n2 boards of n × n blocks is known to be NP-complete [3]."

The reference is in pdf, and after reading it I found that it states that Sudoku is NP-complete since partial Latin square completion is NP-complete (prove given in a paper from 1984 that I could not obtain), and it gives a transformation from a partial Latin square to Sudoku.

It appears to me that "partial Latin square completion" does not require that one and only one solution exists, like Sudoku.

Also, since any instance of a NP problem (for example SAT) can be transformed to a NP-complete problem (for example Sudoku), this means that if Sudoku is a NP-complete problem it must have impossible instances, since there are impossible instances in SAT.

Another thing that I do not understand is how can Sudoku belong to NP-complete, since NP-complete apply to sets of decision problems, which is not the case of Sudoku.

At most it belongs to NP-hard, but I could not found any proof. —The preceding unsigned comment was added by 193.136.111.125 (talk) 17:43, 8 February 2007 (UTC).

New assertion of possible Sudoku combinations

I assert that for n^2 grids of nxn cells the number of possible combinations is

(product) from (k=2 to k=n^2) of k!

or for Sudoku 9!*8!*7!*6!*5!*4!*3!*2!=1.83493347 × 10^21 combinations

Instead of analyzing the grid by the nxn cells with far more complex mathematics, I simply found the solution row by row.

For the first row the number of possible combinations is (n^2)! (or 9! for Sudoku), which I doubt anyone will dispute. Then for the second row's first value must be one less than (n^2), or in the case of classic sudoku, would be 8, so we get 8! or ((n-1)^2)!, and so on. Please email me (@gmail) or respond if you dispute this. --Nitrowilly

I would dispute this because it does not take the regional restriction into account. Even if we ignore that restriction, and only consider Latin squares, this method does not work because of possible duplication. Consider Cell (2,4). By your method, (2,4) (row 2, column 4) has 5 possibilities. However, if we let (2,1) = (1,4), then (2,4) has 6 possibilities, because only three numbers have been used in influencing cells. --Carl ^{(talk|contribs)} 17:20, 24 April 2007 (UTC)

____ I have suggested a mathematical model for any Latin square (and for Sudoku also) using this model, we can easily calculate the number of possible valid Sudoku grids. I did it box by box, as per my calculation it comes out as given below for each Box. for Box1, it is 362880,Box2(86400 ), Box3 (216 ), Box 4 (34560 ), Box5 (9216), Box 6 (64),Box 7 (216),Box 8(64) and Box 9 is 1 so the cumulative values comes out to be 1,908,360,529,573,850,000,000,000,000 or 1.908x10^27. you may refer appendix B at http://www.scribd.com/doc/39235249/How-to-Solve-Sudoku-Mathematically for details, given a chance I can explain it HarshGoel (talk) 15:27, 28 October 2010 (UTC)Harsh Goel

Possibilities given arbitrary symbology

It is my observation that we can actually reduce the number of possible distinct grids by a factor of n!. This is because we can arbitrarily reorder the symbols used to arrive at a different grid, but still have the same grid "pattern."

For example, in the 3x3 case,

1 2 3

2 3 1

3 1 2

is treated as a distinct grid from

2 3 1

3 1 2

1 2 3

because the positions of specific numbers change.

As a more formalized way of looking at it, if you consider an nxn Sudoku, a distinct grid is one which, when the entries in row 1 have been assigned values 1..n, the resulting grid is unique.

Going back to the 3x3 case,

1 2 3

3 1 2

2 3 1

would be considered distinct from the previous two grids because there is no way to reassign symbols (or in this case, numbers) to arrive at the exact same grid as before. --Carl ^{(talk|contribs)} 17:30, 24 April 2007 (UTC)

The forum that served as the source of much of this discussion is 'under new management'. (www.sudoku.com) Therefore, many of this article's citing links are no longer pointing at the source material! Some maintenance is required. Perhaps snippits of the forum's threads could be brought to wiki as new (sub)articles? 72.1.212.20 22:04, 12 June 2007 (UTC)

Merge Algorithmics of sudoku here?

Links better than scrolls

IMHO The length of this article (Maths of Sudoku) is already pressing the limits of a good pedia read. Some sections (e.g. the walk through of the classic Felgenhauer enumeration) probably should be relegated to sub-articles to improve the density of main article. I would prefer to have a one or two sentence summary of Algorithmics here (in Maths) and promote the Math's Algorithmics link from the See Also section into the Math's main body.

I did find the Algrithmics Exact Cover discussion mathematically interesting and worth highlighting in the Maths of Sudoku LarryLACa (talk) 04:46, 2 July 2008 (UTC)

creation of Sudoku puzzles

I cannot find a worthwhile piece on 'how a sudoku is created' nor how a generator can assess the difficulty. I think this would be of some interest to the mid-mathematical. Salisbury-99 (talk) 10:34, 24 September 2008 (UTC)

The last section of Sudoku solving algorithms "Developing Sudokus" discusses the search for Sudokus. It's short, but can be expanded.—LithiumFlash (talk) 02:38, 13 April 2017 (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.

Number of givens

The number of givens for classic sudoku is stated as unknown and guessed as 17, but I reckon I have found a proof. I hope it isn't too long:

17 is the smallest number of numbers that it is possible to have on a sudoku grid and still have a unique solution (77 is the largest number there can be and still not have a unique solution). Proof: start with a completed sudoku. If all the numbers except the 1s are erased, three 1s can also be erased and still leave enough information to determine where all the 1s should go, so long as the 3x3 boxes which the 1s are erased from are not from the same rows or columns of 3x3 boxes. If all but the 1s and 2s are erased, three 2s can be erased for the same reason but, in addition, a further 1 or 2 can be erased if they positioned in such a way that the combination of 1s and 2s together determines where it goes. If all but 1s, 2s and 3s are erased, an extra three 3s can be erased but an additional 1,2 or 3 can be determined by the combination of 1s 2s and 3s. Carrying on in this way, the minimum number of numbers needed to determine a unique solution is 9^2-(3+4+5+6+7+8+9+10+11+1), the 1 on the end being because once the positions of all eight different numbers is established, the 9s are in all the remaining gaps. This is 9^2-(((9-1+3)^2+(9-1+3))/2)+3=17. Far an n^2xn^2 sudoku with n^2 nxn boxes, the minimum number of numbers needed is (n^2)^2-(((n^2+n)^2+(n^2+n))/2)+(((n-1)^2+(n-1))/2)=n^4/2-2n^3-n^2/2-n+1/2. In mini Sudoku there are 6 3X2 boxes. The minimum number of 1s that could determine the position of all of the 1s is 4, or mn-n where the Sudoku contains mn mXn boxes with n as the smaller side. For 1s and 2s the minimum number required is 2mn-2n-1, then 3mn-3n-2 etc. This sums to m^2n^2 - mn^2 - ((mn)th triangular number) - 1 = ( m^2n^2)/2 - mn/2 + mn^2 - 1.Cubola zaruka (talk) 05:52, 3 August 2010 (UTC)

Mathematical Model of Sudoku and Latin Squares

Sudoku or any Latin Square can mathematically modelled into different patterns where the given pre-conditions like unique number in row, column and box can be made part of it, Sudoku can be redrawn using numbers as columns and boxes as rows with coordinates ( X - row of Sudoku and Y Column of Sudoku) , Detail model has been posted at the link, since it is entirely new model, someone need to review it. http://www.scribd.com/doc/39235249/How-to-Solve-Sudoku-Mathematically HarshGoel (talk) 10:20, 22 October 2010 (UTC)Harsh Goel

An irreducible 39 clue Sudoku

The World’s First Sudoku* ‘Thirty-Niner’ is on page 20 of http://software.intel.com/sites/products/parallelmag/parallel_mag_issue4.pdf

 —Preceding unsigned comment added by 192.55.20.36 (talk) 19:59, 27 October 2010 (UTC) 

Two 40's are now known, and a section on this topic has been added to the article "Maximum number of givens"—LithiumFlash (talk) 18:32, 20 April 2017 (UTC)

Difficulty rating

Daily 9x9 sudoku puzzles in my local paper have from one- to five-star difficulty ratings. The rating does not seem to be correlated with the number of givens, which is often 28. How can the difficulty rating be calculated? 84.209.89.214 (talk) 23:27, 30 April 2012 (UTC)

Verifying correctness of 3x3 Sudoku's

Here is a MathOverflow discussion how many computations are needed to verify the correctness of a 3x3 Sudoku: http://mathoverflow.net/questions/129143/verifying-the-correctness-of-a-sudoku-solution. This treatment might as well be interesting to be added to this page. — Preceding unsigned comment added by The tree stump (talk • contribs) 08:22, 1 May 2013 (UTC)

External links modified

Hello fellow Wikipedians,

I have just added archive links to one external link on Mathematics of Sudoku. Please take a moment to review my edit. If necessary, add {{cbignore}} after the link to keep me from modifying it. Alternatively, you can add {{nobots|deny=InternetArchiveBot}} to keep me off the page altogether. I made the following changes:

• Added archive https://web.archive.org/20051224043731/http://www7a.biglobe.ne.jp:80/~sumnumberplace/79790008/ to http://www7a.biglobe.ne.jp/~sumnumberplace/79790008/

When you have finished reviewing my changes, please set the checked parameter below to true to let others know.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—^{cyberbot II}_{Talk to my owner:Online} 06:51, 13 January 2016 (UTC)

Permutations

I don't know if this has already been mentioned, but...
For any given solution, there are (3!)⁸ = 1,679,616 permutations of that arrangement, each one being an (equivalent) solution. The permutations are constructed by:

• swapping the three vertical columns of each of the three 3×9 blocks, a total of 3!³ permutations;
• swapping the three horizontal rows of each of the three 9×3 blocks, a total of 3!³ permutations;
• swapping the three 3×9 vertical blocks within each 9×9 puzzle, a total of 3! permutations;
• swapping the three 9×3 horizontal blocks within each 9×9 puzzle, a total of 3! permutations.

Each swapping permutation keeps the solution valid (since entire columns/rows or blocks of columns/rows are swapped together). Furthermore, all of the permutations are independent of each other, so the total number of permutations is 3!³3!³3!3! = (3!)⁸ = 6⁸ = 1,679,616. In other words, any given solution can be rearranged into 1,679,616 different (but equivalent) arrangements (which includes all of the rotations and reflections of the original solution). This implies that the total number of puzzle solutions is 1.6m times larger than the number of unique solutions, where by a unique solution I mean one that is not a permutation of any other unique solution. — Loadmaster (talk) 17:04, 4 August 2016 (UTC)

This is explained in the section "Sudoku preserving symmetries", Mathematics of Sudoku#Sudoku preserving symmetries. Dobrichev (talk) 22:02, 4 August 2016 (UTC)

According to one of the references, I believe the categories above are missing "Relabeling symbols" and "Reflection, transposition and rotation". This would give 2×9! more "permutations" of a Sudoku. This is (currently) in the article under "2.2 Enumerating essentially different Sudoku solutions"—LithiumFlash (talk) 18:53, 20 April 2017 (UTC)

Rectangular Region Notation

What does the text mean when it says, for a rectangular-regioned puzzle with R=2, C=3, N=6:

[The implied grid configuration has] C×R bands×stacks

?? I read this as saying the grid has C=3 bands × R=2 stacks, but this is hardly correct. The grid has N bands × N stacks. So I wonder if this statement is meant to say that

Each region has C=3 bands × R=2 stacks.

While this is closer to making sense, it is still wrong, as this statement should be:

Each region has R=2 bands × C=3 stacks.

Or, the author could be thinking that

[The implied grid configuration has] C×R regions

but then what's the meaning of bands×stacks in the statement?

☞ If you recognize the author's intended meaning, please clarify this statement in the article.

☞ If you cannot figure out the author's intended meaning, then either register your vote to remove it (via reply here,) or just go ahead & do so.

Anyone who resolves the issue on the article page should feel free to delete this section in the talk page as well!

77th Trombone (talk) 04:33, 8 December 2016 (UTC)

Re-order of article's Sections

This article has very interesting information and conclusions, but the overall presentation makes it somewhat difficult to read due to the lengthy and technical discussion. I think this can largely be remedied by re-ordering the article's sections as follows (and minor deletion):

(1.3) Variants - Not the primary topic. I suggest moving this section to the end (after Automorphic sudokus).

(1.4) Definition of terms and labels - This is currently at the end of (1), but these definitions are either self-evident, or aren't used in the article. I recommend deleting this section.

(5) Method and algorithm details for the 9×9 grid direct enumeration - This section is very lengthy and supports 2-4, but does not have new key conclusions. It is supporting information, and should be behind main sections. I suggest placing this after "Automorphic Sudokus" (but before the new location for Variants).

(6) Constraints of Clue Geometry, and (7) Automorphic Sudokus - These are OK where they are (but after reordering will be earlier in the article).

Re-ordering will also address comment in talk (15) above "IMHO The length of this article is already pressing the limits of a good pedia read".

I think this is rather basic (and lesser more detailed improvements can be performed later) so I plan on doing this soon (maybe tomorrow). If anyone has other ideas or objections please leave a commnet.LithiumFlash (talk) 21:27, 28 March 2017 (UTC)

Completed these tasks. (Some minor cleanup may follow).LithiumFlash (talk) 20:32, 30 March 2017 (UTC)

Lead Tag (Removal)

The lead tag "unreliable sources" is too vague because the article is long, and does not suggest what statements may be dubious. Claims that may be unreliable can be tagged specifically with a WP:RS tag. LithiumFlash (talk) 20:43, 30 March 2017 (UTC)

Standardized Format for Sudoku Images

S1 - Suggested standard

S2

S3

S4

S5

S6

S7

Between Sudoku, Mathematics of Sudoku, and Sudoku solving algorithms I see several formats for displaying a Sudoku (even within a single article). For a standard (frame size, aspect ratio, thickness of lines) I suggest "S1". If color is desired (to show a special feature) S2 is good. I think this will help harmonize the articles, and create a better appearance. If any editors Add new images, please use S1 as a template. If any suggestions or comments please reply.LithiumFlash (talk) 02:32, 1 April 2017 (UTC)

I submitted a request to the Wikipedia Illustration workshop to have some existing images standardized (those that currently deviate the most from the standard).LithiumFlash (talk) 13:46, 1 April 2017 (UTC)

Task complete. There are still some images as S5 (larger white border), but they are clustered in one section and it looks fine, so this work is complete.—LithiumFlash (talk) 15:22, 9 April 2017 (UTC)

LithiumFlash, you are doing a good job in improving the article. But be more careful, please, with the changes beyond simple re-formatting. For example, this sentence isn't quite correct: "A paper by Gary McGuire, Bastian Tugemann, and Gilles Civario, released on 1 January 2012 proved through an exhaustive computer search that the minimum number of clues is 17, and this was confirmed independently by researchers at University College (Dublin)." Thanks,Dobrichev (talk) 07:46, 10 April 2017 (UTC)

Dobrichev, thanks for your kind words. I believe I pulled two sentences from different sections into a single paragraph, and I didn't realize they were about the same work. I (or any editor) will surely fix it. I believe the statement can be recast as follows:

A paper by Gary McGuire, Bastian Tugemann, and Gilles Civario, released on 1 January 2012, explains how it was proved through an exhaustive computer search that the minimum number of clues in any proper Sudoku is 17.

I will plan to fix it early tomorrow (after double-checking the references). Please reply again if there is still a concern. Thank you, and I really appreciate your comment.—LithiumFlash (talk) 00:37, 11 April 2017 (UTC)

A possible confirmation of McGuire's work is the BOINC project sudoku@vtaiwan http://sudoku.nctu.edu.tw/. It didn't publish the source code, leaving the possibility that the process has flaws, or even more - that contributors' efforts were used for a task not related to the subject at all. — Preceding unsigned comment added by Dobrichev (talk • contribs) 05:29, 11 April 2017 (UTC)

Dobrichev, thank you for that observation. I also noticed that the same reference was in the Main article, so I added it here also. I did clarify the statement and believe it is OK now. As usual, feel free anytime to leave other comments if you have questions about the article's quality. You are also free to leave comments at my talk page (User talk:LithiumFlash). Thanks for comments.—LithiumFlash (talk) 15:44, 11 April 2017 (UTC)

https://en.wikipedia.org/wiki/Wikipedia:Image_use_policy says:

"Generally speaking, you should not contribute images consisting solely of formatted or unformatted text, tables, or mathematical formulas. In most cases these can instead be typed directly into an article in wiki markup (possibly using MediaWiki's special syntax for tables, math). This will make the information easier to edit, as well as make it accessible to users of screen readers and text-based browsers."

Maybe the best long-term solution, at least for ordinary sudoku, is a template which will guarantee that all the puzzles/grids on the page are in common format.

Next, I am going to remove the references to external copies of the pictures shown on this page. They refer to simple pictures in a single author's page, don't have any additional explanation like the history, authors, or methodology used to generate the respective puzzle, and don't contribute to the article. (Edit: Done)

I will also remove the "Names" of the puzzles, like "Raphael" and "Tourmaline". If they are so exceptional to have its own name, and the name is sufficiently popular, please provide sources. (Edit: Done)

I have to check again, but after the standardization of the format, few license issues appear. Surprisingly, the new pictures are licensed by the new author, but some of the older were created by other authors. I am not sure whether this is worth and should it happen only for re-formatting purposes. There is plenty of puzzles in public space and I would prefer Public domain pictures for the article.

If the examples of the symmetrical puzzles remain, a slight restructuring of the article is needed. Possibly new sub-section within the "Minimum number of givens" below "Ordinary Sudoku" for the puzzles with given symmetry and minimal number of givens, or a new section "Symmetrical puzzles" close to the bottom of the article that explains the symmetries and automorphisms? The picture at the top of the article has nothing to do there and should be moved/removed too. Dobrichev (talk) 22:39, 11 April 2017 (UTC)

I agree the lead image can be improved. According to Manual of Style a good lead image "...should be relevant and technically well-produced. It is also common for the lead image to be representative because it provides a visual association for the topic, and allow readers to quickly assess if they have arrived at the right page..." Suggestions welcome.—LithiumFlash (talk) 05:56, 12 April 2017 (UTC)

I changed my opinion on using the tables instead of pictures. I found there are already templates made for this purpose, but they aren't looking very well. On the other hand I found that it is very easy to compose a SVG file by hand using an existing file as template and editing only the cells using any general purpose plain text editor. In a few minutes I made this file which could someday come in use.

Minimal 9x9 Sudoku with 40 givens

Dobrichev (talk) 19:03, 18 April 2017 (UTC)

Nice find Dobrichev, the references show that that is the maximum known number of clues for a minimal Sudoku. The article doesn't yet have a section for this topic, so I added it (and the Sudoku).—LithiumFlash (talk) 14:15, 20 April 2017 (UTC)

Sudoku solution grids symmetries

The solution grids symmetries are something fundamental and deserves a dedicated section in the article.
User ‎LithiumFlash had removed it from the article, then I added it back, then he/she removed it again. So far so good. But in its current version, below in the article a text

"A Sudoku will remain valid under the actions of the "Sudoku preserving symmetries" (see also Jarvis)..." points to "Enumerating essentially different Sudoku solutions" where the symmetries are explained. To me this is wrong and confusing.

In addition, a more specific term is "Validity Preserving Transformations". It is widely used in the sources I use, but I am unsure whether it is globally used and is more correct/accurate than "Sudoku Preserving Symmetries". How do you think?

These symmetries are potential target for links from other sections and sudoku-related articles too - methods of canonicalization (normalization) of grids and subgrids, working only with identities in order to reduce the search space, etc.

I am not against removal of this section from the context of the enumeration. Agree that my latest edition was over-structured and not looking good, but it was only an attempt to switch back to the older versions of the article, where it stays for years. Even then it was difficult to find, see the question for #Permutations above in this talk page.

Suggestions are welcome.

Thanks, Dobrichev (talk) 18:47, 18 April 2017 (UTC)

I don't believe I removed any important text unless it was redundant. The current section:

2.2 Enumerating essentially different Sudoku solutions

(includes information about "solution grids symmetries").

This is fairly early in the article, although it is inside the section about "enumerating" solutions. Maybe it will be better to pull this out, and place it before "Enumerating solutions"? Whether it is part of enumeration or not, both statements point to the same reference (#6) and arrive at the same conclusion: "Using this technique, Jarvis/Russell computed the number of essentially different (symmetrically distinct) solutions as 5,472,730,538." Any editor can pull this section out and place it before enumeration (with some minor text revision) if it is what you are referring to. Let me know and I will be happy to do it.—LithiumFlash (talk) 18:07, 20 April 2017 (UTC)

Reliable sourcing requirements

This article has been tagged as relying too much on self published sources since September of 2021, but nothing much has changed. This is a final notice that I intend to start cutting everything based on self published sources, forum posts, and so on soon. If you're reading this and can improve the sourcing with citations to journal articles or books from academic publishers, please do so. If not, this article will be getting shorter. MrOllie (talk) 18:48, 26 June 2022 (UTC)

I have carried out the cuts. Do not restore any of this content without citations that meet WP:RS - that means no forum posts. MrOllie (talk) 17:04, 22 August 2022 (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)