// Skyler Goodell
// 7/9/2011
// Converted from a C program written without methods.
// Determines if a 3x3 grid of numbers is a magic square.

// Generalized by Arup Guha (6/23/2016) to work for squares of size n x n.

import java.util.*;

public class MagicSquareGeneral {

    public static void main(String[] args) {

    	Scanner input = new Scanner(System.in);
    	System.out.println("How many rows in your magic square?");
    	int n = input.nextInt();

        // Create a 2D Array to store the square.
        int[][] square = new int[n][n];

        // Read in the user's magic square.
        System.out.println("Please enter your magic square.");
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                square[i][j] = input.nextInt();

        // Use our two methods to make sure the the square has
        //      the correct numbers and the 'magic' sums.
        // Output if the square is magic or not.
        if (checkFrequency(square) && checkSums(square))
            System.out.println("You have a magic square");
        else
            System.out.println("Not a magic square");
    }

    /* checkFrequency:
     * Make sure that each number 1 through 9 is in the square exactly once.
     *
     * returns: true if each number (1-9) appears exactly once, false otherwise.
     */
    private static boolean checkFrequency(int[][] square)
    {
        // Create an array to store the number of times each number appears.
        int[] freq = new int[square.length*square.length+1];

        // Set each frequency to zero initially.
        // Note: We will NOT use index 0 and we will store how many 1s we see
        //       in index 1, etc.
        for (int i = 1; i < freq.length; i++)
            freq[i] = 0;

        // Loop through each value in the square.
        for (int i = 0; i < square.length; i++)
        {
            for (int j = 0; j < square.length; j++)
            {
                // Invalid number - all values must be between 1 - 9.
                if (square[i][j] < 1 || square[i][j] > square.length*square.length)
                    return false;

                // Increase the frequncy for this number.
                freq[square[i][j]]++;
            }
        }

        // If any number does not appear exactly once then the square is not magic.
        for (int i = 1; i < freq.length; i++)
            if (freq[i] != 1)
                return false;

        return true;
    }

    /* checkSums:
     * Check that the sum of the rows, columns and diagonals all equal 15.
     *
     * returns: true is all rows, columns and diagonals equal 15, false otherwise.
     */
    private static boolean checkSums(int[][] square) {
    	return checkRows(square) && checkCols(square) && checkDiag(square);
    }

	/* Returns true iff all rows in square add up to the correct magic square sum. */
    private static boolean checkRows(int[][] square)
    {
    	// Store side length and correct sum.
    	int n = square.length;
    	int correctSum = n*(n*n+1)/2;

        // Check each row.
        for (int i = 0; i < n; i++)
        {
            // Find the sum of row #i.
            int sum = 0;
            for (int j = 0; j < n; j++)
                sum += square[i][j];

            // If this row does not equal 15, then it is not a magic square
            if (sum != correctSum)
                return false;
        }

        // If we make it here, we're good.
        return true;
    }

    /* Returns true iff all columns in square add up to the correct magic square sum. */
    private static boolean checkCols(int[][] square) {

    	// Store side length and correct sum.
    	int n = square.length;
    	int correctSum = n*(n*n+1)/2;

        // Check each column.
        for (int j = 0; j < n; j++)
        {
            // Find the sum of column #j.
            int sum = 0;
            for (int i = 0; i < n; i++)
                sum += square[i][j];

            // If this column does not equal 15, then it is not a magic square
            if (sum != correctSum)
                return false;
        }

        return true;
    }

    /* Returns true iff all diagonals in square add up to the correct magic square sum. */
    public static boolean checkDiag(int[][] square) {

    	// Store side length and correct sum.
    	int n = square.length;
    	int correctSum = n*(n*n+1)/2;

    	// Get sum of forward diagonal.
    	int sum = 0;
    	for (int i=0; i<n; i++)
    		sum += square[i][i];

    	// See if this didn't work.
    	if (sum != correctSum)
    		return false;

    	// Get backward diagonal sum.
    	sum = 0;
    	for (int i=0; i<n; i++)
    		sum += square[i][n-1-i];

		// This is my final check...
        return sum == correctSum;
    }
}