The very special matrix

Question

It is asked to find the very special matrix where you put the numbers from $1$ to $16$ in it such that;

• The sum of these $16$ numbers in any horizontal, vertical and diagonal (not only main) line (explained below) will be the same number at least $14$ times (there are $4$ vertical, $4$ horizontal, $8$ diagonal lines in $4$x$4$ matrix)
• In that matrix no number will have any consecutive neighbor, for example if $a_{22}=5$ then $a_{12}$ or $a_{21}$ or $a_{23}$ or $a_{32}$ cannot be $4$ or $6$.

This is actually very like magic square matrix but a little bit more complex.

$\begin{bmatrix} a_{11} &a_{12} &a_{13} &a_{14} \\ a_{21}& a_{22} &a_{23} &a_{24} \\ a_{31} &a_{32} &a_{33} &a_{34} \\ a_{41} &a_{42} &a_{43} &a_{44} \end{bmatrix}$

The diagonal case could be in two directions, with 4 lines for each (colors represents which numbers you are supposed to sum)

(This figure represents only for one direction)

for example;

$a_{13}+ a_{24}+ a_{31} + a_{42}$

As a result, there are 16 possible vertical, horizontal and diagonal lines and you need to have 14 or more same result from these lines!

So you can find such a matrix?

Answer 1

I used a computer. I would be interested to how one can deduce a solution without such help.

The first result it came out with, was this: 1 5 13 9 14 11 2 7 4 8 16 12 15 10 3 6 All lines add to 34 except for the top row and third row. By the way, in many solutions you can swap rows 2 and 4 or columns 2 and 4 to get other solutions. It only fails if it introduces new adjacent consecutive numbers in row/column 1 and the new row/column 2.

If you want all 16 lines to add to the same number (34) then you will have some consecutive numbers adjacent in the grid. Here is one such solution: 1 8 10 15 12-13 3 6 7 2 16 9 14 11 5--4 You can cycle the columns around (e.g. move all columns to the left and move column 1 to column 4) to get other solutions. In this way you can break one of those adjacencies, but not both. For more solutions you can also cycle rows around.

Here is the C# program I wrote:

using System;

namespace test4
{
   internal class MagicSquare
   {
      private static readonly int[][] lines = 
      {
         // rows
         new int[]{0,1,2,3},   new int[]{4,5,6,7},   new int[]{8,9,10,11}, new int[]{12,13,14,15},
         // columns
         new int[]{0,4,8,12},  new int[]{1,5,9,13},  new int[]{2,6,10,14}, new int[]{3,7,11,15},
         // diagonals \
         new int[]{0,5,10,15}, new int[]{1,6,11,12}, new int[]{2,7,8,13},  new int[]{3,4,9,14},
         // diagonals /
         new int[]{3,6,9,12},  new int[]{0,7,10,13}, new int[]{1,4,11,14}, new int[]{2,5,8,15},
      };
      static void Main()
      {
         search(new int[16], new bool[16], 0);
      }

      static void search(int[] board, bool[] used, int ix)
      {
         if (ix == board.Length)
         {
            foreach (int i in board) Console.Write(i+" ");
            Console.WriteLine();
            return;
         }
         for (int i = 0; i <= 15; i++)
         {
            if (!used[i])
            {
               // check for adjacent consecutive numbers
               int x = ix%4;
               int y = ix/4;
               if (x > 0 && Math.Abs(board[y*4 + x - 1] - (i + 1)) == 1) continue;
               if (y > 0 && Math.Abs(board[(y-1) * 4 + x] - (i + 1)) == 1) continue;
               board[ix] = i + 1;
               used[i] = true;
               if (IsOk(board)) search(board, used, ix+1);
               used[i] = false;
               board[ix] = 0;
            }
         }
      }

      static bool IsOk(int[] board)
      {
         int f = 0;
         foreach (int[] line in lines)
         {
            if (board[line[3]] > 0 && board[line[0]] + board[line[1]] + board[line[2]] + board[line[3]] != 34)
            {
               f++;
               if( f>2 ) return false;
            }
         }
         return true;
      }
   }
}