6
$\begingroup$

This problem comes from a study of game design, specifically the wonderful abstract strategy game Kamisado, which I highly recommend for the mathematically minded.

The rules of the game are not so important, I am interested only in the board, which looks like this -

                           

The board is an 8x8 Latin Square. I wonder how much choice the designer had in choosing the board. The only restrictions we want are that the board should be the same for both players, and that swapping two colours doesn't matter in terms of gameplay.

So the question is, more generally, "How many Latin squares of size $n$ exist which are isomorphic under a rotation of 180 degrees and symbol permutation?"

Specifically, for $n=8$, "How many possible Kamisado boards are there?". I know the answer must be in the literature somewhere, but am unfamiliar with the area and terminology. If there is a similar question somewhere please point me towards that instead.

$\endgroup$
11
  • $\begingroup$ Do you allow for swapping rows and columns? Do you know Polya's enumerations / Burnside lemma? $\endgroup$ – Calvin Lin Oct 21 '13 at 14:57
  • $\begingroup$ Yes, provided rotational symmetry is kept (so there would have to probably be an even number of row/column swaps). And no, my interest in combinatorics is completely amateur - I will look into them though! $\endgroup$ – Bennett Gardiner Oct 22 '13 at 1:31
  • $\begingroup$ There is no fixer number of colors ? i.e. there could be 1,2,3,..,32. colors? $\endgroup$ – jgyou Oct 29 '13 at 15:18
  • 1
    $\begingroup$ I think you are just looking for the number of Latin squares that are symmetric under $180^{\circ}$ rotations, up to permutation of symbols. $\endgroup$ – mjqxxxx Oct 30 '13 at 16:53
  • 1
    $\begingroup$ I don't know whether your type is one of the ones tabulated at oeis --- I reckon it's up to you to figure that out from the descriptions given with each sequence. Or, if you know the exact answers for smaller boards, that might narrow things down considerably. Or, you might find that even though your exact type isn't tabulated at oeis, the links there take you to sources that will help you solve the problem on your own. Don't be helpless! Look around! read stuff! try stuff! $\endgroup$ – Gerry Myerson Oct 31 '13 at 11:59
2
$\begingroup$

Your question pertains to the number of Latin squares with a particular symmetry ($180^{\circ}$ rotational symmetry -- so the dimension $n$ must be even), up to equivalence under permutation of labels (colors). To choose a single representative of each such equivalence class, consider only normalized Latin squares, which are those with first row equal to $\{1,2,\ldots,n\}$. You then want to fill in rows $2$ through ${n/2}$ in such a way that each row is a permutation of the values $1$ through $n$, and moreover, each entry $x_{i, j}$ is distinct from the entries above it in both its own column and its left-right mirror-image column: that is, $$ x_{i,j}\not\in \left\{ x_{i,k}: k<j \right\} \cup \left\{ x_{n-i,k}: k<j \right\} $$ for $2 \le i \le n/2$ and $1\le j \le n$. The remaining rows are then forced by the rotational symmetry. For instance, for $n=4$ you need to fill in the second row below with $1,2,3,4$ as constrained here: $$ \left[\begin{matrix} 1 & 2 & 3 & 4\\ \{2,3\}& \{1,4\}&\{1,4\}&\{2,3\} \end{matrix}\right]. $$ There are clearly just $4$ ways to do this. For $n=8$, the first two rows are: $$ \left[\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ \not\in\{1,8\} & \not\in\{2,7\} & \not\in\{3,6\} & \not\in\{4,5\} & \not\in\{4,5\} & \not\in\{3,6\} & \not\in\{2,7\} & \not\in\{1,8\} \end{matrix}\right]. $$ By brute force, there are $4752$ ways to fill in the first two rows. For each of these, there are at most $4^8 2^8 = 16777216$ ways to fill in rows $3$ and $4$; so a (generous) upper bound on the number you're looking for is $7.9725330432 \times 10^{10}$. This is quite accessible for a direct calculation.

