Whilst I love solving tough Su-Dokus I have a couple of niggling questions in the back of my head about the puzzle.
1. How many ways are there of populating an empty 9*9 grid such that it satisfies the Su-Doku rules?
2. What is the minimum number of clues (cells) required to give a unique solution?
If anyone has the answers (and reasons/calculations) - please let me know!
Thanks
Steveb
Su-Doku's maths
Re: Su-Doku's Maths.
by howshaw » Tue Mar 15, 2005 12:11 am
Steve. I'm working on the "number of puzzles" problem. I think I have the number of valid arrangements of the top three rows, and perhaps the left three columns as well (boxes 1, 2, 3, 4, 7) at around 9x10(19). My approach is to fill row 1 freely (9! = 9x8x7x6x5x4x3x2x1 permutations) and then divide rows two and three into 6 bands. Then work down columns 1 2 and 3 as stacks. I am relying heavily on the symmetry. I don't have the solution in a presentable form yet and I can't get my head around how boxes 5,6,8,9 releate to the others yet. I haven't done this sort of thing for 25 years!
By the way I've found one beautiful looking puzzle...
1 2 3 . 4 5 6 . 7 8 9
4 5 6 . 7 8 9 . 1 2 3
7 8 9 . 1 2 3 . 4 5 6
2 3 4 . 5 6 7 . 8 9 1
5 6 7 . 8 9 1 . 2 3 4
8 9 1 . 2 3 4 . 5 6 7
3 4 5 . 6 7 8 . 9 1 2
6 7 8 . 9 1 2 . 3 4 5
9 1 2 . 3 4 5 . 6 7 8
look at cooresponding cells in each box, top left for example. Follow a diagonal out of one box into another and see that two digits repeat. See the 83 in bold and the 79 in bold-italic and it even wraps at the grid boundary. See the 26 underlined!
The stacks of box 4 (for example) mirror cells 1, 2, 3 of boxes 4, 5, 6 and that reminds me of something about Gaussian-pivioting arrays and determinants. I know the digits are just symbols but I wonder if it might be worth calculating the determinants of puzzles?
By the way I've found one beautiful looking puzzle...
1 2 3 . 4 5 6 . 7 8 9
4 5 6 . 7 8 9 . 1 2 3
7 8 9 . 1 2 3 . 4 5 6
2 3 4 . 5 6 7 . 8 9 1
5 6 7 . 8 9 1 . 2 3 4
8 9 1 . 2 3 4 . 5 6 7
3 4 5 . 6 7 8 . 9 1 2
6 7 8 . 9 1 2 . 3 4 5
9 1 2 . 3 4 5 . 6 7 8
look at cooresponding cells in each box, top left for example. Follow a diagonal out of one box into another and see that two digits repeat. See the 83 in bold and the 79 in bold-italic and it even wraps at the grid boundary. See the 26 underlined!
The stacks of box 4 (for example) mirror cells 1, 2, 3 of boxes 4, 5, 6 and that reminds me of something about Gaussian-pivioting arrays and determinants. I know the digits are just symbols but I wonder if it might be worth calculating the determinants of puzzles?
- howshaw
- Posts: 9
- Joined: 13 March 2005
Minimal Number for Uniqueness
by dfj » Wed Mar 16, 2005 4:15 pm
Does a Sudoku have to have only the minimal number of entries in order to guarentee a unique solution? I have been looking at number 89 from the Times (March 11) and whilst it is unique, if you remove the 9 from r6c7 it still
appears to be unique.
In terms of the number of entries required to guarentee uniqueness, I am not sure if this is a constant figure as it may depend on which cells are chosen.
appears to be unique.
In terms of the number of entries required to guarentee uniqueness, I am not sure if this is a constant figure as it may depend on which cells are chosen.
- dfj
- Posts: 1
- Joined: 16 March 2005
Permutations
by Guest » Thu Mar 17, 2005 8:23 pm
In reply to the first question, this puzzle was set as an Easter competition yesterday by my maths teacher. To cut a long story short (involving one very late night last night), I came up with a solution that has convinced not only me but (so far) my teacher. I won't post the method until it has been checked properly, but in the mean time the answer I came up with was something in the region of 6.47x10^17. I think howshaw is roughly on the same line of thought as I was.
- Guest
by Guest » Mon Mar 21, 2005 9:48 am
Josh - what did your probability grid look like? I followed the same idea, populating from left to right, line by line the number of possibilities for each cell - the first line looks like this (no disputing this):
9 8 7 6 5 4 3 2 1
But I think the next line though looks like this:
6 5 4 6 5 4 3 2 1
This is because the the 1st box all ready has three numbers on the first line. Following the same logic, line 3 looks like this:
3 2 1 3 2 1 3 2 1
This leads to a possibility grid looking like this:
9 8 7 6 5 4 3 2 1
6 5 4 6 5 4 3 2 1
3 2 1 3 2 1 3 2 1
6 6 6 6 5 4 3 2 1
5 5 4 5 5 4 3 2 1
4 4 4 4 4 4 3 2 1
3 3 3 3 3 3 3 2 1
2 2 2 2 2 2 3 2 1
1 1 1 1 1 1 1 1 1
Multiplying these out you get around 1.74 x 10 ^ 33
9 8 7 6 5 4 3 2 1
But I think the next line though looks like this:
6 5 4 6 5 4 3 2 1
This is because the the 1st box all ready has three numbers on the first line. Following the same logic, line 3 looks like this:
3 2 1 3 2 1 3 2 1
This leads to a possibility grid looking like this:
9 8 7 6 5 4 3 2 1
6 5 4 6 5 4 3 2 1
3 2 1 3 2 1 3 2 1
6 6 6 6 5 4 3 2 1
5 5 4 5 5 4 3 2 1
4 4 4 4 4 4 3 2 1
3 3 3 3 3 3 3 2 1
2 2 2 2 2 2 3 2 1
1 1 1 1 1 1 1 1 1
Multiplying these out you get around 1.74 x 10 ^ 33
- Guest
by Guest » Mon Mar 21, 2005 7:02 pm
I disagree with the second line
The grid starts 9 8 7 6 5 4 3 2 1, but the second line is not
6 5 4 6 5 4 3 2 1. The second 6 can't be right since there may not be 6 choices available (depending on the choices in the first 6 5 4 box it could be as little as 3)
The grid starts 9 8 7 6 5 4 3 2 1, but the second line is not
6 5 4 6 5 4 3 2 1. The second 6 can't be right since there may not be 6 choices available (depending on the choices in the first 6 5 4 box it could be as little as 3)
- Guest
- Posts: 312
- Joined: 25 November 2005
by Guest » Mon Mar 21, 2005 9:15 pm
I wondered about that - it is one possibility, but it is also possible that the first three cells don't eliminate any possibilites from the second box.
So, to catch all possibilities, it has to be a six. What would you have put on the second line?
PS you didn't leave a name - is it Josh again?
So, to catch all possibilities, it has to be a six. What would you have put on the second line?
PS you didn't leave a name - is it Josh again?
- Guest
by Guest » Wed Mar 23, 2005 3:19 am
Well, it certainly can't be both, or others, it has to be something!
Thinking a bit harder about it, the possibilities are that the first three cells on row 2 include 0,1,2 or 3 of the top 3 in box 2. This gives four possibilities for the matrix on the second line:
a) 6 5 4 3 2 1
b) 5 4 3 4 3 2
c) 4 3 2 5 4 3
d) 3 2 1 6 5 4
the middle two multiply out to 1440, and the other two to 720, so to get the highest number of prossibilities, I think the first three boxes looks like this
9 8 7 6 5 4 3 2 1
5 4 3 4 3 2 3 2 1
3 2 1 3 2 1 3 2 1
I still think I'm missing a trick though. I'm half wondering if you actually need to add together the possibilities from four boxes, each with the second line starting with one of the above options. This would also need to be done for the other points of conflict (e.g. where I put 6 6 6 on row 4).
However you do it - it's a big number!
Thinking a bit harder about it, the possibilities are that the first three cells on row 2 include 0,1,2 or 3 of the top 3 in box 2. This gives four possibilities for the matrix on the second line:
a) 6 5 4 3 2 1
b) 5 4 3 4 3 2
c) 4 3 2 5 4 3
d) 3 2 1 6 5 4
the middle two multiply out to 1440, and the other two to 720, so to get the highest number of prossibilities, I think the first three boxes looks like this
9 8 7 6 5 4 3 2 1
5 4 3 4 3 2 3 2 1
3 2 1 3 2 1 3 2 1
I still think I'm missing a trick though. I'm half wondering if you actually need to add together the possibilities from four boxes, each with the second line starting with one of the above options. This would also need to be done for the other points of conflict (e.g. where I put 6 6 6 on row 4).
However you do it - it's a big number!
- Guest
by Guest » Fri Mar 25, 2005 1:37 pm
Hi IJ,
I have been thinking about this problem on and off for a couple of days now, and still don't have a definite answer.
I think your idea of calculating branching probability is a workable one provided we use a computer, because you really need to keep track of the branches which have implications for later probabilities.
I have also tried the elimination method: in total there are 9^81 possible grid layouts; the chance of 1st column satisfying sudoku rule is 9! / 9^9 and you can do this for all other columns and rows in total 18 times. This gives
9^81 * (9!/9^9)^18=6x10^22
which is clearly an upper bound as we still need to incorporate the box constraint. The trouble here is, (9!/9^9)^9 would be an overkill for the box constraints, leading to a the result that is less than 1! At this point, I don't know how to do the box constraints properly. Any ideas?
I have been thinking about this problem on and off for a couple of days now, and still don't have a definite answer.
I think your idea of calculating branching probability is a workable one provided we use a computer, because you really need to keep track of the branches which have implications for later probabilities.
I have also tried the elimination method: in total there are 9^81 possible grid layouts; the chance of 1st column satisfying sudoku rule is 9! / 9^9 and you can do this for all other columns and rows in total 18 times. This gives
9^81 * (9!/9^9)^18=6x10^22
which is clearly an upper bound as we still need to incorporate the box constraint. The trouble here is, (9!/9^9)^9 would be an overkill for the box constraints, leading to a the result that is less than 1! At this point, I don't know how to do the box constraints properly. Any ideas?
- Guest
by Guest » Sat Mar 26, 2005 12:32 pm
Interesting. How about this...
All the rows in insolation give you 9 * 9! possibilities
Now, considering columns can only reduce this number, so col 1 at the moment has 9^9 possibilities (column one will be 999999999), but only 9! are valid, so that gives you...
(9* 9!) - (9^9-9!) which rationalises to
(10*9!)- (9^9)
Column two has 8^9 possibilities so we need to take off 8^9 - 9!...
(11*9!) - (9^9) - (8^9)
So, I think rows and columns alone would give you
(18*9!)-(9^9)-(8^9)-(7^9)-(6^9)-(5^9)-(4^9)-(3^9)-(2^9)-9
Oh bugger, that's negative too!
OK, how about this, start with this grid:
987654321
876543219
765432198
654321987
543219876
432198765
321987654
219876543
198765432
This is consistent for rows and columns, so you only need to worry about boxes:
So how many possibilities are there in the top box: at the moment 9*8^2*7^3*6^2*5, and how many can actually be valid? 9!, of course, which is true for all the boxes. So that doesn't go anywhere either.
Actually, I don't see any sensible answer other than 9*9!. I'm beginning to think this is a self-cancelling problem. By that I mean that although two adjacent boxes, rows or columns with possibilities of 9! seems contradictory, in fact it may not be - consider the first three rows, that might look like this:
987987987
543543543
321321321
Although the first row is over egged (this is way over the actual 9! possibilities) the third line is under-egged. Maybe this balance achieves the right answer.
What do you think?
All the rows in insolation give you 9 * 9! possibilities
Now, considering columns can only reduce this number, so col 1 at the moment has 9^9 possibilities (column one will be 999999999), but only 9! are valid, so that gives you...
(9* 9!) - (9^9-9!) which rationalises to
(10*9!)- (9^9)
Column two has 8^9 possibilities so we need to take off 8^9 - 9!...
(11*9!) - (9^9) - (8^9)
So, I think rows and columns alone would give you
(18*9!)-(9^9)-(8^9)-(7^9)-(6^9)-(5^9)-(4^9)-(3^9)-(2^9)-9
Oh bugger, that's negative too!
OK, how about this, start with this grid:
987654321
876543219
765432198
654321987
543219876
432198765
321987654
219876543
198765432
This is consistent for rows and columns, so you only need to worry about boxes:
So how many possibilities are there in the top box: at the moment 9*8^2*7^3*6^2*5, and how many can actually be valid? 9!, of course, which is true for all the boxes. So that doesn't go anywhere either.
Actually, I don't see any sensible answer other than 9*9!. I'm beginning to think this is a self-cancelling problem. By that I mean that although two adjacent boxes, rows or columns with possibilities of 9! seems contradictory, in fact it may not be - consider the first three rows, that might look like this:
987987987
543543543
321321321
Although the first row is over egged (this is way over the actual 9! possibilities) the third line is under-egged. Maybe this balance achieves the right answer.
What do you think?
- Guest
by Guest » Wed Mar 30, 2005 6:08 pm
A quick calculation suggests that the number of ways of filling the top 3 rows is 948019639680. Here's how I've got this (I hope it's right!):
There are 9! = 362880 possible top rows. Choose one, 123456789, say, and then we'll need to multiply the answer by 9!.
As has been remarked already, the number of options after this depends on what three numbers are beneath the 123. We'll get a different answer if the three numbers are 456 or 789 (in some order), than if they are mixed (e.g., 457 etc.).
123 456 789
[456] xxx xxx
xxx xxx xxx
can be fillied in as:
123 456 789
[456][789][123]
[789][123][456]
where [456] means "write in 4, 5 and 6 in some order". There are 6 arrangements for each of the 6 [xyz], making 6^6 arrangements so far. If the block below 123 is [789], the answer is the same. There are therefore 2*6^6 = 93312 such possibilities.
The other possibility occurs when the numbers below 123 are something like 457. (There are 18 choices of three numbers from 456 789, not including 456 and 789 already accounted for.) Let's choose [457] and multiply the final answer by 18. Then the grid is fillied in:
123 456 789
[457][89a][6bc]
[689][7bc][45a]
where a, b and c are 1, 2 and 3 in some order. Each of the [xyz] again
has 6 possible arrangements. We have to multiply by an additional factor of 3 to account for the choice of a being 1, 2 or 3. In total, we get 18*(6^6)*3 = 2519424 possibilities of this shape.
All this gives a total of
9! * (6^6) * (2 + 18*3) = 948019639680 possibilities,
if I've got this right.
Frazer
There are 9! = 362880 possible top rows. Choose one, 123456789, say, and then we'll need to multiply the answer by 9!.
As has been remarked already, the number of options after this depends on what three numbers are beneath the 123. We'll get a different answer if the three numbers are 456 or 789 (in some order), than if they are mixed (e.g., 457 etc.).
123 456 789
[456] xxx xxx
xxx xxx xxx
can be fillied in as:
123 456 789
[456][789][123]
[789][123][456]
where [456] means "write in 4, 5 and 6 in some order". There are 6 arrangements for each of the 6 [xyz], making 6^6 arrangements so far. If the block below 123 is [789], the answer is the same. There are therefore 2*6^6 = 93312 such possibilities.
The other possibility occurs when the numbers below 123 are something like 457. (There are 18 choices of three numbers from 456 789, not including 456 and 789 already accounted for.) Let's choose [457] and multiply the final answer by 18. Then the grid is fillied in:
123 456 789
[457][89a][6bc]
[689][7bc][45a]
where a, b and c are 1, 2 and 3 in some order. Each of the [xyz] again
has 6 possible arrangements. We have to multiply by an additional factor of 3 to account for the choice of a being 1, 2 or 3. In total, we get 18*(6^6)*3 = 2519424 possibilities of this shape.
All this gives a total of
9! * (6^6) * (2 + 18*3) = 948019639680 possibilities,
if I've got this right.
Frazer
- Guest
