# How Many Solutions Are There to this Puzzle? **URL:** \ **Category:** Factual Questions\ **Created:** [August 29, 2011, 1:47pm UTC](https://boards.straightdope.com/t/how-many-solutions-are-there-to-this-puzzle/594490 "2011-08-29T13:47:14Z")\ **Posts on this page:** 17\ **Page:** 1
**Author:** ![HeyHomie](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/heyhomie/32/207_2.png) [@HeyHomie](https://boards.straightdope.com/u/HeyHomie)\ **Post date:** [August 29, 2011, 1:47pm UTC](https://boards.straightdope.com/t/how-many-solutions-are-there-to-this-puzzle/594490/1 "2011-08-29T13:47:14Z")
This is on the wall at the pre-school classroom at my church: a matrix of nine colored circles, three each of red, yellow, and green, in a 3x3 grid. No row or column contains more than one color. At church it looks like this: GYR RGY YRG How many possible solutions are there? – On the subject of similar puzzles, how many solutions are there to the chess puzzle where you place eight pawns on the board, but no two pawns occupy the row or column? Thanks. ---
**Author:** ![MikeS](https://avatars.discourse-cdn.com/v4/letter/m/919ad9/32.png) [@MikeS](https://boards.straightdope.com/u/MikeS)\ **Post date:** [August 29, 2011, 1:51pm UTC](https://boards.straightdope.com/t/how-many-solutions-are-there-to-this-puzzle/594490/2 "2011-08-29T13:51:21Z")
For the first question, these designs are known to mathematicians as [Latin squares](http://en.wikipedia.org/wiki/Latin_square). There are 12 such designs for a 3x3 square, though as you can see from the table in the linked article, the number grows rapidly as the size increases. ---
**Author:** ![MikeS](https://avatars.discourse-cdn.com/v4/letter/m/919ad9/32.png) [@MikeS](https://boards.straightdope.com/u/MikeS)\ **Post date:** [August 29, 2011, 2:44pm UTC](https://boards.straightdope.com/t/how-many-solutions-are-there-to-this-puzzle/594490/3 "2011-08-29T14:44:19Z")
And for the second question, the answer is 8! = 40,320. To see this, imagine placing the pawns on the board, row by row. The pawn in the first row can be in any of the eight columns. The pawn in the second row can be in any of the seven columns that you didn’t place the first pawn in. The pawn in the third row can by in any of the six remaining columns, and so forth. So 8_7_6\*…_2_1 = 8! = 40,320. This assumes that you count arrangements as distinct even if they’re, say, a 90° rotation or a reflection of each other. If you want to count those arrangements as the same, then the answer isn’t quite so obvious to me. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 29, 2011, 3:05pm UTC](https://boards.straightdope.com/t/how-many-solutions-are-there-to-this-puzzle/594490/4 "2011-08-29T15:05:43Z")
> [@MikeS](#): > > This assumes that you count arrangements as distinct even if they’re, say, a 90° rotation or a reflection of each other. If you want to count those arrangements as the same, then the answer isn’t quite so obvious to me. Look at the [dihedral group](https://secure.wikimedia.org/wikipedia/en/wiki/Dihedral_group) associated with a square. That has eight elements, so the total number of solutions to the puzzle modulo reflections and rotations is just 7!. ---
**Author:** ![Little\_Nemo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/little_nemo/32/3120_2.png) [@Little\_Nemo](https://boards.straightdope.com/u/Little_Nemo)\ **Post date:** [August 29, 2011, 3:35pm UTC](https://boards.straightdope.com/t/how-many-solutions-are-there-to-this-puzzle/594490/5 "2011-08-29T15:35:33Z")
gyr rgy yrg gry ygr ryg ryg ygr gry yrg rgy gyr ygr ryg gry yrg gyr rgy rgy gyr yrg gry ryg ygr ryg gry ygr rgy yrg gyr gyr yrg rgy ygr gry ryg ---
**Author:** ![MikeS](https://avatars.discourse-cdn.com/v4/letter/m/919ad9/32.png) [@MikeS](https://boards.straightdope.com/u/MikeS)\ **Post date:** [August 29, 2011, 3:48pm UTC](https://boards.straightdope.com/t/how-many-solutions-are-there-to-this-puzzle/594490/6 "2011-08-29T15:48:27Z")
> [@ultrafilter](#): > > Look at the [dihedral group](https://secure.wikimedia.org/wikipedia/en/wiki/Dihedral_group) associated with a square. That has eight elements, so the total number of solutions to the puzzle modulo reflections and rotations is just 7!. Aren’t some of the solutions mapped to themselves by elements of the dihedral group, though? The solution where all eight pawns are on a diagonal, for example, is left invariant under reflection about an axis through that diagonal. If there were no fixed elements under the action of the group, then you could divide the 8! solutions into equivalence classes of eight arrangements each, and there would be 7! such classes, but it doesn’t seem like this would work if the equivalence classes aren’t all the same size. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [August 29, 2011, 5:40pm UTC](https://boards.straightdope.com/t/how-many-solutions-are-there-to-this-puzzle/594490/7 "2011-08-29T17:40:27Z")
The more interesting problem on a chessboard, and which I suspect is the one the OP was actually thinking of, is the “eight queens” puzzle. There, you have to have only one piece on each row, column, _and diagonal_. That is to say, if all eight pieces were queens, none of them would be able to attack each other. I don’t think that one has any symmetric solutions (certainly none with mirror symmetry), but it’s harder to count the solutions to begin with. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 29, 2011, 7:22pm UTC](https://boards.straightdope.com/t/how-many-solutions-are-there-to-this-puzzle/594490/8 "2011-08-29T19:22:25Z")
> [@MikeS](#): > > Aren’t some of the solutions mapped to themselves by elements of the dihedral group, though? The solution where all eight pawns are on a diagonal, for example, is left invariant under reflection about an axis through that diagonal. If there were no fixed elements under the action of the group, then you could divide the 8! solutions into equivalence classes of eight arrangements each, and there would be 7! such classes, but it doesn’t seem like this would work if the equivalence classes aren’t all the same size. True. So we can regard 7! as a lower bound. I suspect that the answer is closer to 7! than 8!, but I don’t have a good argument as to why. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [August 29, 2011, 7:51pm UTC](https://boards.straightdope.com/t/how-many-solutions-are-there-to-this-puzzle/594490/9 "2011-08-29T19:51:06Z")
> [@ultrafilter](#): > > True. So we can regard 7! as a lower bound. I suspect that the answer is closer to 7! than 8!, but I don’t have a good argument as to why. (8! - 1376 - 296 - 88)/8 + (1376+296)/4 + 88/2 = 5282 which indeed isn’t much bigger than 7!. The 1376, 296 and 88 are the counts of three different invariant cases such as **MikeS** refers to. (The argument “why” is simply that the invariant cases are relatively uncommon.) ---
**Author:** ![cmyk](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/cmyk/32/3353_2.png) [@cmyk](https://boards.straightdope.com/u/cmyk)\ **Post date:** [August 29, 2011, 7:58pm UTC](https://boards.straightdope.com/t/how-many-solutions-are-there-to-this-puzzle/594490/10 "2011-08-29T19:58:39Z")
> [@Little\_Nemo](#): > > gyr > rgy > yrg > > gry > ygr > ryg > > ryg > ygr > gry > > yrg > rgy > gyr > > ygr > ryg > gry > > yrg > gyr > rgy > > rgy > gyr > yrg > > gry > ryg > ygr > > ryg > gry > ygr > > rgy > yrg > gyr > > gyr > yrg > rgy > > ygr > gry > ryg gyr anrgy yrg hugry ygr ryg ryg ygr angry yrg rgy gyr ygr ryg hungry yrg gyr rgy rgy gyr yrg angry ryg ygr ryg hungry ygr rgy yrg gyr gyr yrg rgy ygr angry ryg And “angry” wins! ---
**Author:** ![rowrrbazzle](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/rowrrbazzle/32/414_2.png) [@rowrrbazzle](https://boards.straightdope.com/u/rowrrbazzle)\ **Post date:** [August 30, 2011, 3:33am UTC](https://boards.straightdope.com/t/how-many-solutions-are-there-to-this-puzzle/594490/11 "2011-08-30T03:33:35Z")
Placing 8 queens on a standard chessboard so that none attacks another has 12 distinct solutions (excluding rotations and reflections). [Eight queens puzzle - Wikipedia](http://en.wikipedia.org/wiki/Eight_queens_puzzle#Solutions_to_the_eight_queens_puzzle) Solution 12 in the wiki article has 180° rotational symmetry. ---
**Author:** ![MikeS](https://avatars.discourse-cdn.com/v4/letter/m/919ad9/32.png) [@MikeS](https://boards.straightdope.com/u/MikeS)\ **Post date:** [September 1, 2011, 2:38pm UTC](https://boards.straightdope.com/t/how-many-solutions-are-there-to-this-puzzle/594490/12 "2011-09-01T14:38:53Z")
**septimus** , how did you arrive at the numbers of symmetric solutions above? I don’t doubt them, I’m just curious how one would derive them for other situations. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [September 1, 2011, 2:56pm UTC](https://boards.straightdope.com/t/how-many-solutions-are-there-to-this-puzzle/594490/13 "2011-09-01T14:56:10Z")
> [@MikeS](#): > > **septimus** , how did you arrive at the numbers of symmetric solutions above? I don’t doubt them, I’m just curious how one would derive them for other situations. Brute force computer exercise. ☹ (I would have preferred to do something clever, but I’m super-lazy and a modern computer can zip through this enumeration before one’s finger even retracts from the Enter key.) I sometimes use an enumeration method like [Pólya’s enumeration theorem](http://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem), but I couldn’t see how to apply it to this problem. ---
**Author:** ![LSLGuy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lslguy/32/5813_2.png) [@LSLGuy](https://boards.straightdope.com/u/LSLGuy)\ **Post date:** [September 1, 2011, 3:45pm UTC](https://boards.straightdope.com/t/how-many-solutions-are-there-to-this-puzzle/594490/14 "2011-09-01T15:45:57Z")
If I may pull a hijack since this seems well-answered … **ultrafilter** ’s link in post 4 points to the https version of wiki (which I’d never seen before). Here’s the corresponding conventional link [Dihedral group - Wikipedia](http://en.wikipedia.org/wiki/Dihedral_group) Does anybody know why there’s an https version of wiki? I wasn’t able to locate any info on wiki’s about … pages. ---
**Author:** ![Bricker](https://avatars.discourse-cdn.com/v4/letter/b/977dab/32.png) [@Bricker](https://boards.straightdope.com/u/Bricker)\ **Post date:** [September 1, 2011, 3:49pm UTC](https://boards.straightdope.com/t/how-many-solutions-are-there-to-this-puzzle/594490/15 "2011-09-01T15:49:26Z")
> [@LSLGuy](#): > > Does anybody know why there’s an https version of wiki? I wasn’t able to locate any info on wiki’s about … pages. To prevent Eve from reading Alice’s article about Bob, of course. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [September 1, 2011, 5:22pm UTC](https://boards.straightdope.com/t/how-many-solutions-are-there-to-this-puzzle/594490/16 "2011-09-01T17:22:45Z")
> [@LSLGuy](#): > > If I may pull a hijack since this seems well-answered … > > **ultrafilter** ’s link in post 4 points to the https version of wiki (which I’d never seen before). Here’s the corresponding conventional link [Dihedral group - Wikipedia](http://en.wikipedia.org/wiki/Dihedral_group) > > Does anybody know why there’s an https version of wiki? I wasn’t able to locate any info on wiki’s about … pages. No idea, but I’m using [HTTPS Everywhere](https://www.eff.org/https-everywhere), which is why I get it. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [September 1, 2011, 8:10pm UTC](https://boards.straightdope.com/t/how-many-solutions-are-there-to-this-puzzle/594490/17 "2011-09-01T20:10:08Z")
**Bricker** , you forgot [the link](http://en.wikipedia.org/wiki/Alice_and_Bob).