$\endgroup$
2
  • $\begingroup$ This upper bound is tighter than the number of $8\times 4$ Latin rectangles ($88390995840$) -- that is, the number of ways to fill in the top half without the mirror-image column constraint -- but only slightly. $\endgroup$ – mjqxxxx Oct 30 '13 at 19:03
  • $\begingroup$ Thanks, both answers have given me some things to think about. $\endgroup$ – Bennett Gardiner Oct 31 '13 at 12:06
2
+50
$\begingroup$

Some Hints:

We have to fill the first player half, then we'll have the second player's half with symetry.

Now, we have a $n$ x $ (n/2)$ table. Just randomly fill the first line, you have $n!$ alternatives, right?

Now, filling the second line. What are our restrictions? No colour can have the same column number with the previous one, of course. And the other restriction comes from the symetry. We know that if a colour is in $i^{th}$ column in $j^{th}$ line, it is also in $(n-i+1)^{th}$ column in $(n-j)^{th}$ line. Then, the other restriction is no colour can have the same column number with $(n-$previous_column_number $+1$). Then, how many alternatives do we have?

Let's start with the first one, we have n-2 alternatives. Now, assume we had put the the first colour to $i^{th}$ column in the first line and $j^{th}$ column in the second line. And now assume we had put the second colour in the first line to $j^{th}$ column. Now, for the second colour we again have n-2 alternatives. But if we had put the first colour into a column different than the one with number $j$, we would have $n-4$ alternatives for the second colour. That is the tricky part of our problem.

Edit (further hint): What you have to find is that:

I have $n$ colours and $n$ spots. For each colour, $k$ spots are forbidden where $k$ depends on the line number, as at $i^{th}$ line, $k= n-2(i-1)$. For example, for first line there is no restriction, you can randomly locate the colours. For the second line, for each colour, 2 spots are forbidden. For third, 4 spots are forbidden etc.

If you can find the number of permutations for that restriction, you'll have your answer.

$\endgroup$
8
  • $\begingroup$ I understand parts of your answer but not all - convince me with a small example? $\endgroup$ – Bennett Gardiner Oct 30 '13 at 12:56
  • 1
    $\begingroup$ Can you tell which parts did you understand and which part you didn't? And this is not the whole answer, I worked on building a whole solution but it's still hard. $\endgroup$ – Zafer Sernikli Oct 30 '13 at 14:11
  • $\begingroup$ Understandable example, $4$x$4$: (it's hard to do with $6$x$6$). You randomly fill the first line, let's say $(a,b,c,d)$. Now, you know that you'll have $(d,c,b,a)$ in the forth line. If you try to fill the second line, what are your restrictions for $a$? You can't put it in the first and forth columns, because they're full. You're gonna put it into second or third column, and that will make you put $d$ into the other column than where you put $a$. Same thing will happen for $b$ and $c$. Then you have $4! \cdot 2 \cdot 2 = 96$ different solutions for $4$x$4$. $\endgroup$ – Zafer Sernikli Oct 30 '13 at 14:36
  • $\begingroup$ Here, it's simple to calculate the alternatives for second line, because restrictions give us only $4$ alternatives. But what I meant is, the restrictions are actually clear. For $6$x$6$ for example, if your first line is like $(a,b,c,d,e,f)$, you cannot put $a$ and $f$ to first and sixth columns, $b$ and $e$ into second and fifth columns, $c$ and $d$ into third and forth columns. What you have to find is a formula for the number of alternatives with those types of restrictions where I mean $2$ restricted spots for every two elements in $n$ length chain. $\endgroup$ – Zafer Sernikli Oct 30 '13 at 14:43
  • $\begingroup$ For 6, it's gonna be $122$ if I did not miscalculate it. And it's only for the second line. Of course you have to calculate the number of alternatives for third line and see that most of the alternatives in second line reaches a dead end. Take the propoer ones and multiplicate with $6!$. You have to find a formula or something, but of course you have to claim a formula and show it by induction. That's why I started with $4$ and tried to find the solution for $6$. $\endgroup$ – Zafer Sernikli Oct 30 '13 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.