10
$\begingroup$

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!)

$\endgroup$
  • 2
    $\begingroup$ Do you mean the rows, columns, and diagonals have the same sum? $\endgroup$ – Julian Rosen Dec 18 '14 at 17:04
  • $\begingroup$ $3\times 3$ is not possible either (place the different elements on the diagonal, and you cannot use any element on the off-diagonal) You might want to rephrase that bit in your question. $\endgroup$ – M.Herzkamp Dec 19 '14 at 10:43
  • $\begingroup$ In the spirit of this site, I think Julian's answer it's the best and should be the accepted one. $\endgroup$ – BmyGuest Dec 20 '14 at 8:17
  • $\begingroup$ @BmyGuest I cannot accept Julian's answer as it does not fully answer the question. $\endgroup$ – warspyking Dec 20 '14 at 15:04
8
$\begingroup$

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):

4x4 Image

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:

5x5 Image
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.

$\endgroup$
  • $\begingroup$ Nice, I look forward to 6, 7, 8, and 10 (9 can be included but already solved by someone else) $\endgroup$ – warspyking Dec 18 '14 at 13:50
  • $\begingroup$ Thanks, already working on 9 so I'll finish it quickly. I guess the real puzzle is finding an infallible method for any nxn (excluding 2 of course) $\endgroup$ – For I In Range Dec 18 '14 at 13:52
  • $\begingroup$ On second thought, maybe I'll leave nine... after filling the whole thing in I just realised I messed up the 1s and 9s :( $\endgroup$ – For I In Range Dec 18 '14 at 14:04
  • 2
    $\begingroup$ 3×3 is basic? Impossible more like. Whatever permutation of 1, 2 and 3 you have on the top row, one of them will always be repeated in the middle cell, making it impossible to obtain a total of 6 in every row & column and on both diagonals. $\endgroup$ – squeamish ossifrage Dec 18 '14 at 14:08
  • 1
    $\begingroup$ @ForIInRange I (maybe wrongly) interpreted the question to mean all the rows, cols, and diags have to add to the same number. I agree with you in that I think the puzzle is more interesting if they all must contain each number exactly once. $\endgroup$ – Lopsy Dec 18 '14 at 17:44
15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I would expect this answer to become the accepted one, as it is a fully complete answer reducing the problem to an existing one with already known answer. $\endgroup$ – BmyGuest Dec 20 '14 at 8:16
  • $\begingroup$ @BmyGuest It really is a better answer. Mine was first but this is a more comprehensive answer $\endgroup$ – For I In Range Dec 27 '14 at 16:55
  • $\begingroup$ My question got upvoted which caused me to come back. The reason I never accepted this was because you never provided an example "Can you fill grid like this? If so, show an example, and include as much detail as possible" $\endgroup$ – warspyking Jun 27 '15 at 0:19
8
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ This construction works not just for primes, but for any number not divisible by 2 or 3. $\endgroup$ – Lopsy Dec 18 '14 at 19:02
4
$\begingroup$

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).

$\endgroup$
4
$\begingroup$

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

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.

$\endgroup$

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.