SPOJ.com - Problem PROG0590

PROG0590 - Antimagic squares

no tags

A magic square is an arrangement of $n^2$ distinct numbers (i.e. each number is used once) in a square $n \times n$ grid, where the numbers in each row, in each column, and the numbers in the main and secondary diagonals all add up to the same number. The number of rows (and columns) $n$ is called the order of the square. The unique som is called the magic constant or magic sum of the square. As an example, here is an orde-4 magic square having magic sum 34.

16	3	2	13
5	10	11	8
9	6	7	12
4	15	14	1

This famous magic square occurs in Albrecht Dürer's engraving Melencolia I, and is believed to be the first seen in European art. The sum 34 can be found in the rows, columns, diagonals, each of the quadrants, the center four squares, and the corner squares (of the $4 \times 4$ as well as the four contained $3 \times 3$ grids). This sum can also be found in the four outer numbers clockwise from the corners ($3+8+14+9$) and likewise the four counter-clockwise (the locations of four queens in the two solutions of the 4 queens puzzle), the two sets of four symmetrical numbers ($2+8+9+15$ and $3+5+12+14$), the sum of the middle two entries of the two outer columns and rows ($5+9+8+12$ and $3+2+15+14$), and in four kite or cross shaped quartets ($3+5+11+15$, $2+10+8+14$, $3+9+7+15$, and $2+6+12+14$). The two numbers in the middle of the bottom row give the date of the engraving: 1514. The numbers 1 and 4 at either side of the date correspond to the letters A and D which are the initials of the artist.

Albrecht Dürer's engraving Melencolia I (1514).

Detail containing the magic square in Albrecht Dürer's engraving Melencolia I (1514).

A heterosquare is an arrangement of $n^2$ distinct numbers (i.e. each number is used once) in a square $n \times n$ grid, where the numbers in each row, in each column, and the numbers in the main and secondary diagonals all add up to a distinct number. As an example, here is an order-4 heterosquare.

2	1	3	4
5	6	7	8
9	10	11	12
13	14	15	16

An antimagic square is a heterosquare whose row, column and diaginal sums are consecutive integers (if arranged in ascending order). As an example, here is an order-4 antimagic square.

2	15	5	13
16	3	7	12
9	8	14	1
6	4	11	10

Assignment

In this assignment we represent a square $n \times n$ grid as a sequence (a list or a tuple) of $n$ elements, that represent the rows of the grid. Each row is itself represented as a sequence (a list or a tuple) of $n$ integers, that represent the successive numbers on that row. Your task is to implement the following five functions, that all take a square $n \times n$ grid as their argument.

A function numbers that returns a set containing all distinct numbers that occur in the square grid.
A function sums that returns a set containing the distinct sums of all rows, columns and diagonals of the square grid.
A function magic that returns a Boolean value, that indicates whether or not the given square is magic.
A function hetero that returns a Boolean value, that indicates whether or not the given square is a heterosquare.
A function antimagic that returns a Boolean value, that indicates whether or not the given square is antimagic.

Example

>>> numbers([[2, 7, 6], [9, 5, 1], [4, 3, 8]])
{1, 2, 3, 4, 5, 6, 7, 8, 9}
>>> numbers([[2, 1, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]])
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}
>>> numbers([[2, 15, 5, 13], [16, 3, 7, 12], [9, 8, 14, 1], [6, 4, 11, 10]])
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}

>>> sums([[2, 7, 6], [9, 5, 1], [4, 3, 8]])
{15}
>>> sums([[2, 1, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]])
{34, 35, 36, 40, 10, 42, 26, 58, 29, 31}
>>> sums([[2, 15, 5, 13], [16, 3, 7, 12], [9, 8, 14, 1], [6, 4, 11, 10]])
{32, 33, 34, 35, 36, 37, 38, 29, 30, 31}

>>> magic([[2, 7, 6], [9, 5, 1], [4, 3, 8]])
True
>>> magic([[2, 1, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]])
False
>>> magic([[2, 15, 5, 13], [16, 3, 7, 12], [9, 8, 14, 1], [6, 4, 11, 10]])
False

>>> hetero([[2, 7, 6], [9, 5, 1], [4, 3, 8]])
False
>>> hetero([[2, 1, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]])
True
>>> hetero([[2, 15, 5, 13], [16, 3, 7, 12], [9, 8, 14, 1], [6, 4, 11, 10]])
True

>>> antimagic([[2, 7, 6], [9, 5, 1], [4, 3, 8]])
False
>>> antimagic([[2, 1, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]])
False
>>> antimagic([[2, 15, 5, 13], [16, 3, 7, 12], [9, 8, 14, 1], [6, 4, 11, 10]])
True

