The Quite Unusual Square

Question

Imagine an $n \times n$ grid filled with the numbers 1, ..., $n$ where $n$ > 3 each number appearing n times, where each row, column, and diagonal all equal the same number. Can you fill grid like this? If so, show an example, and include as much detail as possible (for example if there's only 1 solution). If not, provide mathematical proof it's impossible.

I've purposely excluded $1 \times 1$ due to simplicity, $2 \times 2$ due to impossibility and $3 \times 3$ also due to impossibility (for solvers like you!)

Answer 1

Nice idea for a puzzle, reminds me of Sudoku in a way. An answer for 4x4 (Simple I know but I have to start somewhere):

How I found it:

If the total of each row, column and diagonal must be the same, then it follows that the total for an $n$ x $n$ square must be $n^2 /2 + n/2$. This is achieved with one of each of the numbers $1, ... n$ appearing in every row, column and diagonal.

To find my answer, I started by filling in a diagonal with numbers 1-4, then simply filled in the remainder through trial and error.

Fear not, more answers will come! I extended the method I used for 4x4 and solved the 5x5 this time:

This time I started again by filling in the diagonal, but then filled in the 3s in a symmetrical pattern. After that I filled in the 1s and then rotated that design by 180 degrees and used it again for the 5s. Lastly I solved the 2s and 4s in the same way.

So, to summarise:

Filling a $n \times n$ grid with the above rules seems to always be possible, because as pointed out by squeamish ossifrage, there are hundreds of thousands of permutations for the numbers to sit in for the 9x9.

Answer 2

The squares you describe are related to Latin squares. A Latin square of order $n$ is an $n\times n$ square grid, filled with the numbers $1,\ldots,n$, such that each number appears once in every row and in every column. A Latin square is called doubly diagonal if each number also appears once on each diagonals. A doubly diagonal Latin square satisfies your condition, because each number appears $n$ times, and the rows, columns, and diagonals sum to $1+\ldots+n=\frac{n(n+1)}{2}$.

For $n$ a positive integer, a doubly diagonal Latin square of order $n$ exists if and only if $n=1$ or $n\geq 4$. I won't try to describe the general construction here, but this is written down explicitly in [1].

[1] Gergely, Ervin. A simple method for constructing doubly diagonalized Latin squares. J. Combinatorial Theory Ser. A, 16 (1974), 266--272.

Answer 3

I found a simple algorithm for odd numbers not divisible by 3.

Start with 1,2,...,n
For each subsequent row, push by 2.

5x5:

1 2 3 4 5
4 5 1 2 3
2 3 4 5 1
5 1 2 3 4
3 4 5 1 2

7x7:

1 2 3 4 5 6 7
6 7 1 2 3 4 5
4 5 6 7 1 2 3
2 3 4 5 6 7 1
7 1 2 3 4 5 6
5 6 7 1 2 3 4
3 4 5 6 7 1 2

11x11:

1  2  3  4  5  6  7  8  9  10 11
10 11 1  2  3  4  5  6  7  8  9
8  9  10 11 1  2  3  4  5  6  7
6  7  8  9  10 11 1  2  3  4  5
4  5  6  7  8  9  10 11 1  2  3
2  3  4  5  6  7  8  9  10 11 1
11 1  2  3  4  5  6  7  8  9  10
9  10 11 1  2  3  4  5  6  7  8
7  8  9  10 11 1  2  3  4  5  6
5  6  7  8  9  10 11 1  2  3  4
3  4  5  6  7  8  9  10 11 1  2

edit: See Lopsy's comment.

This method will work for any number not divisible by 2 or 3. If each column is a series with a push-value of p, each diagonal will be a series with a push-value of p-1 and p+1. At 2, this means one diagonal is pushed by 1 (1,n,n-1,...,2), or pushed by 3.

So as long as a number does not share any divisors with p-1,p, or p+1, and p is not equal to 1 or n-1, p should work for that n.

This is equivalent to the classical algorithm for generating Latin squares (pushing by 1 each row), then taking out the even rows and appending them to the bottom.

I'm sure it's always possible to build these squares for n > 3, but this is just an easy case for these numbers.

Answer 4

Here's a $9 \times 9$ grid that I found in about a minute using a Sudoku solver:

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

There are thousands more $9 \times 9$ solutions. From this square alone, I think it's possible to generate another 2903039 possible answers (since there are 9! permutations of the numbers 1-9, and the grids can be rotated four different ways with two possible reflections).

Answer 5

Let me trump the others (for now) with a 16x16: (taken from my answer to another question here:

Given each line (and each main diagonal) holds numbers 1-16, they all have a total value of 136. Each number also appears 16 times.

As a bonus: it's a working 16x16 sudoku, with each 4x4 block being a magic square.

Answer 6

There seems to be multiple interpretations of this question.

Every broken diagonal contains every symbol

Possible if and only if $n$ is odd.

We can use diagonally cyclic Latin squares (as in DrLemniscate's answer). For all odd $n \geq 1$, we use this particular square: $$ \begin{bmatrix} \color{blue} 8 & 7 & 6 & 5 & 4 & \color{red} 3 & 2 & 1 & 0 \\ 1 & \color{blue}0 & 8 & 7 & 6 & 5 & \color{red} 4 & 3 & 2 \\ 3 & 2 & \color{blue} 1 & 0 & 8 & 7 & 6 & \color{red} 5 & 4 \\ 5 & 4 & 3 & \color{blue} 2 & 1 & 0 & 8 & 7 & \color{red} 6 \\ \color{red} 7 & 6 & 5 & 4 & \color{blue} 3 & 2 & 1 & 0 & 8 \\ 0 & \color{red} 8 & 7 & 6 & 5 & \color{blue} 4 & 3 & 2 & 1 \\ 2 & 1 & \color{red} 0 & 8 & 7 & 6 & \color{blue} 5 & 4 & 3 \\ 4 & 3 & 2 & \color{red} 1 & 0 & 8 & 7 & \color{blue} 6 & 5 \\ 6 & 5 & 4 & 3 & \color{red} 2 & 1 & 0 & 8 & \color{blue} 7 \\ \end{bmatrix} $$ Horizontally the symbols decrease by $1$; vertically the symbols increase by $2$; along the main broken diagonals (and in particular, along the main diagonal) the symbols increase by $1$. These properties ensure that there are no repeated symbols in rows and columns (i.e., it is a Latin square), and there are no repeated symbols on the broken diagonals. (Formally, $-1$, $1$, and $2$ are generators of $\mathbb{Z}_n$ when $n$ is odd.)

Now at this point we notice that diagonally cyclic Latin squares have an orthogonal mate where each main diagonal is a unique symbol: $$ \begin{bmatrix} \color{blue} 2 & \color{red} 1 & \bf \color{green} 0 \\ \bf \color{green} 1 & \color{blue} 0 & \color{red} 2 \\ \color{red} 0 & \bf \color{green} 2 & \color{blue} 1 \\ \end{bmatrix} \begin{bmatrix} \color{blue} 0 & \color{red} 1 & \bf \color{green} 2 \\ \bf \color{green} 2 & \color{blue} 0 & \color{red} 1 \\ \color{red} 1 & \bf \color{green} 2 & \color{blue} 0 \\ \end{bmatrix}. $$ However, the cyclic Latin square (generalizing the Latin square on the right above) has no orthogonal mate when $n$ is even (this goes back to Euler), so the desired Latin square impossible when $n$ is even.

Every broken diagonal and every broken antidiagonal contain every symbol

Possible if and only if $n \equiv \pm 1 \pmod 6$.

Since these are a special case of the previous case, they can only exist when $n$ is odd.

The diagonally cyclic Latin squares in DrLemniscate's answer work when $n \equiv \pm 1 \pmod 6$: along the main broken diagonals (and in particular, along the main diagonal) the symbols increase by $3$ (since $3$ generates $\mathbb{Z}_n$ in these cases).

When $n \equiv 3 \pmod 6$, it wasn't immediately obvious so I asked about it on MathOverflow. Afterwards, I realized it would give rise to a "strong complete mapping" and they don't exist when $n \equiv 3 \pmod 6$.

The main diagonal and the main antidiagonal contain every symbol

Possible if and only if $n \not\in \{2,3\}$.

Here, no conditions are applied to the non-main broken diagonals and antidiagonals. These are called doubly diagonal Latin squares. Julian Rosen's answer covers this, although there were other proofs around the same time:

A. J. W. Hilton, On double diagonal and cross latin squares，J. London Math, 1973 (link).

C. C. Lindner, On constructing doubly diagonalized latin squares, Feriodica Mathematica Hungarica Vol. 5 (3), (1974), pp. 249--253 (link).

You're unlikely to get a better write-up of the general case than the published papers on this. However, we've basically already solved a large number of cases.

If we have two doubly diagonal Latin squares of orders $n$ and $m$ and take their direct product (if $L_{ij}$ and $M_{ij}$ are the Latin squares, than its direct product is a new Latin square with $(L_{ij},M_{ij})$ in cell $(i,j)$), we get a doubly diagonal Latin square of order $nm$.

The diagonally cyclic Latin square construction when $n \equiv \pm 1 \pmod 6$ works here (which includes all primes $\geq 5$). And Hilton (op. cit.) gives these examples for orders $n \in \{4,6,8,9\}$.

So this is enough for when $n$ is not $2P$ or $3P$ where $P$ is a product of (not necessarily distinct) primes $\geq 5$. These cases seem to require more care, so it's best to refer to these papers.

The main diagonal contains every symbol

Possible if and only if $n \neq 2$.

I include this mostly for completeness sake. We take a diagonally cyclic Latin square of odd order $\geq 3$, and prolong it using a broken diagonal other than the main diagonal.

$$ \begin{bmatrix} 4 & \color{blue} 3 & 2 & 1 & 0 \\ 1 & 0 & \color{blue} 4 & 3 & 2 \\ 3 & 2 & 1 & \color{blue} 0 & 4 \\ 0 & 4 & 3 & 2 & \color{blue} 1 \\ \color{blue} 2 & 1 & 0 & 4 & 3 \\ \end{bmatrix} \longrightarrow \begin{bmatrix} 4 & \color{blue} 5 & 2 & 1 & 0 & \color{red} 3 \\ 1 & 0 & \color{blue} 5 & 3 & 2 & \color{red} 4 \\ 3 & 2 & 1 & \color{blue} 5 & 4 & \color{red} 0 \\ 1 & 4 & 3 & 2 & \color{blue} 5 & \color{red} 1 \\ \color{blue} 5 & 2 & 0 & 4 & 3 & \color{red} 2 \\ \color{red} 2 & \color{red} 3 & \color{red} 4 & \color{red} 0 & \color{red} 1 & \color{red} 5 \\ \end{bmatrix} $$

When we prolong, we shift the contents of the chosen broken diagonal to both (a) a newly created column on the right, and (b) a newly created row at the bottom; fill the cells of the chosen broken diagonal with a new symbol; and add the new symbol to the bottom-right cell.