Problem of the Day
A new programming or logic puzzle every Mon-Fri

Given a 3x3 square fill in the numbers 1-9, using each number once, so that each row, column and diagonal add up to the same number. A diagonal must be as long and wide as the square to be counted. For instance, on a standard number pad the only valid diagonals are 1, 5, 9 and 3, 5, 7.

To take this a step further, write a program that can solve this for an NxN square (e.g.: for a 5x5 square use the numbers 1-25).

Comments:

• Carlos - 10 years, 9 months ago

  I had solved this problem before, it only works for odd numbers, for even numbers i believe you need something to remember, used numbers. It's a bit more complicated and unfortnately i don't have the time today. Here's the solution for odd numbers:

  public static int[][] magicSquare;
  
      public static void main(String[] args) {
          testCase();
      }
  
      public static void testCase() {
          createOddSquare(3);
          displaySquare();
          System.out.println("\n\n");
          createOddSquare(5);
          displaySquare();
          System.out.println("\n\n");
          createOddSquare(19);
          displaySquare();
      }
  
      private static void createOddSquare(int s) {
          magicSquare = new int[s][s];            //Will hold the answer
          int r = 0;                              //Runs through the rows
          int c = s / 2;                          //Runs through the columns
          int lR = r;                             //The last row
          int lC = c;                             //The last column
  
          magicSquare[r][c] = 1;
          int mS = s * s;                         //Size of the matrix
          for (int k = 2; k < mS + 1; k++) {
              if (r - 1 < 0) {
                  r = s - 1;
              } else {
                  r--;
              }
  
              if (c + 1 == s) {
                  c = 0;
              } else {
                  c++;
              }
  
              if (magicSquare[r][c] == 0) {
                  magicSquare[r][c] = k;
              } else {
                  r = lR; c = lC;
                  if (r + 1 == s) {
                      r = 0;
                  } else {
                      r++;
                  }
  
                  magicSquare[r][c] = k;
              }
  
              lR = r; lC = c;
          }
      }
  
      private static void displaySquare() {
          for (int j=0; j<magicSquare.length; j++) {
              for (int k=0; k<magicSquare[j].length; k++) {
                  if(magicSquare[j][k] >= 10 && magicSquare[j][k] < 100) {
                      System.out.print(magicSquare[j][k] + "   ");
                  } else if(magicSquare[j][k] >= 100 && magicSquare[j][k] < 1000) {
                      System.out.print(magicSquare[j][k] + "  ");
                  } else if(magicSquare[j][k] >= 1000) {
                      System.out.print(magicSquare[j][k] + " ");
                  } else {
                      System.out.print(magicSquare[j][k] + "    ");
                  }
              }
  
              System.out.print("\n");
          }
      }
  

  reply permalink

• Johnny - 10 years, 9 months ago

  Not sure how to program but the answer for a 3x3 square is

  [2,7,6] [9,5,1] [4,3,8]

  reply permalink

• Q - 10 years, 9 months ago

  So I only have a few minutes but some basics would be to gather the input of box size, figure out how many total squares, and the sum that each row/col/diag should be.

  squaresize = n

  squarecount = squaresize²

  rowcoltotal = ((squarecount(squarecount+1))/2)/squaresize

  From here you can rotate through the lowest available number and highest numbers plus a middle number to get the possible rows/columns then rotate their positions to find the right match up plus diags. You would also have to watch out for some boxes that would not be able to be solved, such as a 2x2 box.

  reply permalink

• Pyro - 10 years, 8 months ago

  So i have this solution in python for n=3, but it dosen't work for n>3. The number of possible permutations are too big. Working on it :D

  import itertools
  
  def print_sol(l):
      print "SUM = ", sum(l[0:3])
      print " "
      print l[0:3]
      print l[3:6]
      print l[6:9]
      print " "
  
  n=3
  numbers_list=range(1,((n**2)+1))
  
  comb=list(itertools.permutations(numbers_list))
  
  print comb
  m=len(comb)
  aux=0
  mm=0
  
  while (aux<m):
      if sum(comb[aux][0:3])==sum(comb[aux][3:6]) and \
         sum(comb[aux][0:3])==sum(comb[aux][6:9]) and \
         sum(comb[aux][0:3])==((comb[aux][0])+(comb[aux][3])+(comb[aux][6])) and \
         ((comb[aux][0])+(comb[aux][3])+(comb[aux][6]))== \
         ((comb[aux][1])+(comb[aux][4]))+(comb[aux][7]) and \
         ((comb[aux][0])+(comb[aux][3])+(comb[aux][6])) == \
         ((comb[aux][2])+(comb[aux][5])+(comb[aux][8])) and \
         ((comb[aux][0])+(comb[aux][3])+(comb[aux][6]))== \
         ((comb[aux][0])+(comb[aux][4]))+(comb[aux][8]) and \
         ((comb[aux][0])+(comb[aux][3])+(comb[aux][6]))== \
         ((comb[aux][2])+(comb[aux][4]))+(comb[aux][6]) :
          print_sol(comb[aux])
          mm=mm+1
      aux=aux+1
  
  print "TESTED COMBINATIONS : ", m
  print "SOLUTIONS : ", mm
  

  reply permalink

• Anonymous - 10 years, 6 months ago

  #python 2.7
  def generate_square(size):
      if size % 2 == 0:
          print "Must be an odd number"
      else:
          square = []
          for i in range (size):
              row = []
  
              for i in range (size):
                  row.append(0)
              square.append(row)
          sum = ((size*size)/2+ 1) * size
          number = 1
          row = 0
          column = size/2
  
          while number <= size*size:
              if square[row][column] == 0:
                  square[row][column] = number
  
                  if (row - 1) >= 0:
                      row = row - 1
                  else:
                      row = size - 1
  
                  column = (column + 1) % size
                  number = number + 1
              else:
                  row = (row + 2) % size
                  if (column - 1) >= 0:
                      column = column - 1
                  else:
                      column = size - 1
  
  
          for k in range(size):
              print square[k], "\n"
  

  reply permalink