Unsolved Problems In Mathematics #2242 : The Secret of Sudoku
Many people think the maths is a pretty closed field – that there aren't really many open questions that can be appreciated by people with little training in the field.
These people are, as usual, wrong, wrong, wrong....
If you've been reading newspapers (instead of, er, revising…) recently, you will have found what we can loosely term Sudoku Wars. In a recent, short period of time, more or less all the major newspapers, from the Guardian to the Telegraph to the Sun, have taken on this rather obscure Japanese puzzle. Today, the Guardian had one puzzle to every page of their G2 supplement.
Quite possibly this mania will blow off in a week or so.
If you don't know what sudoku is…
Basically, you have a 9×9 grid that is further divided into 9 3×3 smaller squares. The trick is to, given a number of initial hints, fill up the grid with digits 1–9 so that:
- Every subgrid contains all 9 digits.
- Every row contains all 9 digits.
- Every column contains all 9 digits.
Fun, eh? Ok, it's more interesting that it sounds. It's reasonably easy to think of an algorithm to solve it – simple trial and error can work. But it has been proven that the puzzle is NP-Complete – that there is unlikely that there is an efficient (i.e. scaling according to some polynomial law) way to do it. In short, it's a fair bet that a Sudoku puzzle will take you a long, long time…
(Part of the neatness of NP-Complete problems is that one fast solution can be used to solve other problems quickly as well. So if you do find a really fast solution, make sure YOU COME STRAIGHT TO ME, AND TELL NO ONE ELSE. )
Erm… In any case… A lot of other questions of Sudoku are interesting, and unanswered. For example, a newspaper cannot just randomly toss together a lot of numbers, and hope that it makes a decent sudoku puzzle. Some patterns of initial conditions give NO solution. Others allow several solutions. For example, if we want to fit the corners of a rectangle with two different numbers, unless we get a hint about one of them, the two possible combinations can be substituted for each other.
So, what's the minimum number of hints we need to give to get a single unique solution? We don't know. The best that has been found is 18. But we really don't know. (Or at least, I don't know.)
In fact, we don't even know how many solutions there are for a blank grid – how many ways can we fill a standard 9×9 grid whilst not breaking the rules of Sudoku?
Maths. Scratch the surface, and we know almost nothing.
13 May 2005 21:27
| 
Comments (64)
| 
Report a problem
Loading…
64 comments by 2 or more people
[Skip to the latest comment]Lee Davis
calculating the total number of ways of filling a blank grid is not too difficult with a little thought as it is simply a case of working out the number of permutations and combinations. When I have a bit more time i might sit down and work it out but it is a rather large number butconsiderably less than 1.1E50
14 May 2005, 12:49
It seems easy, yes, but it isn't. A large proportion of permutations don't work. It's very easy to calculate the number of possibilities in one, initial square. But extend it to the neighbouring two squares is hard – since these two may imply contradictions in the 3×3 square touching both of them. And extending it to fill the 9×9 grid is neigh on impossible.
14 May 2005, 13:17
Sam Samuelson
Happiness is Shanghai, and all of lifes problems seem insignificant
link
14 May 2005, 20:42
I wrote a program for solving Su Doku. After reading your blog I modified the program so instead of stopping after a solution it adds 1 to a total and looks for another solution. So all I need to do is feed it an entirely blank grid and it will tell me how many solutions there are. Yeah right, that's not going to work unless my processor is a trillion GHz! That's what I get for trying brute force. I can however tell you that there are at least 165 valid grids!
22 May 2005, 07:25
Coloin
I have nearly done it
I might even have done it but not totally proved it.
How does
= 2 890 020 218 795 458 560 000
or maybe it is
= 5 780 040 437 590 917 120 000
These are very big numbers.
I did it first ! 24th may 05
Maybe the japanese have already solved it ?
Regards
There is a forum on suduku.com
24 May 2005, 00:16
Tony Goddard
I have read about some of the efforts to solve sudoku but no one seems to be using
the tried and tested methods of linear optimisation: replace values x in cells by 2^x-1
so 1 becomes 1, 2 becomes 2 3 becomes 4 and 9 becomes 256. The sums of rows
columns and boxes are 511. That gives 27 equations for up to 64 unknowns. There
should be matrix algorithms around that try and find solutions for such ill conditioned
sets of equations. Originally I tried to devise a program based on this method, but gave
up and resorted to brute force search.
24 May 2005, 17:41
Hey, that's an interesting approach! I don't know about linear optimisation, but it looks pretty funky.
Why 64 unknowns? The grid is 9×9. Is it 64 because one row and one column can be deduced by the filling of the other 64 squares? If so, you can also give yourself a free box (intersecting the row and column) and possibly more…
24 May 2005, 19:13
David
The number of ways a blank 9×9 grid can be completed and satisfy the su doku criteria is 9! times 2*18 or 95,126,814,720. For a 16x16 grid it is 16! times 2*48. A little bit of group theory helps.
31 May 2005, 14:24
Can you please tell us why?
31 May 2005, 15:01
Someone seems to have solved the number-of-solutions problem by a brute force approach. See:
link
31 May 2005, 15:27
"The number of ways a blank 9×9 grid can be completed and satisfy the su doku criteria is 9! times 2*18 or 95,126,814,720. For a 16×16 grid it is 16! times 2*48. A little bit of group theory helps."
"Who do you think you are? Pierre De Fermat?" ;) Seriously though, what is it with people giving unsubstantiated answers. I don't dispute you're correct (though Zhou seems to) but come on, explain your answer please.
31 May 2005, 17:36
One thing I've been wondering, you might be able to help me out here…
How exactly do we KNOW for sure that this problem is NP-complete? There might be a really quick algorithm that we just haven't found yet. More importantly, how is it that finding a quick algorithm for this will help us find a quick algorithm for lots of other NP-complete problems? Many such problems are seemingly unrelated to each other.
I don't know the number of possible Suduko solutions, but its very very big.
05 Jun 2005, 13:40
Well, the definition of NP-Complete is that if we can solve one, we can transform the algorithm to solve others. So to prove it, we just need to prove a transformation from this puzzle to another, known to be NP-Complete puzzle.
A technical proof can be found here. Look for the part on 'Number Place'.
05 Jun 2005, 15:25
tinfoil
The minimumSoduku grid that I have been able to find so far is 17. That is, 17 (unfortunately not symmetrical) clues define a unique grid. One example is:
xx6 9xx x7x
xxx x1x xx2
8xx xxx xxx
x2x xxx xx4
xxx xxx xx1
xx5 xx6 xxx
xxx xxx x6x
xxx xx2×5x
x1x x43 xxx
seems to have only one valid solution. I have no proof that this is a minimum, and I would have guessed that 18 was the minimum until I found this one.
08 Jun 2005, 19:06
Gavin Lock
WRT Tony's linear optimisation…
27 equations because you need 1 for each row, 1 for each column and 1 for each region.
64 I assume to be 81–17, where 17 is generally accepted as the minimum number of givens required.
As far as 2^x-1 is concerned though, you might as well just add the digits themselves to verify thast you get 45 (1+2+3+..+9). Now admittedly, 1+2+3+5+5+5+7+8+9 is wrong, but so is 1+2+4+8+8+8+32 etc, so you may need disambiguation logic either way.
09 Jun 2005, 12:33
Graham
I do not know how many solutions there are to su-doku. However the answer is clearly divisible by 4*9!=1,451,520
Solve any su-doku puzzle then exchange all the 1s with 2s or 2s with 3s etc and you will still have a 9*9 grid that satisfies the su duko rules. The number of ways the 9 numbers 1–9 can be arranged is 9! thats basic maths. So there are 9! permutations for any solution. Now again take any solution and rotate it by 90 degrees to give another 4 permutations of the same solution. I'm pretty sure because of the arrangement of the 9 numbers in the centre box no symetrical solutions are possible so these should be distinct. Now to get an idea of the real number of solutions you could write a program to check solutions against other solutions and group them into permutations of each other as described above. I've thought how to do this, A simple way (not the best) would be to take 2 solutions and calculate (10*a+b) for a and b numbers in the same cells in solution a and b. If there are only 9 diferent values in the 81 answers the solutions are congruent. You will need 4 passes for the 4 symetries its not hard. This is not the best way to do it but the easiest to explain. I would imagine most people setting su doku puzzles are just working with different permutations of a hand full of solutions. That said looking at it I would think there are quite a few distinct solutions.
Anyway maybe someone wants to give this a go. Is it 10s 100s 1000s or 10,000s? You can find out. Given that for any solution there are another 1,451,519 the program that claims to solve all 13.98 million solutions is clearly wrong.
24 Jun 2005, 12:02
jerry
The additional constraint that a standard nine-by-nine sudoku puzzle have three-by-three blocks that also contain each of the nine digits reduces the enormous number of possible nine-by-nine Latin squares to a smaller but still-humungous number: 6,670,903,752,021,072,936,960. See link for a discussion on how Bertram Felgenhauer of Dresden, Germany, obtained this number, which represents how many unique, one-solution puzzles can be produced.
29 Jun 2005, 22:20
Tim
Zhou – I don't think that paper proves that Sudoku is NP-Complete – I think it just shows that checking to see if a Sudoku problem has multiple solutions is NP-Complete.
In the begining of the paper they show that the Another Solution Problem often has a different complexity to the original problem, then later they show that ASP for Sudoku is NP-Complete. There is no analysis of the original Sudoku problem.
Please correct me if I'm wrong :)
30 Jun 2005, 02:26
angus
How do I know, for any one puzzle, how many solutions there are. i.e. I pick up a puzzle and I want to know if there is only a single unique answer or hundreds.
30 Jun 2005, 12:12
Ankit Patel
It is 9! times 3!x3!x3!x3!x2!x2! which comes to 1,881,169,920.
09 Jul 2005, 18:38
Daniel
Hi,
@tinfoil: Your minimumSoduku with 17 givens has one unique solution:
146 928 375
593 617 842
872 435 916
721 359 684
968 274 531
435 186 297
257 891 463
384 762 159
619 543 728
Using my solver I can prove in 107.50 sec that there exists only this single solution
and no other solution.
If you remove e.g. the 4 in r4c9 then there exist in total 20908 solutions.
Regards
26 Jul 2005, 10:23
Eric L
Hi,
Tinfoil
With my excel sheet, it took me 72 secs to solve it.
It seems that it is not because you have less digits on the initial grid that it is more difficult.
Eric
Paris
03 Aug 2005, 13:55
Richard V
There is another approach. Start with a valid Sudoku matrix and calculate how many ways it can be transformed to produce other valid matrices. The obvious starting matix is:
123456789
789123456
456789123
234567891
891234567
567891234
345678912
912345678
678912345
The first three rows can be arranged in 3! ways. Ditto the second and third sets of three rows. The rows can therefore be arranged in 3! x 3! x 3! ways. Similarly the sets of three columns can be arranged in 3! x 3! x 3! ways. The 3×3 blocks can also be rearranged, keeping the Sudoku validity. Vertically there are 3! ways; horizontally there are 3! ways. Finally one needs to multiply by 4 for rotation and 2 for handedness. The result is 8 multiplied by 3! to the power 8 which is 13,436,928. This is smaller than other so-called "solutions" but I've not been convinced by them. It depends whether one solution can be transformed into all others. Bit like Rubik's cube.
06 Aug 2005, 15:51
lamita
I guess only mathematicians are trying to figure out how many solutions a puzzle can have. I solve them by process of elimination. One time I worked so long and hard, I got a headache. It was only three numbers off, or was it?
If you have four possibilities four each square it seems impossible to figure out manually. One would need excel or some computer assistance, but it seems that would take the fun out of it. If it is too, too difficult, it is no longer fun but a distraction and an aid to procrastintion (LK).
But, I still believe an algebraic expression can simply solve each puzzle. Someone knows, but they are not telling. Calling all Havard and MSU alumni!!!
08 Aug 2005, 00:07
Thomas
Hi,
I had a similar question. I wanted to know how many unique boards there were (excluding symetrical answers). This way any board could be constructed by taking a unique form and moving it arround. Before talking to my friend Pierre De Fermat, I decided to Google it and found:
5,472,730,538
link
Well, how bout that?
Cheers,
TD
02 Sep 2005, 17:30
Rev. Bob
Are there sudoku puzzles in which the solution graph doesn't branch? I.e., at any given point there's one and only one cell which can be filled given the cells already filled and the rules of the puzzle?
22 Sep 2005, 11:19
nobody
Hi,
@tinfoil: Your minimumSoduku with 17 givens has one unique solution:
146 928 375
593 617 842
872 435 916
721 359 684
968 274 531
435 186 297
257 891 463
384 762 159
619 543 728
Using my solver I can prove in ¡23 sec! that there exists only this single solution
and no other solution.
30 Sep 2005, 23:55
The Minnesota Mayhem
@tinfoil:
In 2.32 seconds I can prove that your minimum Suduko with 17 givens has more than one solution. I used the AC-3 algorithm on the directed constraint arcs between cells to remove the possible values for each cell. If your puzzle had only one solution, then after AC-3 finishes, each cell should only have one possible value, and that value would be the one the cells needs to be set to in order to solve the puzzle. But with your puzzle, there were many cells that had multiple possible values after the algorithm finished.
23 Oct 2005, 05:40
The Minnesota Mayhem
@tinfoil:
I apologize. Your puzzle does have one and only one solution. I realize now the AC-3 algorithm doesn't recognize all inconsistent constraint arcs and parse them out, so there are many chances for it to think a puzzle has multliple solutions b/c it couldn't find all the ways to remove all but one of the possible values for each cell.
23 Oct 2005, 16:29
Ultimateron
I have a program that solves Sudoku by first using only "manual" techniques – the sort that real people use with a pen and paper – then goes on to guess numbers and solves it. All the problems that I have generated myself (using trial and error till I get one with a unique solution) require guessing. BUT ALL the ones published in, for example, The Times, CAN be solved by manual methods. SO, how do they go about generating problems which can be solved by human beings rather than computer?
21 Nov 2005, 13:50
Matthew
Soduko Solving Rules
Allowed numbers: the numbers that are not canceled out by other numbers within the 3×3 subgrid and 2 9×1 number lines that intersect at the box
Definite numbers: the numbers that are set by the rules of sudoku or part of the starting sudoku grid
Subgrid: 3×3 grids within main (9×9) grid that contain the numbers 1 through 9 (9 subgrids within main grid)
Number line: 9×1 line that contains the numbers 1 through 9 (18 number lines within main grid, 9 horizontal x 9 vertical)
In each box, calculate the allowed numbers using the definite numbers and rules below:
1) only one of each number can exist within 2 intersecting 9×1 number lines and each of the 3×3 subgrids, so calculate allowed numbers by using the definite numbers within the subgrids and numberlines to find which numbers are not allowed (you are left with the allowed numbers)
2) if an allowed number is only within one column or row inside the 3×3 subgrid, this means that you can cancel out this number in the other 2 3×3 subgrids along this 1×9 number line
3) if only one box in a 3×3 grid allows the number, then this is the place for that number within this subgrid
4) if the other 2 3×3 grids along a 9×1 number line do not allow a number, the number must fall along the 9×1 number line within the remaining 3×3 subgrid
5) if there is only one place along a number line that a number may be placed, then this is the place for that number
26 Jan 2006, 19:54
Nicolas
I would like to suggest this nice website Daily Sudoku Puzzle
It proposes daily new sudoku puzzles, and in particular, fiendish level with only one solution where it is necessary to use complex methods.
27 Jan 2006, 23:15
Fernand Colin
A sudoku grid is a group 9! x 68 x 2 permutations. 9! is related to the number of ways you can transcode the 9 figures. 68 is related to number of allowed permutations of lines, columns and blocs. 2 is the parity factor (flipping the grid or mirror image)
Knowing 8 independ nummers in 1 row and in 1 column plus a single data outside the row and the column can be shown to solve in at most 42 x 66 logical operations of comparison with a set of predefine templates. So the minimum data needed is 17. The data outside the row and the line is needed to resolve the parity factor.
28 Mar 2006, 23:13
Fernand Colin
A sudoku grid is a group 9! x 68 x 2 permutations. 9! is related to the number of ways you can transcode the 9 figures. 68 is related to number of allowed permutations of lines, columns and blocs. 2 is the parity factor (flipping the grid or mirror image)
Knowing 8 independ nummers in 1 row and in 1 column plus a single data outside the row and the column can be shown to solve in at most 42 x 66 logical operations of comparison with a set of predefine templates. So the minimum data needed is 17. The data outside the row and the line is needed to resolve the parity factor.
28 Mar 2006, 23:19
nexika
Who Else Wants To Know The Secrets To Solving Sudoku Puzzles?"
Click here! NOW!
link
01 Apr 2006, 23:39
Kyle
There are only about 5.5 billion diiferent solved sudoku boards possible if count boards transformed under column o row permutation, ie swaping in the same three block width, swapping three block widths, ie column or row that are in the same three blockis, or by renaming ie swapping 4 and 9 all over the bored as being the same bored. the actually form a permutaion group under function composition, but that is another topic completely
10 Apr 2006, 18:45
Moritz Lenz
Hi,
regarding your discussion about how many hints are needed, I found a interesting page about minimal sudoku: link
Gordon has a collection of >30.000 sudoku with only 17 hints. I checked them, they are all distinct (e.g. you can not generate one from another by just permuting the number, exchanging rows etc.). I also wrote a little perl script that takes away one hint and solves it, and each generated sudoku has multiple solutions.
I have a german homepage about sudoku:
link
And something about two programs I wrote (one solver and one about a program that transforms a sudoku to a canonical form) (It's in german as well, but I may translate some of it if there is a general interest):
link
30 May 2006, 15:26
Richard K
the total # of configs. of a 9×9 grid (#'s 1 – 9), (no duplicate #'s in rows) is 9! x 9! which is about 132 billion. The vast, vast majority of these will be non–Sudoku solutions. – I haven't figured out what # is but it must be far less than 132 billion – popular # I have heard is 5 billion – this still seems way to high to me – my guess would be a few hundred million
02 Jun 2006, 22:33
Richard K
revision of my bad math & previous posting: # of possible configs. of a 9×9 grid is 9! x 9! x9!, not 9! x 9!, which is about 360,000×132 billion – sorry I was only out by a factor of 360,000. This then refutes everything I said about the 5 billion solutions # being in question. Maybe I should leave this topic to the more qualified out there.
03 Jun 2006, 20:35
Maybe that's a good idea.
03 Jun 2006, 22:23
Richard K
Some redemption – Came up with formula (won't go into details):
N! x (N–1)! x (N! x .367) gives an approx. for the total number of different grid patterns (ie. no duplicating #'s in the rows and columns in the grid). So for a grid of #'s 1 – 5 plug in N=5 and get about 127,000 patterns. Using N=9, you get 1.95×10 15 patterns. Because a Sudoku grid also has to have 9 grids 1-9, I then divided 1.95 x 1015 by 9! (makes sense if you think about it) and got 5.4 billion. I believe this is the accepted value (approx.) calculated by others.
05 Jun 2006, 08:50
Charles N
I have spent some time evaluating the total possible solution with a blank grid question. I created a program that would runs every possible number from 1 to 9 through a 9 by 9 grid creating 1.96627e+77 possible combinations. Then if the set of numbers meet the criteria of a valid Suduko solution it adds it to a running tally. I ran the program for some time and compared the progress to the time interval. Therefore I determined with this brute force method it would take roughly 1.59304e+64 days to finish. As we all know this will take way way to long. However I had an Idea… If we only looking at the 1st top row for 9 squares, the numbers 1 to 9 only appearing once in any given square results in 8,201,576 possible correct solutions & 991,798,423 non correct, that’s a ratio of 0.8% correct out of the total possible. Now if the first line uses one of these solutions each of the following 8 lines must then use a decreasing amount of the same possible combinations. Therefore it appears to be a easier way to calculate the total possible solution by using only those possible solutions to start off with rather then every possible combination including clearly wrong solutions. I will refine my program and hopefully arrive at a final solution in a shorter time span.
20 Jun 2006, 22:03
Charles N
After refining my old program it now appears that a more constricted brute force attack would take 3.33329e+43 days rather then 1.59304e+64 days. In the big picture that's a huge reduction of time but still way way to long for my small computer. Then I thought about breaking the program up kind of like the SETI program. So if every person in the world had a computer averaging the same speed as mine it would take 18252101300479123887748117727584 years to finish not calculation in advances in processor speeds. Sounds like a plan lol…... Sigh.. Brute fore cannot succeed. So sad :–(
20 Jun 2006, 22:25
Charles N
Small correction the in the 1st top row for 9 squares, the numbers 1 to 9 only appearing once in any given square results in 362,880 possible correct solutions.
20 Jun 2006, 23:05
Charles N
Small correction the in the 1st top row for 9 squares, the numbers 1 to 9 only appearing once in any given square results in 362,880 possible correct solutions.
20 Jun 2006, 23:08
Moritz Lenz
Regarding the number of Sudokus, you should read the following paper (or at least its abstratct) (PDF warning):
link
(there are 6670903752021072936960 different Sudokus).
You can reduce the number of cycles your program has to make if you consider equivalency classes…
Best regars,
Moritz
20 Jul 2006, 18:26
Mike P
I have read the link provided by Moritz Lenz (comment #46) and these two guys appear to know what they are talking about. Certainly a lot cleverer than I am.
But, how about this. It has a certain symetry to it:
Starting in Block B1:
In B1 you get 9!
In B2 and B4 you get 6!*6! (because with B1 filled you only have 6 choices in each Row of B2 or Column of B4 and you can fill them in 6! ways)
In B5 (centre block) you get 4!*4! (Your choices are now reduced to 4 once B1 B2 and B4 are filled and you can use these in 4! ways)
In B3 and B7 you get 3!*3! (And so on)
In B6 and B8 you get 2!*2!
In B9 you get 1!*1! (By the time you get to fill this Block each square only has one possible number that can fill it)
This = 9!x2×6!x6!x4!x4!x2×3!x3!x2×2!x2!x1!x1!
This totals 1.24825E17 or 601 974 000 000
Now that is just for ONE symetry starting with 9! in block B1. You can permute these 9 Blocks 9! ways so the final answers is the above multiplied by 9!
This totals 4.52966E22 or 45 296 600 000 000 000 000 000
Now the answer given by the clever guys is 6.671E21 which is a little less than I have.
But hey, I think I am close enough!
:)
Mike
23 Jul 2006, 13:06
Mike P
Oops. Sorry.
1.24825E17 obviously totals 124 825 000 000 000 000
But the solution remains the same
Mike
23 Jul 2006, 20:04
Moritz Lenz
Hi Mike,
regarding your comment #47:
If you take a look at block b1 you have 9! posibilities if you consider permutations, or just one if you don't consider them.
Therefore it is wrong to multiply twice with 9!. It leads to a result with the right order of magnitude but nonetheless its wrong – sorry ;–/
To be a bit more verbose:
You should take a look at how many Sudokus you can construct that start with
1 2 3
4 5 6
7 8 9
After you found that number, let's call it N, you can multiply it by 9!. But if you now want to permute the blocks you are creating Sudokus that – after permutation – start with the same block as above. You are counting them twice.
Best regars,
Moritz
24 Jul 2006, 15:38
Jean-Marc
Once you generate a valid grid, how do you know how many numbers you have to blank out and still make it solvable?
Jean–Marc
22 Aug 2006, 02:06
BKoct
How many permutations are there for the number of "clue sets" that exist?
Lets make it easy – even for just one puzzle
Puzzled!
aka Brian
22 Aug 2006, 03:43
Paul MacGowan
Im a little confused by comment #47
Before finding this web site, I had approached it in a similar way but come up with a very different answer 8,776,790,000,000,000.
Im certainly no maths wizz so could someone tell me where im going wrong, perhaps with an idiot example?
My method was as follows …
It assumes that the permutations of the block being calculated are reduced due to neighboring block(s) already being populated.
9! Permutations in Top Left block
6! Permutations of the Top Middle Block
3! Permutations of Top Right Block
6! Permutations of the Middle Left Block
3! Permutations of Bottom Left Block
3! Permutations of Middle Middle Block
3! Permutations of Middle Right Block
3! Permutations of Bottom Middle Block
3! Permutations of Bottom Right Block
That gives me 8.77679E +15 8,776,790,000,000,000 and i dont understand why i would then need to rotate, transpose or wotever else you guys are on about.
Please educate me!
Paul
01 Oct 2006, 08:10
Paul MacGowan
On 2nd thoughts perhaps Bottom Right Block cant have 3! permutations as its contents will always be driven by the other blocks.
That would take my answer down to 1.4628 E15 1,462,800,000,000,000
More confused!
Paul
01 Oct 2006, 08:25
Paul MacGowan
Doh!
On 3rd thought, there are also less than 3! permutations in each of the Middle Right or Bottom Middle Blocks.
E.g., The contents of the top right block also affects the middle rights contents but to a lesser degree.
Does this drop the permutations down from 3! to 2! in each case or am i clutching at straws here?
If so my answers drops again, this time to
1.62533 E+14 162,533,000,000,000
At this rate I’ll have it down to single figures before long.
Im unsure about the permutation in those 2 blocks, perhaps one of you mathematicians can enlighten me?
Paul
01 Oct 2006, 08:40
Paul MacGowan
OK, last crack at this i promise ….
changed my mind about the 2! probability for those two blocks, instead think that they originally had the same probability as the neighboring block, ie 3!, but
that its compound effect is to halve that, so my ignorant conclusion is that its 3!/2
so my final attempt is …
9! x 6! x 3! x 6! x 3! x 3! x 3! x (3!/2) x (3!/2) x 1!
which is
3.65699 E14
365,699,000,000,000
If this is wrong please tell me coz I am trying to work this out for a good reason
(want to use this as an example of how out database solution (www.minotaur.eu) can resolve complex selections across trillions of records in seconds, but need to know the outer boudaries of this dataset before we generate it and load it)
If im right about the magnitude we will be able to provide a free online platform that tells the user how many possible solutions there are for any given sudoku problem, within seconds (and display them if required)
guess you guys all sleep in on Sundays!
Thanks
Paul
01 Oct 2006, 12:15
Sohan
Maybe someone can consider that in the 9×9 grid each number is repeated 9 times so that has to be considered in the permutation or combination calculations so as to get a value of how many different ways the numbers can be arranged without repetition in any particular 3×3 ninth of the grid and then apply a condition (the rules of sudoku).. I’m no mathematician so yeah just giving ideas. Sudoku is addictive!
Peace
13 Oct 2006, 12:39
lillian
this is the game that will help you focus on every thing it makes you learn how to be patien to everything this is a good game for kids to play
01 Nov 2006, 20:19
parijat
interesting problem, I ve not calculated but It no of solutions should not be more than few hundread.
11 Feb 2007, 15:28
sam
can u give me a link to find suduko answers
01 May 2007, 00:41
Nathan
I’m not 100% sure, but I think the answer might be 4
16 May 2007, 00:33
coolpanda
I wrote a problem for solving it actually there are four answers:
Orignal Matrix:
1 6 4 0 0 0 0 0 2
2 0 0 4 0 3 9 1 0
0 0 5 0 8 0 4 0 7
0 9 0 0 0 6 5 0 0
5 0 0 1 0 2 0 0 8
0 0 8 9 0 0 0 3 0
8 0 9 0 4 0 2 0 0
0 7 3 5 0 9 0 0 1
4 0 0 0 0 0 6 7 9
Result:
1 6 4 7 9 5 3 8 2
2 8 7 4 6 3 9 1 5
9 3 5 2 8 1 4 6 7
3 9 1 8 7 6 5 2 4
5 4 6 1 3 2 7 9 8
7 2 8 9 5 4 1 3 6
8 1 9 6 4 7 2 5 3
6 7 3 5 2 9 8 4 1
4 5 2 3 1 8 6 7 9
1 6 4 7 9 5 3 8 2
2 8 7 4 5 3 9 1 6
9 3 5 2 8 1 4 6 7
3 9 1 8 7 6 5 2 4
5 4 6 1 3 2 7 9 8
7 2 8 9 6 4 1 3 5
8 1 9 6 4 7 2 5 3
6 7 3 5 2 9 8 4 1
4 5 2 3 1 8 6 7 9
1 6 4 8 9 7 3 5 2
2 8 7 4 6 3 9 1 5
9 3 5 6 8 1 4 2 7
3 9 1 2 7 6 5 8 4
5 4 6 1 3 2 7 9 8
7 2 8 9 5 4 1 3 6
8 1 9 7 4 5 2 6 3
6 7 3 5 2 9 8 4 1
4 5 2 3 1 8 6 7 9
1 6 4 8 9 7 3 5 2
2 8 7 4 5 3 9 1 6
9 3 5 6 8 1 4 2 7
3 9 1 2 7 6 5 8 4
5 4 6 1 3 2 7 9 8
7 2 8 9 6 4 1 3 5
8 1 9 7 4 5 2 6 3
6 7 3 5 2 9 8 4 1
4 5 2 3 1 8 6 7 9
18 Jun 2007, 17:29
coolpanda
6 more, and i might still missing some … :(
1 6 4 3 9 7 8 5 2
2 8 7 4 6 3 9 1 5
9 1 5 6 8 1 4 2 7
3 9 1 2 7 6 5 8 4
5 4 6 1 3 2 7 9 8
7 2 8 9 5 4 1 3 6
8 5 9 7 4 1 2 6 3
6 7 3 5 2 9 8 4 1
4 3 2 8 1 5 6 7 9
1 6 4 3 9 7 8 5 2
2 8 7 4 5 3 9 1 6
9 1 5 6 8 1 4 2 7
3 9 1 2 7 6 5 8 4
5 4 6 1 3 2 7 9 8
7 2 8 9 6 4 1 3 5
8 5 9 7 4 1 2 6 3
6 7 3 5 2 9 8 4 1
4 3 2 8 1 5 6 7 9
1 6 4 3 9 5 7 8 2
2 8 6 4 7 3 9 1 5
3 1 5 6 8 1 4 2 7
7 9 2 8 1 6 5 4 3
5 4 7 1 6 2 3 9 8
6 2 8 9 5 7 1 3 4
8 3 9 7 4 1 2 5 6
6 7 3 5 2 9 8 6 1
4 5 1 2 3 8 6 7 9
1 6 4 3 9 5 7 8 2
2 8 6 4 7 3 9 1 5
9 1 5 6 8 1 4 2 7
7 9 2 8 1 6 5 4 3
5 4 7 1 6 2 3 9 8
6 2 8 9 5 7 1 3 4
8 3 9 7 4 1 2 5 6
6 7 3 5 2 9 8 6 1
4 5 1 2 3 8 6 7 9
1 6 4 3 9 5 7 8 2
2 8 7 4 6 3 9 1 5
3 1 5 6 8 1 4 2 7
7 9 2 8 1 6 5 4 3
5 4 6 1 7 2 3 9 8
6 2 8 9 5 7 1 3 4
8 3 9 7 4 1 2 5 6
6 7 3 5 2 9 8 6 1
4 5 1 2 3 8 6 7 9
1 6 4 3 9 5 7 8 2
2 8 7 4 6 3 9 1 5
9 1 5 6 8 1 4 2 7
7 9 2 8 1 6 5 4 3
5 4 6 1 7 2 3 9 8
6 2 8 9 5 7 1 3 4
8 3 9 7 4 1 2 5 6
6 7 3 5 2 9 8 6 1
4 5 1 2 3 8 6 7 9
18 Jun 2007, 18:35
Wanda
I’ve been wondering the same question…what’s the secret? I know there’s an easier way. I’m just going to purchase the “Sudoku for Dummies” book and see what comes out of it. One night I spent over 2 hours on one puzzle and almost drove myself nuts.
18 Sep 2007, 18:18
Ok this is odd, I got here via Stumble Upon…
It’s the first time I’ve come across a Warwick Blogs page when I’ve been playing with my “stumble” button in the early hours.
Erm… congratulations?!
10 Apr 2009, 01:54
Add a comment
You are not allowed to comment on this entry as it has restricted commenting permissions.