# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Message body

 Emoticons View more Emoticons
 [quote="lostdummy"]I think solution is 9!*6!*6!*3!*3!*3! [/b], or around 10^13 Way I got to this number is to see in how many ways we can chose numbers starting from one corner, for example top left corner: 9 8 7 6 5 4 3 2 1 6 5 4 3 2 1 3 2 1 6 3 - 3 2 1 5 2 4 1 3 2 1 For top row in top left box, 987 means we can chose all 9 numbers for first position, but only 8 for second (since 1st number is chosen in same row), and one less for 3rd (so 7). Second row in same box is already limited by those 3 selected numbers ans start from 6 (so 654), and same for third row (321). For top middle box, upper row continue as 654 (limited by 3 numbers in same row in first box), but second row is now constrained both by those 3 numbers in this box and also by 3 numbers in left box, so it starts from 3 (321), and rest is forced (1). Top right box start from 3 in upper row , since there are already 6 numbers in upper row, so 321, and rest is forced. BTW, all empty spaces are also forced (so "1"). Same logic is applied to left middle box (only vertically), then left bottom box. Interesting is middle box, where we still can make combinations - first number is constrained by 3 numbers above it and 3 to left, so it starts at 3 (321). Rest is forced. That result in picture as above, and number 9!*6!*3! (horizontal top boxes) * 6!*3! (vertical left boxes) * 3!(middle box)= 9!*6!*6!*3!*3!*3! BTW, I did not consider symmetries here to get "number of unique sudokus" - this is solution for total number of valid sudokus. *EDIT* After some thought, there could be problem with this solution. For example, in second row of top middle box (321), it is not clear that first position have only 3 possible values, since numbers in upper row of that box can duplicate with some or all of 3 numbers in row to left and that would leave 6 possible choices in such case ... or still only 3 choices if numbers do not duplicate.[/quote]
Options
HTML is OFF
BBCode is ON
Smilies are ON
 Disable BBCode in this post Disable Smilies in this post

 All times are GMT
 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
 Topic review
Author Message
Thok*
Posted: Tue Aug 30, 2011 9:44 pm    Post subject: 1

lostdummy wrote:
Thok* wrote:
These 20+20+5=45 ways are close to 125/3=41 2/3.

Nice example, and it makes good point - although sudoku case is still about 1550 times more "weird" (at 0.005% difference) than above example ( at 8% difference) ;p

1/9! is a much smaller number than 1/3
lostdummy
Posted: Tue Aug 30, 2011 10:53 am    Post subject: 0

Thok* wrote:
These 20+20+5=45 ways are close to 125/3=41 2/3.

Nice example, and it makes good point - although sudoku case is still about 1550 times more "weird" (at 0.005% difference) than above example ( at 8% difference) ;p
Thok*
Posted: Mon Aug 29, 2011 10:01 pm    Post subject: -1

