Talk:Mathematics of Sudoku

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class Low Priority  Field: Discrete mathematics
Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article.

Contents

[edit] 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.

[edit] 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 Bands(g) valid Sudoku bands (typically ~200); though the generator itself is emphatically not a valid band.

We loop over all compatible generators (g1,g2,g3) 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 16803 = 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 Bands(g) and a unique number of completions to a full grid (the g2,g3 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
  • 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 ...

[edit] 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)

[edit] 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)

[edit] 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)

[edit] To Do

[edit] 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)

[edit] ;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.

[edit] 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)

[edit] 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)

[edit] 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).

[edit] 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)

[edit] Bottom of List, Please insert comments above

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

[edit] 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)

[edit] 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)

[edit] 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)


[edit] 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)

[edit] 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).

[edit] 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)

[edit] 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)