public class MagicSquare {
  final int square[][];
  final boolean used[];
  final int n;
  final int magicSum;
  int total = 0;

  public MagicSquare(int n) {
    square = new int[n][n];
    this.n = n;
    used = new boolean[n*n+1];
    magicSum = n*(n*n+1)/2;
  }

  // handles only rows and columns
  boolean validUpTo(int step) {
    for (int r = 0; r < n; r++) {
      if (step == (r+1)*n-1) {
        int sum = 0;
        for (int c = 0; c < n; c++) { sum += square[r][c]; }
        return (sum == magicSum);
      }
    }

    for (int c = 0; c < n; c++) {
      if (step == n*(n-1)+c) {
        int sum = 0;
        for (int r = 0; r < n; r++) { sum += square[r][c]; }
        return (sum == magicSum);
      }
    }

    return true;
  }

  boolean isValid() {
    int sumD1 = 0;
    int sumD2 = 0;
    for (int i = 0; i < n; i++) {
        sumD1 += square[i][i];
        sumD2 += square[i][n-i-1];
    }

  return (sumD1 == magicSum  && sumD2 == magicSum );
}

boolean solve(int step) {
  if (step == n*n) {
    return isValid();
  }

  for (int val = 1; val <= n*n; val++) {
    if (used[val]) { continue; }

    used[val] = true;
    square[step/n][step%n] = val;
    if (validUpTo(step) && solve(step+1)) {
      return true;
    }
    square[step/n][step%n] = 0;
    used[val] = false;
  }

  return false;
}



public void outputSolution () {
  for (int r = 0; r < n; r++) {
    for (int c = 0; c < n; c++) {
      System.out.print(square[r][c]);
      System.out.print(' ');
    }
    System.out.println();
  }
  System.out.println();
}

void count(int step) {
  if (step == n*n) {
    if (isValid()) {
      total++;
      outputSolution();
    }
    return;
  }

  for (int val = 1; val <= n*n; val++) {
    if (used[val]) { continue; }

    used[val] = true;
    square[step/n][step%n] = val;
    if (validUpTo(step)) {
      count (step+1);
    }
    square[step/n][step%n] = 0;
    used[val] = false;
  }
}
}

//MAIN



public class Main {
  public static void main(String[] args) {
	long startTime = System.currentTimeMillis();
    MagicSquare m = new MagicSquare(4);
    m.solve(0);
    m.outputSolution();

    m = new MagicSquare(4);
    m.count(0);
    System.out.println("There are " + m.total + " possible squares.");

    long stopTime = System.currentTimeMillis();
    long elapsedTime = stopTime - startTime;
    System.out.println(elapsedTime);
  }
}