Een magisch vierkant of tovervierkant is een vierkant $n \times n$ rooster dat opgevuld wordt met $n^2$ verschillende natuurlijke getallen (elk getal komt slechts één keer voor), zodat de $n$ rijen, de $n$ kolommen en beide diagonalen allemaal dezelfde som opleveren. Het getal $n$ wordt de orde van het vierkant genoemd. De unieke som wordt de magische constante of het karakteristieke getal van het vierkant genoemd. Hieronder zie je bijvoorbeeld een magisch vierkant van orde 4 met magische constante 34.

16	3	2	13
5	10	11	8
9	6	7	12
4	15	14	1

Dit bekend magisch vierkant komt voor op de gravure Melencolia I (melancholie) van Albrecht Dürer uit 1514. Merk op dat het jaartal van de gravure verwerkt zit in de onderste rij van het vierkant. Dit magische vierkant is niet alleen opmerkelijk omdat alle rijen, kolommen en diagonalen dezelfde som 34 hebben, maar onder meer ook de vier hoekpunten, de vier middelste getallen, de $2 \times 2$ getallen in de linkerbovenhoek, rechterbovenhoek, linkerbenedenhoek en rechterbenedenhoek, en de twee middelste getallen in de eerste en laatste kolom, respectievelijk de bovensten en onderste rij.

Gravure Melancolia I van Albrecht Dürer uit 1514.

Detail met magisch vierkant uit de gravure Melancolia I van Albrecht Dürer uit 1514.

Een heterovierkant is een vierkant $n \times n$ rooster dat opgevuld wordt met $n^2$ verschillende natuurlijke getallen, zodat de $n$ rijen, de $n$ kolommen en beide diagonalen allemaal een verschillende som opleveren. Hieronder zie je bijvoorbeeld een heterovierkant van orde 4.

2	1	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Een antimagisch vierkant is een heterovierkant waarvan de sommen van de rijen, de kolommen en beide diagonalen een opeenvolgende reeks natuurlijke getallen vormen (als ze eerst in stijgende volgorde gesorteerd worden). Hieronder zie je bijvoorbeeld een antimagisch vierkant van orde 4.

2	15	5	13
16	3	7	12
9	8	14	1
6	4	11	10

Opgave

In deze opgave stellen we een vierkant $n \times n$ rooster voor als een sequentie (een lijst of een tuple) met $n$ elementen, die de rijen van het rooster voorstellen. Elke rij wordt op haar beurt voorgesteld als een sequentie (een lijst of een tuple) van $n$ integers, die de opeenvolgende getallen op de rij voorstellen. Gevraagd wordt om de volgende vijf functies te schrijven, waaraan telkens een vierkant $n \times n$ rooster als argument moet doorgegeven worden.

Een functie getallen die een verzameling teruggeeft met alle verschillende getallen die in het vierkant rooster voorkomen.
Een functie sommen die een verzameling teruggeeft met de verschillende sommen van alle rijen, kolommen en diagonalen van het vierkant rooster.
Een functie magisch die een Booleaanse waarde teruggeeft, die aangeeft of het gegeven vierkant een magisch vierkant is.
Een functie hetero die een Booleaanse waarde teruggeeft, die aangeeft of het gegeven vierkant een heterovierkant is.
Een functie antimagisch die een Booleaanse waarde teruggeeft, die aangeeft of het gegeven vierkant een antimagisch vierkant is.

Voorbeeld

>>> sommen([[2, 7, 6], [9, 5, 1], [4, 3, 8]])
{15}
>>> sommen([[2, 1, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]])
{34, 35, 36, 40, 10, 42, 26, 58, 29, 31}
>>> sommen([[2, 15, 5, 13], [16, 3, 7, 12], [9, 8, 14, 1], [6, 4, 11, 10]])
{32, 33, 34, 35, 36, 37, 38, 29, 30, 31}

>>> getallen([[2, 7, 6], [9, 5, 1], [4, 3, 8]])
{1, 2, 3, 4, 5, 6, 7, 8, 9}
>>> getallen([[2, 1, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]])
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}
>>> getallen([[2, 15, 5, 13], [16, 3, 7, 12], [9, 8, 14, 1], [6, 4, 11, 10]])
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}

>>> magisch([[2, 7, 6], [9, 5, 1], [4, 3, 8]])
True
>>> magisch([[2, 1, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]])
False
>>> magisch([[2, 15, 5, 13], [16, 3, 7, 12], [9, 8, 14, 1], [6, 4, 11, 10]])
False

>>> hetero([[2, 7, 6], [9, 5, 1], [4, 3, 8]])
False
>>> hetero([[2, 1, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]])
True
>>> hetero([[2, 15, 5, 13], [16, 3, 7, 12], [9, 8, 14, 1], [6, 4, 11, 10]])
True

>>> antimagisch([[2, 7, 6], [9, 5, 1], [4, 3, 8]])
False
>>> antimagisch([[2, 1, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]])
False
>>> antimagisch([[2, 15, 5, 13], [16, 3, 7, 12], [9, 8, 14, 1], [6, 4, 11, 10]])
True

Submit solution!

Added by:	Peter Dawyndt
Date:	2015-11-11
Time limit:	10s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	PY_NBC