Can you fill in the missing numbers in this unfriendly magic square?

Question

An unfriendly magic square is a magic square whereby the difference between neighbouring numbers always is subject to a minimum, i.e.

• Each number in the matrix is unique.
• Each row, column and the two diagonals add up to the same number (the magic constant).
• The difference between each pair of neighbouring numbers is greater than or equal to a specified constant value.
• Difference is defined as the larger number minus the smallest.
• Neighbour is defined as two numbers that are adjacent horizontally, vertically or diagonally.

In this case, the matrix consists of the numbers 1-25, and the magic constant is 65. The difference must be at least 4*, so 1 and 5 could be adjacent but not 1 and 3.

^{*No examples for the order 5 magic square exist with a minimum difference of 5 (or greater).}

Can you fill in the missing numbers?

\begin{bmatrix}?&?&?&12&?\\?&?&?&?&?\\?&?&?&?&?\\?&?&?&?&?\\?&14&?&?&?\end{bmatrix}

Here is a clue which reveals three more of the numbers:

\begin{bmatrix}?&10&?&12&?\\?&?&?&?&?\\?&?&13&?&?\\?&?&?&?&?\\?&14&?&16&?\end{bmatrix}

Answer 1

I have found a no-computer solution looking at a few patterns and bringing the possible solution set to 4 trial-and-error solutions, out of which 1 seems to solve it. And I would like to apologise in advance for using the hint. I am extremely sorry because using hints means I lack some understanding somewhere.

We start with the basic $5\times 5$ magic square (called basic hereafter):

\begin{bmatrix} 17 & 24 & 1 & 8 & 15 \\ 23 & 5 & 7 & 14 & 16 \\ 4 & 6 & 13 & 20 & 22 \\ 10 & 12 & 19 & 21 & 3 \\ 11 & 18 & 25 & 2 & 9 \end{bmatrix}

The matrix we want to find and is partially given is (called special hereafter):

\begin{bmatrix}?&10&?&12&?\\?&?&?&?&?\\?&?&13&?&?\\?&?&?&?&?\\?&14&?&16& \end{bmatrix}

Observe that both $10$ and $12$ go from row $4$ of basic of to row $1$ of special and $14$ and $16$ go from row $2$ of basic to row $5$ of special. Let's then follow the assumption that the first row of special is a permutation of the fourth row of basic and similarly the fifth row of special is a permutation of the second row of basic.

We tackle the former case first. Observe that $10$ is in the first column of basic and in the second column of special, whereas $12$ is the second column of basic and in the fourth column of special. Following the pattern, $19$ is in the third column of basic and hence should move to the sixth column, which is the first column modulo $5$ of special. Also, $21$ is in the fourth column of basic and hence should move to the eighth column, which is the third column modulo $5$ of special.

The latter case is similarly solved, which gives us:

\begin{bmatrix}19&10&21&12&3\\?&?&?&?&?\\?&?&13&?&?\\?&?&?&?&?\\23&14&5&16&7\end{bmatrix}

Now look at the primary diagonal of special. It contains $19,13$ and $7$, which are three elements from the third column of basic. Assume that the primary diagonal of special is a permutation of the third column of basic.

Also, for the sake of the arguments that follow, we label some elements of special:

\begin{bmatrix}19&10&21&12&3\\?&c&?&b&?\\?&?&13&?&?\\?&a&?&d&?\\23&14&5&16&7\end{bmatrix}

Then we now have $c=1$ or $25$ and $d=25$ or $1$ respectively. Observe that both solutions satisfy condition three and four of "difference".

We look at possible values of $a$ and $b$ (Note that $a+b=26$). Given condition three and four of difference, the following conditions follow:

$$a\le 10\ \text{or}\ a\ge 18\\ a= 1\ \text{or}\ a\ge 9\\ a\le 9\ \text{or}\ a\ge 17\\ a\le 19$$

