Magic Square Classification

Interview

Time limit1sMemory limit128 MB

Summary
Read multiple square matrices and classify each into one of five magic square categories based on row, column, diagonal sums, distinctness, and consecutiveness.
Level

Easy3 of 10

Topics
Matrix, Implementation, Array
Solved
No attempts yet

Problem

Matheos the magician wants to classify square tables of integers by their magical properties. A square has the same number of rows and columns. For each square, define the reference sum S as the sum of the first column.

Classify each square by the following rules.

  • Not Magick: at least one row or column does not sum to S.
  • Semi-Magick Square: every row and every column sums to S, but at least one of the two diagonals does not.
  • Weakly-Magick Square: every row, every column, and both diagonals sum to S.
  • Strongly-Magick Square: every row, every column, and both diagonals sum to S, and all numbers in the square are distinct.
  • Magically-Magick Square: every row, every column, and both diagonals sum to S; all numbers are distinct; and the numbers are consecutive integers with no gaps.

The following 2 x 2 square is a Semi-Magick Square because every row and column sums to 5, but the diagonals do not.

23
32

The following 3 x 3 square is a Magically-Magick Square because every row, column, and diagonal sums to 15, all numbers are distinct, and the numbers are consecutive from 1 through 9.

816
357
492

Given a sequence of squares, write a program that determines which of the five classifications applies to each square.

Input

The input consists of a sequence of squares. Each square begins with an integer n on its own line, the number of rows and columns. It is guaranteed that 2 <= n <= 8. The next n lines each contain n integers. The input ends with a line containing only 0.

Output

For each square, print one line in the form Square k: result, where k is the square number starting from 1. The result must be exactly one of the following strings.

  • Magically-Magick Square
  • Strongly-Magick Square
  • Weakly-Magick Square
  • Semi-Magick Square
  • Not a Magick Square

Examples1

  1. Example 1

    Input
    2
1 1
1 2
2
-2 -3
-3 -2
3
8 1 6
3 5 7
4 9 2
0
    Expected output
    Square 1: Not a Magick Square
Square 2: Semi-Magick Square
Square 3: Magically-Magick Square