import java.util.HashSet;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
try {
Scanner sc = new Scanner(System.in);
int size = sc.nextInt();
MagicSquare m = new MagicSquare(size);
sc.close();
long start = System.currentTimeMillis();
m.solve(0);
long duration = System.currentTimeMillis() - start;
System.out.println("Runtime in ms : " + duration+" = "+duration/1000 + "sec");
System.out.println("There are "+m.solutions+" solutions with mirroring");
} catch (Exception ex) {
ex.printStackTrace();
}
}
}
import java.util.HashSet;
import java.util.Scanner;
public class MagicSquare {
private int[] square;
private int[] row_sum;
private int[] col_sum;
private int magicNumber;
private int size;
private boolean[] usedNumbers;
public int solutions=0;
private int squareSize;
public MagicSquare(int size) {
this.size = size;
this.usedNumbers = new boolean[size * size + 1];
this.square = new int[size * size];
this.row_sum = new int[size];
this.col_sum = new int[size];
this.magicNumber = ((size * size * size + size) / 2);
this.squareSize = size * size;
}
public boolean solve(int x) {
if (x == squareSize && checkDiagonals()) {
for (int i = 0; i < size; i++) {
if (row_sum[i] != magicNumber || col_sum[i] != magicNumber) {
return false; // no solution, backtrack
}
}
solutions++;
System.out.println("Solution: "+solutions);
printSquare();
return false; // serach for next solution
}
// the 1d square is mapped to 2d square
HashSet<Integer> validNumbers = new HashSet<Integer>(); // all valid Numbers from one position
if(x%size == size-1 && magicNumber-row_sum[(x/size)] <= squareSize &&
usedNumbers[magicNumber-row_sum[x/size]] == false) {
validNumbers.add(magicNumber-row_sum[(x/size)]); // All values in a row, except for the last one were set
}
if(x/size == size-1 && magicNumber-col_sum[(x%size)] <= squareSize && //
usedNumbers[magicNumber-col_sum[x%size]] == false) {
validNumbers.add(magicNumber-col_sum[x%size]); // // All values in a col, except for the last one were set
}
if(x%size != size-1 && x/size != size-1) { // for all other positions
for(int i=1; i<usedNumbers.length; i++) {
if (usedNumbers[i]== false) validNumbers.add(i);
}
}
if(validNumbers.size()==0) {
return false; // no valid numbers, backtrack
}
for (int v : validNumbers) {
row_sum[x/size] += v;
col_sum[x%size] += v;
if (row_sum[x/size] <= magicNumber && col_sum[x%size] <= magicNumber) {
square[x] = v;
usedNumbers[v] = true;
if (solve(x + 1) == true) {
return true;
}
usedNumbers[v] = false;
square[x] = 0;
}
row_sum[x/size] -= v;
col_sum[x%size] -= v;
}
return false;
}
private boolean checkDiagonals() {
int diagonal1 = 0;
int diagonal2 = 0;
for(int i=0; i<squareSize; i=i+size+1) {
diagonal1 = diagonal1 + square[i];
}
for(int i=size-1; i<squareSize-size+1; i = i+size-1) {
diagonal2 = diagonal2 + square[i];
}
return diagonal1==magicNumber && diagonal2==magicNumber;
}
private void printSquare() {
for (int i = 0; i < squareSize; i++) {
if(i%size ==0) {
System.out.println();
}
System.out.print(square[i] + " ");
}
System.out.println();
}
}