lostdummy wrote:
I would expect either much more duplications between symbol permutations and other symmetry cases (as L'lanmal suggested) or no duplications, but such very small and yet existing number I did not expect ;p

That's less weird then you think. Consider the number of ways to color the points of a triangle with 5 colors up to rotation. There are 125=5^3 ways, ignoring rotation. These break up into 5*4*3/3=20 ways to color with three different colors, 5*4=20 ways to have ways to use two colors, and 5 ways to use one color. These 20+20+5=45 ways are close to 125/3=41 2/3.

Basically, it's hard to have extra symmetries that fix a pattern, but it can and does happen a small portion of the time.
Zag
Posted: Mon Aug 29, 2011 12:28 pm    Post subject: -2

That little bit of difference sounds more like a rounding error to me.
lostdummy
Posted: Mon Aug 29, 2011 8:35 am    Post subject: -3

Thok wrote:
6670903752021072936960
... Wikipedia claims the number of 16x16 sudokus (with 16 4x4 squares) is still an open problem.

Ah, once you mentioned wikipedia, I found this link, that explain fairly well current numbers about sudoku, and even how they got to total number:

http://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerating_all_possible_Sudoku_solutions

But I still find one thing strange: they state 6,670,903,752,021,072,936,960 total sudokus, and also state 5,472,730,538 "unique" sudokus, while confirming that my guess was correct about number of symmetry cases (3,359,232) and also confirming they use what L'lanmal suggested as conjugation (with all 9! = 362,880 permutations of symbols).

And if we divide Total/Symmetries/Conjugations, we get VERY close but not IDENTICAL to their number of unique sudokus: dividing result in some 5,472,447,994 and that is different to stated 5,472,730,538 "unique" sudokus.

That would suggest that using permutations of symbols result in almost no duplications, with key word "almost" - it still suggest some 0.00005% of duplications.

I would expect either much more duplications between symbol permutations and other symmetry cases (as L'lanmal suggested) or no duplications, but such very small and yet existing number I did not expect ;p
Thok
Posted: Sat Aug 27, 2011 2:14 am    Post subject: -4

6670903752021072936960

Gotten by using Sloane's integer series page

The general problem is fairly wild: once you factor the obvious factors, there isn't much structure. Wikipedia claims the number of 16x16 sudokus (with 16 4x4 squares) is still an open problem.
L'lanmal
Posted: Fri Aug 26, 2011 5:59 pm    Post subject: -5

The most natural transformation I can think of on a sudoku is conjugation. (e.g. Replace all 1s with 9s and all 9s with 1s.) This does not change the structure what-so-ever (or influence the reasoning needed to solve one), just the labeling conventions.

I imagine this will overlap greatly with rearranging rows and columns.
lostdummy
Posted: Thu Aug 25, 2011 2:55 pm    Post subject: -6

I did some counting on how many there are different transformations from those listed above, and it turns out there are 2*3!^8 (=3,359,232) of those.

In fact, I found that following transformations from my above list duplicate with each other:
- vertical mirroring is subset of combination of vertical box and column transformations
- horizontal mirroring is subset of combination of horizontal box and row transformations
- rotation by 2 or 3 is combination of rotate by 1 and above horiz/vert box/row transformations

So reduced list of valid non duplicated transformations is:
- (2) rotate to right by 90 degrees
- (3!) permutations of whole vertical box groups
- (3!) permutations of whole horizontal box groups
- (3!*3!*3!) permutation of 3 vertical columns within each of 3 vertical box groups
- (3!*3!*3!) permutation of 3 horizontal rows within each of 3 horizontal box groups

That means if we apply all those transformation on unique sudoku position, it will result in 2*3!^8 (=3,359,232) sudokus.

Of course, that presume only those transformations that I listed before - maybe someone can think of some other transformation that would result in non-duplicated valid sudokus ;p
lostdummy
Posted: Thu Aug 25, 2011 10:14 am    Post subject: -7

Heh, my last sentence from previous post started me thinking on this "symmetry" problem:

What is exactly symmetry, and why would we consider it at all here?

Common sense response would be that if we can create new valid sudoku from existing one by just applying mirroring or rotating, we could consider those to be "same" and not count in number of "unique" sudoku puzzles.

Now, in that "common sense" definition key word is "unique", and that would mean here : "can not be derived from other unique sudoku with some transformation"

And again, key word there is "transformation" - clearly mirroring and rotating are such transformations, but are they all ?
As I mentioned, just doing permutation of vertical 3x3 boxes will also result in valid sudoku. Is such transformation also as valid as mirroring here?
And where do we stop?Computer program who is searching all possible sudokus starting from one "unique" sudoku position is also transformation.

Probably some common sense approach would be to say that only "easy or straightforward" transformation are valid to determine uniqueness, but that is too subjective definition. One definition that could be more precise would be:
Any transformation that can be defined just by changing position of any of 9x9 cells

That means if we label every cell in 9x9 grid with number 1 to 81 (1 top left, 9 top right, 81 bottom right), then we can say that for example mirroring across vertical line will put number from original cell 1 at new cell 9, 2 at 8 ... 73 at 81 etc.

Therefore vertical mirroring can be described by list of 81 numbers, each defining where "original" number from that cell will end up ( in above example: 9,8,7,6,5,4,3,2,1,18,17...81,80,79,78,77,76,75,74,73)

Clearly computer program searching all sudokus can not be described in such way, so it does not count as valid "transformation". But bonus question here is:

What are all valid transformation for sudoku, and how much they would reduce number of unique solutions?

Some of transformations that I saw so far:
2x vertical mirroring
2x horizontal mirroring
4x rotations
3!x permutations of whole vertical box groups
3!x permutations of whole horizontal box groups
3!*3!*3!x permutation of 3 vertical columns within each of 3 vertical box groups
3!*3!*3!x permutation of 3 horizontal rows within each of 3 horizontal box groups

Now, most of those transformations are multiplicative, meaning we can apply both vertical mirroring and one rotation, or permutation and rotation etc... so total number of "derived" sudokus from one "unique" sudoku would be close to multiply of all of above.

So just going by those numbers listed, it would mean that one unique sudoku can generate 2*2*4*6*6*6*6*6*6*6*6 derived sudokus.

BUT some permutations when combined can get same end result. For example, multiplied 2x horizontal mirroring and 2x vertical and 4x rotations suggest total of 16 derived (including one unique) sudokus, but rotate twice get same result as mirror vertical and horizontal, or rotate three times and mirror vertical gets same result as rotate once and mirror horizontal etc .. so total number of different derived sudokus using both mirrorings and rotates is actually 8 .

I dont know if other listed transformations above also have similar duplication effects, or if in fact those are all valid transformations. IF they were, number of derived sudokus from one unique would be around 8*6^8, and number of "unique" sudokus would be 9!*6!*6!*3!*3!*3! / (8*3!*3!*3!*3!*3!*3!*3!*3!*) = 9!*6!*6!/(8*6^5) = 3024000

BUT I suspect that number is not correct, ie I suspect that both some of other transformations mentioned above when applied in combination get duplicated results similar to mirror/rotate (which when corrected would reduce number of derivations from one unique sudoku and increase total number of unique sudokus) , and also its possible that some other transformation that I did not think about exists (which then would inclrease number of derivations and reduce number of unique sudokus)
lostdummy
Posted: Thu Aug 25, 2011 8:10 am    Post subject: -8

I think solution is 9!*6!*6!*3!*3!*3! [/b], or around 10^13

Way I got to this number is to see in how many ways we can chose numbers starting from one corner, for example top left corner:

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

For top row in top left box, 987 means we can chose all 9 numbers for first position, but only 8 for second (since 1st number is chosen in same row), and one less for 3rd (so 7). Second row in same box is already limited by those 3 selected numbers ans start from 6 (so 654), and same for third row (321).
For top middle box, upper row continue as 654 (limited by 3 numbers in same row in first box), but second row is now constrained both by those 3 numbers in this box and also by 3 numbers in left box, so it starts from 3 (321), and rest is forced (1). Top right box start from 3 in upper row , since there are already 6 numbers in upper row, so 321, and rest is forced. BTW, all empty spaces are also forced (so "1").

Same logic is applied to left middle box (only vertically), then left bottom box.

Interesting is middle box, where we still can make combinations - first number is constrained by 3 numbers above it and 3 to left, so it starts at 3 (321). Rest is forced.

That result in picture as above, and number 9!*6!*3! (horizontal top boxes) * 6!*3! (vertical left boxes) * 3!(middle box)= 9!*6!*6!*3!*3!*3!

BTW, I did not consider symmetries here to get "number of unique sudokus" - this is solution for total number of valid sudokus.

*EDIT* After some thought, there could be problem with this solution. For example, in second row of top middle box (321), it is not clear that first position have only 3 possible values, since numbers in upper row of that box can duplicate with some or all of 3 numbers in row to left and that would leave 6 possible choices in such case ... or still only 3 choices if numbers do not duplicate.
LordKinbote
Posted: Wed Aug 24, 2011 1:19 am    Post subject: -9

groza528 wrote:
I came up with this question yesterday. I don't know the answer. Frankly, the answer doesn't interest me terribly, but the solution does... I want to know if there is an elegant way to arrive at a numerical answer. Just to satisfy my own curiosity.

How many legal solutions are there to a blank sudoku grid?

Or even better, how many non-isomorphic solutions are there to a blank sudoku grid (that is, if you have two grids, and the only difference is that the 2s are where the 1s are and vice-versa, that doesn't count)?
L'lanmal
Posted: Tue Aug 23, 2011 12:45 am    Post subject: -10

One approach would be to calculate the odds that a randomly chosen Latin Squares meets the blocks of 9 requirement, and multiply by the number of 9x9 Latin Squares. (Of which, it is "well-known" that there are 5,524,751,496,156,892,842,531,225,600. Link http://en.wikipedia.org/wiki/Latin_square )
But with no known closed-form formulae for number of arbitrary sized Latin Squares, a systematic formula for number of valid Sudoku grids from that method seems unlikely.

The number for 9x9 case in particular is known (published 2005), but that paper (Bertram Felgenhauer and Frazer Jarvis) is probably not the elegant solution you are hoping for.
Sentran
Posted: Tue Aug 23, 2011 12:04 am    Post subject: -11

groza528 wrote:
I'm referring to a full 9x9 grid, not just one section of the grid. If I were only trying to fill in a 3x3 grid, of course it's 9!, but to fill in the full 9x9 you have to start with the 9! and then fill in the other rows/columns/sections in a constricted manner.

I tried this again in a 3x3 grid, and I came up with more than 6 possible combinations, which led me to believe I had come up with an answer. My new answer is 14,631,321,600.
groza528
Posted: Tue Aug 23, 2011 12:01 am    Post subject: -12

I disagree with the last line; I'm not convinced that the end is as easy as you say.

Consider the smaller example, two rows of two 2x2 squares.

4! = 24 ways to fill in the upper left, which is pretty arbitrary. Let's assume we fill in
Code:
AB|..
CD|..
------
..|..
..|..

So then there are 2 ways to finish out the top row and 2 ways to finish out the second row which do not interfere with each other. So we're up to 96. Let's pick one of them:
Code:
AB|CD
CD|BA
------
..|..
..|..

There are likewise 4 ways to fill in the bottom right square based on the upper right.
Code:
AB|CD
CD|BA
------
..|AC
..|DB

And now the very last two digits will of course be forced, but the NEXT two my instinct says two choices... except oops! There is no possible way to fill R3C2. This is not the case for all permutations of the first three squares. So the end still requires you to consider how many previous permutations left you with infertile ground.

I tried to use induction at first but I couldn't get a proper baseline for the 2x2 example, which makes it hard to recognize a pattern.
Zag
Posted: Mon Aug 22, 2011 11:43 pm    Post subject: -13

Hmmm. Interesting problem. This would be my approach:

Consider the word "square" always means one block of 9 numbers, so a sudoku has three rows of three squares.

Take the top left square. You can place the numbers 1-9 in those positions any way you like, so that gives you 9! combinations.

Now consider the square to its right. This has the same 9! combinations, but many of them are now illegal because of conflicts with the first square. I was hoping something would hit me on how to enumerate the illegal positions, but nothing is. The big problem is the large number of overlaps. Ok. Here's the best I have

The number of illegal positions due to exactly 1 number in the top row being illegal (and possibly more in other rows, but only 1 in the top) is 3 * 3 * (6C2) * 6! I think. That's 3 numbers that can make it illegal * 3 positions * the number of combinations for 2 numbers that wouldn't be illegal * the number of possible combinations for the remaining six numbers. You could do a similar calculation for the combinations that are illegal due to exactly 2 numbers in the top row, and the number for all three in the top row being illegal (3! * 6!).

Then you have to count the number of ways that the second square can be illegal because there are 0 illegal values in the top row and exactly 1, exactly 2, and all 3 illegal in the second row. Note that once the first and second rows (of this second square) are legal, the last row must be, as well.

Phew! On to the third square, which will be easy. There are (3!) ^3 legal combinations of this block, given the first two blocks.

The first square of the middle row of squares will have the same number of combinations as the second square of the top row.

The middle square is tricky, I haven't worked that one out, yet.

Once you have that, the rest are pretty easy, and are left as an exercise for the grad student.
groza528
Posted: Mon Aug 22, 2011 11:42 pm    Post subject: -14

I'm referring to a full 9x9 grid, not just one section of the grid. If I were only trying to fill in a 3x3 grid, of course it's 9!, but to fill in the full 9x9 you have to start with the 9! and then fill in the other rows/columns/sections in a constricted manner.
Sentran
Posted: Mon Aug 22, 2011 11:31 pm    Post subject: -15

My immediate response would be 9! (with the ! meaning factorial, not just a vehement 9), which is 362,880 possible combinations.

To think through logically...
If it was a grid of 1 number, there is only 1 possible outcome.
If it was a grid of 2, there are 2 possible outcomes. (2*1)
If it was a grid of 3, there are 6 possible outcomes. (3*2*1)
And so on to 9.
groza528
Posted: Mon Aug 22, 2011 11:11 pm    Post subject: -16

I came up with this question yesterday. I don't know the answer. Frankly, the answer doesn't interest me terribly, but the solution does... I want to know if there is an elegant way to arrive at a numerical answer. Just to satisfy my own curiosity.

How many legal solutions are there to a blank sudoku grid?