This gives that the possible values of $a$ are $\{1,9,18,19\}$. Correspondingly $b$ has possible values $\{25,17,8,10\}$. Since $b\ne 25$ (since $c$ or $d$ has value $25$) and $b\ne 10$ ($10$ has already been used), the possible values of $a$ and $b$ reduce to $\{9,18\}$ and $\{17,8\}$.

Thus we have $4$ cases to check, which are the possible values of the $4$-tuple $(a,b,c,d)$. The first possibility is $(9,17,1,25)$. This gives:

\begin{bmatrix}19&10&21&12&3\\?&1&?&17&?\\?&?&13&?&?\\?&9&?&25&?\\23&14&5&16&7\end{bmatrix}

This is not possible as the remaining element of the second column is $31>25$.

The next possibility we check is $(9,17,25,1)$ which gives:

\begin{bmatrix}19&10&21&12&3\\?&25&?&17&?\\?&?&13&?&?\\?&9&?&1&?\\23&14&5&16&7\end{bmatrix}

This is also not possible because the remaining element of the second column is $7$ which has been used once.

For $(18,8,25,1)$, we have:

\begin{bmatrix}19&10&21&12&3\\?&25&?&8&?\\?&?&13&?&?\\?&18&?&1&?\\23&14&5&16&7\end{bmatrix}

The remaining element of the second column becomes negative, and thus this is discarded. The only remaining solution is $(18,8,1,25)$ which gives:

\begin{bmatrix}19&10&21&12&3\\?&1&?&8&?\\?&?&13&?&?\\?&18&?&25&?\\23&14&5&16&7\end{bmatrix}

Filling in the obvious elements, we have:

\begin{bmatrix}19&10&21&12&3\\?&1&?&8&?\\?&22&13&4&?\\?&18&?&25&?\\23&14&5&16&7\end{bmatrix}

Now the third row of special looks like a permutation of the third row of basic, and we see that the third row first column element of special cannot be $20$ (as $22-20=2<4$) and hence we have:

\begin{bmatrix}19&10&21&12&3\\?&1&?&8&?\\6&22&13&4&20\\?&18&?&25&?\\23&14&5&16&7\end{bmatrix}

Also the third column of special looks like a permutation of the principle diagonal of basic, and we see that the second row third column element of special cannot be $9$ (as $9-8=1<4$) and hence we have:

\begin{bmatrix}19&10&21&12&3\\?&1&17&8&?\\6&22&13&4&20\\?&18&9&25&?\\23&14&5&16&7\end{bmatrix}

The second row of special is a permutation of the first row of basic and the fourth row of special is a permutation of the fifth row of basic. As $15-12=3<4$ and $4-2=2<4$, thus the final special square comes to be:

\begin{bmatrix}19&10&21&12&3\\15&1&17&8&24\\6&22&13&4&20\\2&18&9&25&11\\23&14&5&16&7\end{bmatrix}

One can verify that all the conditions are met by this solution and hence we are done.

This is obviously no algorithm as this does not work in a general situation, and if one asks if we got lucky, we dare say yes...

Answer 2

The solution:

 19 10 21 12  3
 15  1 17  8 24
  6 22 13  4 20
  2 18  9 25 11
 23 14  5 16  7

View C code

Answer 3

With no-computers removed, I attempted a brute-force search in Python.

import numpy as np
from itertools import permutations, combinations

best = np.array([[20, 10, 22, 12, 24],
              [15, 6, 2, 8, 4],
              [11, 21, 17, 13, 18],
              [25, 1, 5, 23, 3],
              [7,14,19,9,16]])

assert set(best.flatten()) == set(range(1, 26))

def cost(x):
    min_dist = 4
    total = 0

    if x.shape[0] == x.shape[1]:
        if x[0,3] != 12:
            total += 100
        if x[4, 1] != 14:
            total += 100
        if x[0, 1] != 10:
            total += 100
        if x[2, 2] != 13:
            total += 100
        if x[4, 3] != 16:
            total += 100
        total += 1 if np.abs(65 - np.sum(np.diagonal(x))) else 0
        total += 1 if np.abs(65 - np.sum(np.diag(np.fliplr(x)))) else 0
        for col in x.T:
            total += 1 if np.abs(65 - np.sum(col)) else 0
