Su-Doku's maths

Everything about Sudoku that doesn't fit in one of the other sections

Postby Guest » Thu Mar 31, 2005 11:12 am

In reply to afj,
This was how i started off - taking the numbers in triplets (under letters abcdefghi to make it a little more maths-y) and finding the combinations. However, in my original method i forgot that a, b and c don't all have to be on the same line all the time! So, i refined this a little further, but still ended up never having, for example, a on top of b. I've tinkered a little further, but it always ends up as a number of digits having either x or y places to go depending on where other digits have gone, so it requires a lot more thought from me.
I have heard of someone using a Monte Carlo algorithm on a supercomputer for 20 days and coming up with an answer in the region of 6x10^21 (so i wasn't too far off!). A teacher was going to try and 'borrow' supercomputer time over the holidays (long story...) and use his own algorithm to come up with an answer, but i'm not sure how successful he will have been in procuring the computer!
I will try and give this some more thought (haven't done so since my other post - no, the guest wasn't me - because of other, more important but less interesting, schoolwork and revision for exams) and get back to you all when i have.
If we solve this algebraically (ie not using algorithms on very very powerful computers), what's the chance of, say, The Times giving us a mention?
J
Guest
 

Postby Guest » Fri Apr 01, 2005 6:11 pm

I suspect that these "brute-force" counting methods are going to be difficult to push far enough to get the full answer, although I might see how far I can get this weekend. Another method would be to start with one fixed solution, such as that given by howshaw, and find a sequence of transformations which allow any solution to be reduced to this fixed one. (For example, applying any permutation of the first three rows to any solution will again give a valid solution.) Then one should form the "group" of all these transformations, and use a computer to work out its size. It's not too difficult to find quite a few transformations which take a valid Sudoku to another valid Sudoku, but I've completely failed to show that these generate all valid Sudokus from a given one.

Incidentally, the number of 9x9 "Latin squares", that is, grids with a 1-9 in each row and column (but not counting the 3x3 boxes) was computed by Bammel and Rothstein in 1975 as 5524751496156892842531225600, about 5 x 10^27; this is therefore an upper bound for the possible valid Sudoku puzzles. I'll see if I can get hold of the relevant documents and whether it might be possible to adapt the method...

Frazer
Guest
 

Re: Su-Doku's maths

Postby Guest » Tue Apr 05, 2005 8:45 pm

2. What is the minimum number of clues (cells) required to give a unique solution?
I think it"s 0 because at school befor Christmas we had a 9x9 grid Sudoku puzzle which was empty and we had to fill it like Sudoku puzzle and I was one of the people who filled it completly. Of cource that's only what I think. Other people might have other suggustions.



a big maths and puzzle fan, Saba [/quote]
Guest
 
Posts: 312
Joined: 25 November 2005

Postby Sue De Coq » Wed Apr 06, 2005 8:57 am

The minimum number of cells required on a valid 3x3 Su Doku puzzle is probably 18 or 19. It's certainly posible to create a symmetric puzzle with a unique solution attainable through 'pure logic' with 19 cells - I've created many personally - but I remember an interview with Wayne in The Times in which he claimed to have heard of somebody who had created a puzzle with 18 cells, though Wayne hadn't seen the puzzle. Of course, it would be difficult to prove that, for instance, it's impossible to create a puzzle with 17 cells - the figures 18 and 19 are the concensus view of various experienced puzzle-makers.

The problem with the 0-cell puzzle is that it has many, many solutions - as the remainder of the topic makes clear. It's wonderfully symmetric, though!
Sue De Coq
 
Posts: 93
Joined: 01 April 2005

Postby Guest » Fri Apr 08, 2005 7:51 pm

Suggestions to aid in determining the number of possible unique solutions:

Box1 (upper left) can be populated in 9! ways
Box5 (centre) can be then be populated in 9! ways, independently of Box1 above, as there are no rules common to both.
Box9 (lower right) can be populated in 9! waysby the same logic.

Therefore there are (9!)^3 independant ways to fill boxes 1,5 and 9.

By symmetry, the number of ways to fill boxes 2, 4, 7, and 8 will be equal to each other. Let's call this value C. So we have C^4*(9!)^3 ways to fill boxes 1,2,4,5,6,8, and 9.

Once you have only boxes 3 and 7 to fill, there can only be 1 (trivial)unique way to do it.

Therefore, the overall number of unique solutions is C^4*(9!)^3. All that is left is to determine C.
Guest
 
Posts: 312
Joined: 25 November 2005

Number of possible grids

Postby tannedblondbloke » Sat Apr 09, 2005 10:03 am

How many possible grids are there?

Here's my attempt.

First we consider block 5; then blocks 4 and 6; then blocks 2 and 8; then blocks 1, 3, 5 and 7.

1 - Block 5
In filling in block 5, there are no constraints, and clearly we can fill it in any of 9! ways. For the rest of this post, I will assume this block is filled out as below, as we can go from any grid to one looking like this by relabelling:

123
456
789

How many ways are there of filling blocks 4 and 6? Well, let's consider the rows and columns of blocks 4 and 6 separately - rows first.

2 - Rows of Blocks 4 and 6
In block 4, all numbers must be shifted up a row or down a row (ordering the rows cyclicly, up from row 4 is row 6, and down from row 6 is row 4) as numbers can't occupy a row in block 4 if they occupy that row in block 5. And whatever shift applies in block 4, the opposite shift applies in block 6 (if number 5 is shifted up to row 4 in block 4, it must be shifted down to 6 row in block 6) by applying the same constraint to blocks 4 and 6.

Let's consider then what happens to numbers 4, 5, and 6. We only need count what happens in block 4 as we know the opposite happens in block 6. For each, there are two choices - shift up or shift down - so 2x2x2=8 choices in total. In 2 of these choices, 4, 5 and 6 are all shifted in the same direction (up or down); in the other 6, one is shifted one way and two the other.

Suppose 4, 5 and 6 are all shifted to row 4; where can 7, 8 and 9 go? Well, they can't remain in row 6, and because row 4 is occupied, they can't go there. So they are forced up into row 5, and 1, 2 and 3 are shifted up into row 6. So all the row choices are forced. By symmetry a similar argument applies if 4, 5 and 6 are shifted down.

Now suppose 4 and 6 are all shifted up and 5 is shifted down. Where can 7, 8 and 9 go? Well, they can't remain in row 6, and 2 cells in row 4 are occupied. One could go to row 4, but the other two have to go to row 5. What about 1, 2 and 3? They can't remain in row 4, and two cells in row 5 are occupied, so two of them must go to row 6, which along with number 5 is now fully occupied. So of 7, 8 and 9, exactly two shift up and one down, and of 1, 2 and 3, exactly two shift up and one down. So we need to choose one of 1, 2 and 3, and one of 7, 8 and 9 to move down, and the rest of those numbers move up.

To recap - with block 5 fixed, there are 2+(6x9)=56 ways of assigning numbers to rows in block 4 - just work out what happens to numbers 4, 5 and 6 (up or down, for 8 choices) - in 2 of those 8, they are all shifted the same way and indeed all 9 numbers are shifted that way. In the other 6 choices, one of 4, 5 and 6 move opposite to the others, and we must also pick an opposite mover out of each of {1,2,3} and {7,8,9}. And having made these choices, the assignment of numbers to rows in block 6 are forced.

3 - Columns of Blocks 4 and 6
In block 4, we have assigned 3 numbers to row 4, 3 to row 5, and 3 to row 6. Within each row, there is no constraint - we can assign those numbers to columns arbitrarily. So for each row there are 6! choices to be made, ie (6!)^3 in total. The same applies to block 6.

Taking steps 1, 2 and 3 together, there are 9! x 56 x (6!)^6 ways of populating blocks 4, 5 and 6.

4 - Blocks 2 and 8
By the same argument, all numbers in block 2 are shifted left or right in block 2, relative to their position in block 5, and the opposite applies to block 8 - we simply consider what happens to numbers 2, 5 and 8, and what that forces on each of {1,4,7} and {3,6,9} and come up with 56 ways of assigning numbers to columns in block 2 (which forces assignments to columns in block 8). Numbers can be assigned to rows freely.

So we have 9! x 56^2 x (6!)^12 ways of assigning numbers to blocks 2, 4, 5, 6 and 8.

5 - Blocks 1, 3, 7 and 9
In block 1, all numbers are shifted up or down relative to their position in block 2, and the opposite shift applies to block 3. We have 56 choices as before.

In block 7, all numbers are shifted up or down relative to block 8, and the opposite shift applies to 9 - 56 choices again.

In block 1, all numbers are shifted left or right relative to their position in block 4, and the opposite now applies to 7 - 56 choices.

Finally, in block 3, all numbers are shifted left or right relative to block 6, and opposite applies to 9 - 56 choices

So the final number of choices is 9! x 56^6 x (6!)^12 = 217,210,668,439,560,000,000,000,000,000,000,000,000,000,000,000,000
tannedblondbloke
 
Posts: 16
Joined: 09 April 2005

Postby Guest » Sat Apr 09, 2005 6:10 pm

Tannedblondbloke,

I read this carefully, and the basic method seemed to make sense, but I think the maths has gone awry somewhere.

The number of possibilities for 3 boxes can't be more then 9!^3... If three boxes could be populated with no restrictions, then maximum number of combinations is 9!^3, but the rows place restrictions, and so must reduce this number. Your figure of 9!x56x6!^6 is around 3 billion times bigger!

In fact, the total figure cannot be more than 9!^9 (the possibilities for unrestricted population of 9 rows, columns or boxes), which is about half your final answer.

The question is how much less is it? How many of those 9!^9 are invalid?
Guest
 

Sorry, good spot

Postby tannedblondbloke » Sat Apr 09, 2005 7:34 pm

I am a muppet. Well spotted IJ.

Everywhere I wrote 6!, I really meant 6, ie 3!

So the answer is 9! x 56^6 x (3!)^12 = 24,361,621,955,711,200,000,000,000

Does that look more reasonable?

Enjoying this Soduko lark. Never tried it before last Saturday, and after seeing people at the office doing it, bought the book last Sat, and from there discovered this website. Between doing puzzles, I'm finding time to think about some of the maths, and am writing a solver in XL VBA as an intellectual challenge - I must get out more!:D
tannedblondbloke
 
Posts: 16
Joined: 09 April 2005

Re: Sorry, good spot

Postby RFB » Sat Apr 09, 2005 11:13 pm

tannedblondbloke wrote:I must get out more!:D

Especially if you want your id to remain accurate:D
RFB
 
Posts: 43
Joined: 03 April 2005

Postby Guest » Sun Apr 10, 2005 7:10 pm

TBB (Hope you don't mind the informality!),

Yes - it feels like a better sized number, but whether it's the right or not I'll leave for those with bigger brains than I!

I wrote my solver in XL VBA too - be careful, it becomes an obsession! If you haven't found it, it's worth reading through the "Solving Mechanically" thread on this site. Milobird and I came up with 3 rules that will solve every Times Puzzle. In fact these can be reduced to just two, as two of the three are basically inverses of each other...
Guest
 

Solver

Postby tannedblondbloke » Sun Apr 10, 2005 11:45 pm

IJ wrote:TBB (Hope you don't mind the informality!),

Yes - it feels like a better sized number, but whether it's the right or not I'll leave for those with bigger brains than I!

I wrote my solver in XL VBA too - be careful, it becomes an obsession! If you haven't found it, it's worth reading through the "Solving Mechanically" thread on this site. Milobird and I came up with 3 rules that will solve every Times Puzzle. In fact these can be reduced to just two, as two of the three are basically inverses of each other...


Yeah I saw that - I'd kind of deduced a "pairs" version of a couple of these but hadn't really formalised a general case, and certainly hadn't realised the inverse point..

At the moment I've only programmed up simple versions of the 2 invese rules - ie if a candidate can only go in one cell in a unit, or if a cell has only one feasible candidate. But it's surprising how many Difficult cases from the book it will solve (in well under one second). I can use manual intervention to manually apply the more complex rules to a partial solution, and start it running again. I'll try to handle the general case next weekend.

However, it seems there are other esoterica out there, which given your comment about solving everything in the Times, suggests that in general additional algorithms are needed for puzzles worse than fiendish - I saw some stuff about XWings, Nishio and Swordfish which I've not really thought about. One step at a time!
tannedblondbloke
 
Posts: 16
Joined: 09 April 2005

Postby Guest » Thu Apr 14, 2005 2:52 pm

tanndedblondbloke:

I am not sure if I agree with your answer for the number of unique solutions. I arrived at a different answer using a slightly different approach, and I cannot see a hole in my logic. But I also cannot see a hole in yours. Maybe you can help resolve this for me:

Step A:
Blocks 1, 5 and 9 can each be independently filled 9! ways, as they have no rules in common, for 9!^3 ways altogether.

Step B:
With Blocks 1 and 5 filled, there are 56 ways to fill the rows of block 2, and 56 ways to fill the columns of block 2, using identical logic as you used to fill block 1 in your step 5. So there must be 56^2 ways to fill block 2.

Symmetry says that there are 56^2 ways to fill block 4.

So we now have 9!^3 * 56^4 ways to fill blocks 1,2,4,5, and 9.

Step C:
With blocks 1 and 4 filled, there is only one way to choose which numbers go in the columns of block 7. With block 9 filled, there are only two unique ways to place one of the numbers in each column. Once one of the numbers is placed, the other two are forced. So each of the three columns has 2 ways to be filled, so there are 2^3 ways to fill block 7. By symmetry, there must be 2^3 ways to fill block 3.

So far , we have 9!^3 * 56^4 * 2^6 ways to fill blocks 1,2,3,4,5,7, and 9.

Step D:
This one is pretty straightforward. With only blocks 6 and 8 to fill, there can be only one unique way to fill them.

Bottom Line: I assert that there are S2 = 9!^3 * 56^4 * 2^6 ways to uniquely fill a 9x9 soduku puzzle.

You assert that there are S1 = 9! * 56^6 * 6^12 solutions.

Reducing to common factors:
9! = 2 * 3 * 2^2 * 5 * 2*3 * 7 * 2^3 * 3^2 = 2^7 * 3^4 * 5 * 7
56 = 2^3 * 7

S1 = (2^7 * 3^4 * 5 * 7) x (2^18*7^6) x (2^12*3^12)
S1 = 2^37 * 3^16 * 5 * 7^7
S1 = 2.4362 * 10^25

S2 = (2^21 * 3^12 * 5^3 * 7^3) x (2^12*7^4) x (2^6)
S2 = 2^39 * 3^12 * 5^3 * 7^7
S2 = 3.0076 * 10^25

These are very close results, but rely on quite different combinatory factors, which seems very wrong. Yet I cannot find a flaw in your or my reasonings.
Guest
 
Posts: 312
Joined: 25 November 2005

Postby Guest » Thu Apr 14, 2005 4:05 pm

I'm not sure about your 56^2 in step B.

I'm assuming the 56 combinations based on the rows comes from the constraints made by box 1. If this is so, then surely this number must be reduced by the constraints made by box 4, not increased?
Guest
 

Postby Guest » Thu Apr 14, 2005 7:09 pm

IJ: I was the'guest' from the post above.

Read tannedblondeblock's solution above. He (in great detail) shows why there are 56 ways to fill a row or column within a block when there is another full block constraining the choices. I am simply stealing his result of 56 (and therefore 56^2) in my method.


=============================================


BTW, I see a possible reason why our two answers vary, and it is a fundamental problem with my solution.

It is quite easy to construct a partial solution with blocks 1,2,3,4,5,8, and 9 filled using my method, and arrive at a point where NO value can be filled into one or more cells of blocks 3 or 7 because, for that cell, the twelve numbers already filled in on the same row/column of the other blocks represent all of the 9 numbers already.

Hmmm.
Guest
 

I need to think about this

Postby tannedblondbloke » Fri Apr 15, 2005 6:28 am

I need to think about this - however, I agree with your step B.

tinfoil wrote:IJ: I was the'guest' from the post above.

Read tannedblondeblock's solution above. He (in great detail) shows why there are 56 ways to fill a row or column within a block when there is another full block constraining the choices. I am simply stealing his result of 56 (and therefore 56^2) in my method.


=============================================


BTW, I see a possible reason why our two answers vary, and it is a fundamental problem with my solution.

It is quite easy to construct a partial solution with blocks 1,2,3,4,5,8, and 9 filled using my method, and arrive at a point where NO value can be filled into one or more cells of blocks 3 or 7 because, for that cell, the twelve numbers already filled in on the same row/column of the other blocks represent all of the 9 numbers already.

Hmmm.
tannedblondbloke
 
Posts: 16
Joined: 09 April 2005

PreviousNext

Return to General