2
$\begingroup$

I found the definition that a relaxed magic square of type $n\times n$ has row and column sums constant, and all numbers from $1$ to $n^2$ appears exactly once. How can one enumerate those, like how many $4\times 4$ squares has of upper left number at most $5$?

$\endgroup$
  • $\begingroup$ The word enumerate often has the slightly specialized meaning in combinatorics of "list all possibilities", as opposed to simply "count all possibilities". Is that the case with your Question? $\endgroup$ – hardmath Aug 16 '14 at 21:02
  • $\begingroup$ You might be able to simplify the problem with a bit of group theory... note that relaxed magic square are preserved under row or column swap and rotations. $\endgroup$ – Jack M Aug 16 '14 at 21:05
  • $\begingroup$ I'm trying to find a method to count the number of squres having upper left corner at most 5. $\endgroup$ – student Aug 16 '14 at 21:08
  • 1
    $\begingroup$ I hope this isn't a stupid remark, but have you tried exhaustive computer search? Computers are really good for that kind of thing. $\endgroup$ – MJD Aug 16 '14 at 21:26
  • 2
    $\begingroup$ Since your question is “How can one enumerate those”, my answer is: get better at programming the computer to perform exhaustive searches. There is a body of technique you can learn that will help you solve this particular kind of problem. Alas, a more detailed answer would be too long for a comment, and is off-topic for this site anyway. $\endgroup$ – MJD Aug 16 '14 at 22:55
1
$\begingroup$

Using a modfied version of the Perl program at this MSE link that is deterministic rather than randomized I was able to confirm the count $171720$ of the total number of relaxed magic squares with a value from one to five in the upper left corner. (The Perl script could probably profit from a re-write in C.)

This is the beginning of the list:

001 002 015 016 
006 011 007 010 
013 012 004 005 
014 009 008 003 

001 002 015 016 
006 011 007 010 
014 009 008 003 
013 012 004 005 

001 002 015 016 
006 011 010 007 
013 009 004 008 
014 012 005 003 

001 002 015 016 
006 011 010 007 
014 012 005 003 
013 009 004 008 

001 002 015 016 
007 008 009 010 
012 011 006 005 
014 013 004 003 

001 002 015 016 
007 008 009 010 
012 013 004 005 
014 011 006 003 

001 002 015 016 
007 008 009 010 
012 013 006 003 
014 011 004 005 

001 002 015 016 
007 008 009 010 
014 011 004 005 
012 013 006 003 

001 002 015 016 
007 008 009 010 
014 011 006 003 
012 013 004 005 

001 002 015 016 
007 008 009 010 
014 013 004 003 
012 011 006 005 

001 002 015 016 
007 008 010 009 
012 011 005 006 
014 013 004 003 

001 002 015 016 
007 008 010 009 
012 011 006 005 
014 013 003 004 

001 002 015 016 
007 008 010 009 
014 013 003 004 
012 011 006 005 

001 002 015 016 
007 008 010 009 
014 013 004 003 
012 011 005 006 

001 002 015 016 
007 010 006 011 
012 013 005 004 
014 009 008 003 

001 002 015 016 
007 010 006 011 
014 009 008 003 
012 013 005 004 

001 002 015 016 
007 010 011 006 
012 009 005 008 
014 013 003 004 

001 002 015 016 
007 010 011 006 
012 013 005 004 
014 009 003 008 

001 002 015 016 
007 010 011 006 
014 009 003 008 
012 013 005 004 

001 002 015 016 
007 010 011 006 
014 013 003 004 
012 009 005 008 

001 002 015 016 
007 011 006 010 
012 008 009 005 
014 013 004 003 

001 002 015 016 
007 011 006 010 
012 013 004 005 
014 008 009 003 

And this is the end of the list:

005 016 012 001 
015 003 002 014 
010 007 011 006 
004 008 009 013 

005 016 012 001 
015 003 002 014 
010 009 007 008 
004 006 013 011 