##    for row in x:
##        total += 1 if np.abs(65 - np.sum(row)) else 0
    for i in range(x.shape[0]):
        for j in range(x.shape[1]):
            if 0 < i: # check above
                total += np.abs(x[i-1,j] - x[i,j]) < min_dist
            if i < x.shape[0] - 1: #check below
                total += np.abs(x[i+1,j] - x[i,j]) < min_dist
            if 0 < j: # check left
                total += np.abs(x[i,j-1] - x[i,j]) < min_dist
            if j < x.shape[1] - 1: #check right
                total += np.abs(x[i,j+1] - x[i,j]) < min_dist
            if 0 < i and 0 < j: # check above left
                total += np.abs(x[i-1,j-1] - x[i,j]) < min_dist
            if i < x.shape[0] - 1 and j < x.shape[1]-1: # check below right
                total += np.abs(x[i+1,j+1] - x[i,j]) < min_dist
            if 0 < i and j < x.shape[1]-1: # check above right
                total += np.abs(x[i-1,j+1] - x[i,j]) < min_dist
            if i < x.shape[0] - 1 and 0 < j: # check above left
                total += np.abs(x[i+1,j-1] - x[i,j]) < min_dist

    return total

all_rows = [perm for perm in permutations(range(1,26), r=5) if sum(perm) == 65]
all_rows = [row for row in all_rows if (10 not in row and 12 not in row) or (10 in row and 12 in row)]
all_rows = [row for row in all_rows if (14 not in row and 16 not in row) or (14 in row and 16 in row)]
all_rows = [row for row in all_rows if (13 not in row) or (13 in row and 10 not in row and 14 not in row)]
all_rows = [row for row in all_rows if (10 not in row) or (row[1] == 10)]
all_rows = [row for row in all_rows if (12 not in row) or (row[3] == 12)]
all_rows = [row for row in all_rows if (13 not in row) or (row[2] == 13)]
all_rows = [row for row in all_rows if (14 not in row) or (row[1] == 14)]
all_rows = [row for row in all_rows if (16 not in row) or (row[3] == 16)]

for j, row1 in enumerate(all_rows):
    print((j+1), len(all_rows))
    if row1[1] == 10 and row1[3] == 12:
        for row2 in all_rows:
            if not set(row1).intersection(set(row2)) and not cost(np.array([row1, row2])):
                for row3 in all_rows:
                    if row3[2] == 13 and np.all([not set(i).intersection(set(row3)) for i in [row1, row2]]) and not cost(np.array([row1, row2, row3])):
                        for row4 in all_rows:
                            if np.all([not set(i).intersection(set(row4)) for i in [row1, row2, row3]]) and not cost(np.array([row1, row2, row3, row4])):
                                for row5 in all_rows:
                                    if row5[1] == 14 and row5[3] == 16 and np.all([not set(i).intersection(set(row5)) for i in [row1, row2, row3, row4]]) and not cost(np.array([row1, row2, row3, row5])):
                                        if cost(best) > cost(np.array([row1, row2, row3, row4, row5])):
                                            best = np.array([row1, row2, row3, row4, row5])
                                            print(cost(best), best, '\n')
                                        if not cost(np.array([row1, row2, row3, row4, row5])):
                                            print(np.array([row1, row2, row3, row4, row5]), '\n')
                                            quit()
                                    else:
                                        continue
                            else:
                                continue
                    else:
                        continue
            else:
                continue
    else:
        continue

And here we finally have the solution:

[[ 19 10 21 12 3] [ 15 1 17 8 24] [ 6 22 13 4 20] [2 18 9 25 11] [ 23 14 5 16 7]]