3×3 Quilt: n-Tile n×n checkerboards

3x3 QuiltSo, my wife and daughter were taking some squares of fabric to make a 3×3 quilt for a doll that’s going in an Operation Christmas Child shoebox. My wife asked me if it were possible, using 3 of each square, to not have any repeats in any row or column, and not to have a diagonal that’s solid. In short, the answer is no.

So, it turns out, this is just modified PseuDoKu. For a 3×3 pattern, with three of each, there are `3! = 6` permutations of the three squares (ABC, ACB, BAC, BCA, CAB, CBA). With three rows, there are `(3!)^3 = 6^3 = 216`. But if you just define the upper left square (whichever it is) as A, the upper-middle square as B, and the upper-right as C, then there’s really only one combination you have to think of. (If I have my fancy math terms correct, the others are isomorphic. Watching Numberphile and related channels has taught me some terms I never learned in school.) So when we permute the second row, if we eliminate impossible versions, all we are left with are two combinations for the first two rows:

ABC ABC ABC ABC ABC ABC
ABC ACB BAC BCA CAB CBA
XXX XXX XXX XXX XXX XXX

Each of those good ones has only one choice for the row beneath, assuming we’re enforcing the rows and columns rule (but not enforcing diagonals).

ABC ABC
BCA CAB
CAB BCA

And, as you can easily see, one of the diagonals has the same square repeated each time. So none of the 3×3 grids work.

But what about other grids?

A 1×1 grid both passes and fails simultaneously: “A”. All rows, columns, and diagonals only have one-each of A, so it obviously passes. But all rows, columns, and diagonals are all A’s, so fail for not being unique.

A 2×2 grid passes on rows and columns easily, but fails on diagonals:

AB
BA

We discussed the 3×3 grid in detail.

A 4×4 grid is the simplest of the PseuDoKu, but with the additional rule that diagonals cannot be solid. I know there are many that aren’t solid, but when I revisited my PseuDoKu generator, the first one it created did have a repeat in a diagonal, even though it wasn’t solid. A quick check does show that you can get the diagonals to have just one of each symbol as well (it makes sense; I know there are variants of 9×9 sudoku that require the diagonals to follow the uniqueness rule as well, and I thought that any square-of-squares — 4×4, 9×9, 16×16, … &mdash would have a subset of solutions that follow the diagonals rule as well.

ABCD
DCBA
BADC
CDAB

I wasn’t sure on grids between 4×4 and 9×9, so I made up some macros to help me to the row/column/diagonal elimination with possibilities, and was able to pare down to at least one valid solution each:

5×5       6×6       7×7       8×8
ABCDE     ABCDEF    ABCDEFG   ABCDEFGH
ECABD     EDAFCB    EGBFCAD   BHECDGAF
BEDCA     CFEABD    GCFBDEA   HABFGCDE
DABEC     FCDBAE    DEGCABF   GFDEBAHC
CDEAB     DEBCFA    FDEABGC   FDHGCEBA
          BAFEDC    CFAEGDB   EGFHADCB
                    BADGFCE   CEGAHBFD
                              DCABFHEG

(Those were all with the strong-diagonal rule “no repeats in the diagonal”, rather than the original weaker-diagonal rule “no solid diagonals”)

I won’t show a 9×9, because that’s just sudoku with unique diagonals.

I don’t have a rigorous proof, but given that 3 and under have no unique-diagonal solutions, but 4 thru 9 do have unique-diagonal solutions, I conjecture that I can generalize n bigger than 3 will have unique-diagonal solutions.

However, if I had a proof, I think I’d know why 3×3 doesn’t work, not just easily be able to see that it doesn’t. My guess is that it has something to do with `3! < 3^2`, whereas `n! > n^2` for `n>3` — thus we have more choices for the row/column/diagonal permutations than we do squares in the grid. It almost makes sense as a reason.