005 016 012 001 
015 006 002 011 
004 003 013 014 
010 009 007 008 

005 016 012 001 
015 006 002 011 
004 009 007 014 
010 003 013 008 

005 016 012 001 
015 006 002 011 
004 009 013 008 
010 003 007 014 

005 016 012 001 
015 006 002 011 
010 003 007 014 
004 009 013 008 

005 016 012 001 
015 006 002 011 
010 003 013 008 
004 009 007 014 

005 016 012 001 
015 006 002 011 
010 009 007 008 
004 003 013 014 

005 016 012 001 
015 008 002 009 
003 004 013 014 
011 006 007 010 

005 016 012 001 
015 008 002 009 
004 003 014 013 
010 007 006 011 

005 016 012 001 
015 008 002 009 
010 007 006 011 
004 003 014 013 

005 016 012 001 
015 008 002 009 
011 006 007 010 
003 004 013 014 

005 016 012 001 
015 009 002 008 
004 003 013 014 
010 006 007 011 

005 016 012 001 
015 009 002 008 
004 006 013 011 
010 003 007 014 

005 016 012 001 
015 009 002 008 
010 003 007 014 
004 006 013 011 

005 016 012 001 
015 009 002 008 
010 006 007 011 
004 003 013 014 

005 016 012 001 
015 009 004 006 
003 007 010 014 
011 002 008 013 

005 016 012 001 
015 009 004 006 
011 002 008 013 
003 007 010 014 

Here is a central segment:

003 009 014 008 
016 006 001 011 
002 015 012 005 
013 004 007 010 

003 009 014 008 
016 006 001 011 
005 004 012 013 
010 015 007 002 

003 009 014 008 
016 006 001 011 
005 012 004 013 
010 007 015 002 

003 009 014 008 
016 006 001 011 
005 012 015 002 
010 007 004 013 

003 009 014 008 
016 006 001 011 
005 015 012 002 
010 004 007 013 

003 009 014 008 
016 006 001 011 
010 004 007 013 
005 015 012 002 

003 009 014 008 
016 006 001 011 
010 007 004 013 
005 012 015 002 

003 009 014 008 
016 006 001 011 
010 007 015 002 
005 012 004 013 

003 009 014 008 
016 006 001 011 
010 015 007 002 
005 004 012 013 

003 009 014 008 
016 006 001 011 
013 004 007 010 
002 015 012 005 

003 009 014 008 
016 006 001 011 
013 004 012 005 
002 015 007 010 

003 009 014 008 
016 006 001 011 
013 007 004 010 
002 012 015 005 

003 009 014 008 
016 006 001 011 
013 012 004 005 
002 007 015 010 

003 009 014 008 
016 006 011 001 
002 012 005 015 
013 007 004 010 

003 009 014 008 
016 006 011 001 
005 015 002 012 
010 004 007 013 

003 009 014 008 
016 006 011 001 
010 004 007 013 
005 015 002 012 

I can post the code if anyone is interested though like I said a re-write in C would probably be the better choice.

$\endgroup$
0
$\begingroup$

For any integer $n \ge 0$, $\begin{bmatrix}2&13+n&12&7\\11&8&1&14+n\\5&10&15+n&4\\16+n&3&6&9 \end{bmatrix}$ is a magic square with an upper left number of $2$. This gives us infinitely many such magic squares satisfying the given conditions.

EDIT: The above was posted before the OP added the constraint that the relaxed magic square contain each of the integers between $1$ and $n^2$ exactly once.

$\endgroup$
  • $\begingroup$ Often a 4×4 magic square is restricted to contain exactly the elements 1…16. $\endgroup$ – MJD Aug 16 '14 at 22:32
0
$\begingroup$

I am posting a solution in C which is blazingly fast compared to the Perl program. (I worked on this problem before but I cannot now seem to locate the post.) The C program takes minutes to solve a problem where Perl takes hours even though both use the same algorithm. Note that we can do much better with a randomized algorithm, but here the problem seems to ask for a deterministic solution.

