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.
For the first question, these designs are known to mathematicians as Latin squares. 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.
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 876*…21 = 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.
Look at the 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!.
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
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.
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.
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.)
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!
Placing 8 queens on a standard chessboard so that none attacks another has 12 distinct solutions (excluding rotations and reflections). Eight queens puzzle - Wikipedia
Solution 12 in the wiki article has 180° rotational symmetry.
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, but I couldn’t see how to apply it to this problem.
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
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.
No idea, but I’m using HTTPS Everywhere, which is why I get it.
Bricker, you forgot the link.