Here is a central segment for the four by four:

004 011 006 013 
014 016 001 003 
007 005 012 010 
009 002 015 008 

004 011 006 013 
014 016 001 003 
009 002 015 008 
007 005 012 010 

004 011 006 013 
014 016 001 003 
009 005 012 008 
007 002 015 010 

004 011 006 013 
014 016 003 001 
007 005 010 012 
009 002 015 008 

004 011 006 013 
014 016 003 001 
009 002 015 008 
007 005 010 012 

004 011 006 013 
015 001 016 002 
003 014 007 010 
012 008 005 009 

004 011 006 013 
015 001 016 002 
005 008 009 012 
010 014 003 007 

The output of the deterministic algorithm for the five-by-five starts with

001 002 013 024 025
003 008 014 017 023
018 016 015 009 007
021 019 011 010 004
022 020 012 005 006

001 002 013 024 025
003 008 014 017 023
018 016 015 009 007
022 020 012 005 006
021 019 011 010 004

001 002 013 024 025
003 008 014 017 023
018 016 015 010 006
021 019 012 009 004
022 020 011 005 007

001 002 013 024 025
003 008 014 017 023
018 016 015 010 006
021 020 011 009 004
022 019 012 005 007

001 002 013 024 025
003 008 014 017 023
018 016 015 010 006
021 020 012 005 007
022 019 011 009 004

001 002 013 024 025
003 008 014 017 023
018 016 015 010 006
022 019 011 009 004
021 020 012 005 007

001 002 013 024 025
003 008 014 017 023
018 016 015 010 006
022 019 012 005 007
021 020 011 009 004

001 002 013 024 025
003 008 014 017 023
018 016 015 010 006
022 020 011 005 007
021 019 012 009 004

Now for the five-by-five and the six-by-six I had the algorithm start by assigning a random order to the values being tried and continue deterministically thereafter, which will continue to produce all assignments, only in a different order. This gave the following segment for the five-by-five:

001 002 023 020 019
005 018 003 014 025
022 015 017 007 004
013 021 012 008 011
024 009 010 016 006

001 002 023 020 019
005 018 003 014 025
022 015 017 004 007
024 009 010 016 006
013 021 012 011 008

001 002 023 020 019
005 018 003 014 025
022 015 017 004 007
013 021 012 011 008
024 009 010 016 006

001 002 023 020 019
005 018 003 014 025
022 015 013 008 007
021 006 017 011 010
016 024 009 012 004

001 002 023 020 019
005 018 003 014 025
022 015 013 008 007
016 024 009 012 004
021 006 017 011 010

001 002 023 020 019
005 018 003 014 025
022 015 010 007 011
024 009 012 016 004
013 021 017 008 006

001 002 023 020 019
005 018 003 014 025
022 015 010 007 011
013 021 017 008 006
024 009 012 016 004

For the six-by-six, we get the segment

001 021 028 036 013 012
031 034 027 005 004 010
033 016 007 024 006 025
009 035 008 015 026 018
023 002 019 020 030 017
014 003 022 011 032 029

001 021 028 036 013 012
031 034 027 005 004 010
033 016 007 024 006 025
009 035 008 015 026 018
014 003 022 011 032 029
023 002 019 020 030 017

001 021 028 036 013 012
031 034 027 005 004 010
033 016 007 024 006 025
009 035 008 011 030 018
023 003 022 020 026 017
014 002 019 015 032 029

001 021 028 036 013 012
031 034 027 005 004 010
033 016 007 024 006 025
009 035 008 011 030 018
023 002 022 015 032 017
014 003 019 020 026 029

001 021 028 036 013 012
031 034 027 005 004 010
033 016 007 024 006 025
009 035 008 011 030 018
014 003 019 020 026 029
023 002 022 015 032 017

001 021 028 036 013 012
031 034 027 005 004 010
033 016 007 024 006 025
009 035 008 011 030 018
014 002 019 015 032 029
023 003 022 020 026 017

001 021 028 036 013 012
031 034 027 005 004 010
033 016 007 024 006 025
009 035 008 018 026 015
023 003 022 011 032 020
014 002 019 017 030 029

And this is the code, compiled with GCC 4.8.3.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

void search(int **sq, int N, int sum, int sofar, int *seen, 
            int *cref, int pflag)
{
  int row, col;

  if(sofar == N*N){
    if(pflag){
      for(row = 0; row < N; row++){
        for(col = 0; col < N; col++){
          printf("%03d ", sq[row][col]);
        }
        printf("\n");
      }
      printf("\n");
    }

    (*cref)++;
    return;
  }

  int loc_col = sofar % N;
  int loc_row = (sofar - loc_col) / N;

  int nxt;
  for(nxt = 1; nxt <= N*N; nxt++){
    if(!seen[nxt]){
      sq[loc_row][loc_col] = nxt;
      seen[nxt] = 1;

      int no_admit = 0, empty, sval;

      for(row = 0; row < N; row++){
        empty = 0; sval = 0;

        for(col = 0; col < N; col++){
          if(sq[row][col] == -1){
            empty++;
          }
          else{
            sval += sq[row][col];
          }
        }

        if((empty == 0 && sval != sum) ||
           (empty > 0 && sval >= sum)){
          no_admit = 1;
          break;
        }
      }

      for(col = 0; col < N; col++){
        empty = 0; sval = 0;

        for(row = 0; row < N; row++){
          if(sq[row][col] == -1){
            empty++;
          }
          else{
            sval += sq[row][col];
          }
        }

        if((empty == 0 && sval != sum) ||
           (empty > 0 && sval >= sum)){
          no_admit = 1;
          break;
        }
      }


      if(!no_admit){
        search(sq, N, sum, sofar + 1, seen, 
               cref, pflag);
      }

      seen[nxt] = 0;
      sq[loc_row][loc_col] = -1;
    }
  }
}


int main(int argc, char **argv)
{
  int printflag = 1;
  int N = 4;
  int maxcorner = 5;

  if(argc > 1){
    printflag = (!strcmp(argv[1], "yes") ? 1 : 0);
  }

  if(argc > 2){
    N = atoi(argv[2]);

    if(N < 1){
      fprintf(stderr, "dimension is a positive int, "
              "got %d\n", N);
      exit(-1);
    }
  }

  if(argc > 3){
    maxcorner = atoi(argv[3]);

    if(maxcorner < 1 || maxcorner > N*N){
      fprintf(stderr, "max corner is a positive int "
              "less than %d, got %d", N*N, maxcorner);
      exit(-2);
    }
  }

  int buf[N*N];
  int *sq[N];

  int row, col;
  for(row = 0; row < N; row++){
    sq[row] = buf + row*N;

    for(col = 0; col < N; col++){
      sq[row][col] = -1;
    }
  }

  int sum = N*(N*N+1)/2;

  int pos, seen[N*N+1];
  for(pos = 0; pos < N*N+1; pos++){
    seen[pos] = 0;
  }

  int count = 0; int corner;
  for(corner = 1; corner <= maxcorner; corner++){
    sq[0][0] = corner; seen[corner] = 1;

    search(sq, N, sum, 1, seen, &count, printflag);

    sq[0][0] = -1; seen[corner] = 0;
  }

  fprintf(stderr, "%d\n", count);

  return 0;
}

Addendum. Here is a seven-by-seven that the second version produced:

001 011 034 038 009 035 047
041 015 018 032 014 033 022
036 026 048 025 017 010 013
042 029 008 006 049 021 020
045 012 019 030 027 037 005
003 039 002 040 031 016 044
007 043 046 004 028 023 024

001 011 034 038 009 035 047
041 015 018 032 014 033 022
036 026 048 025 017 010 013
042 029 008 006 049 021 020
045 012 019 030 027 037 005
007 043 046 004 028 023 024
003 039 002 040 031 016 044
$\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.