Project Magic Square

waarom?

Tijdens een bezoek aan Barcelona kwam ik in aanraking met een magisch vierkant. Gaudi had aan een zijde van de Sagrada Familia de volgende matrix geplaatst:

Deze magische vierkanten zijn mooi symetisch (ook de som vier kwadranten is gelijk) en facinerend.

Wat is een magisch vierkant?

Een magisch vierkant is een matrix welke aan de volgende eigenschap voldoet:
iedere rij op geteld is evenveel als iedere kolom opgeteld wat evenveel is als de diagonale.
In dit geval dus 33. Iedere rij en kolom is opgeteld 33.

Wat afwijkend is aan dit magisch vierkant boven de standaard magische vierkanten, is dat het uit meerdere dezelfde getallen bestaat. Bij een standaard magisch vierkant wordt ieder getal (van 0 tot 15 of 1 tot 16) slechts eenmaal gebruikt.

De uitdaging!

Toen kwam de vraag in mij op, hoeveel van dit soort vierkanten bestaan er, kan ik dit bereken. Doordat getallen meerdere malen kunnen voorkomen kan je niet een of ander backtrack gebaseerd algoritme gebruiken. Alles uitproberen lijkt doenbaar er zijn slechts 16^16 mogelijkheden. Dat zijn er dus:

18.446.744.073.709.551.616

Om het nog enigsinds op te lossen, ben ik de mogelijkheden gaan onderzoeken om dit gedistribureerd te doen. Een computer kan natuurlijk duizenden mogelijkheden per minuut controlleren, maar bij een getal van deze grote is het door 1 computer niet echt te doen. Daarom heb ik het probleem opgedeeld in 268.435.456 deel problemen. ofwel deel vierkanten.

x1 x2 x3 x4
x5 x6 x7 y1
z1 z2 z3 z4
z5 z6 z7 z8

Een deelprobleem is gedefineerd als een block, er zijn dus ruwweg 250 miljoen deelproblemen. Ieder blok is om te zetten in een x1..x7 combinatie. Blok 1 is dus

0 0 0 0
0 0 1 y1
z1 z2 z3 z4
z5 z6 z7 z8

block 127.123 is:

0 0 1 15
0 9 2 y1
z1 z2 z3 z4
z5 z6 z7 z8

y1 is vervolgens te berekenen uit (x1+x2+x3+x4)-(x5+x6+x7)

De waarden vn z1 t.m z8 worden vervolgens door een computer uitgerekend. Dit neemt voor een computer ongeveer 2 minuten tijd in beslag (Pentium 2 Ghz)

Nu zijn er ook zat blocken welk helemaal niet zinvol zijn om te onderzoeken, bijvoorbeeld blok 1, doordat de bovenste rij al kleiner is dan de 2de rij opgeteld heeft het geen zin om het block verder berekenen. Hiervoor zijn er zogeheette blockbuster geintroduceerd.  Deze zoeken alle onzinnige blocks en maken ze onschadelijk. De gewone clients onderzoeken alleen zinnige blokken. Ofwel blokken waarvan een blockbuster heeft opgemerkt dat ze potentiele magische vierkanten kunnen bevatten. De magische clients "proberen" nog 4.294.967.296 mogelijke combinaties uit per block. Er zijn dus meerdere computers bezig met ieder zijn eigen blokje.

Hoe op te lossen?

Hoe dit nu te realiseren, men neme een computer, installeren er MySQL op, en stoppen er 250 miljoen records in. Vervolgens schrijf je een applicatie welke aan de database om een block te geven vraagt welke nog niet opgelost is, niet in gebruik is en welke door een blockbuster als zinvol gezien kan worden. De computer rekent hier 2 minuten aan en geeft indien hij een (of meerdere) magisch vierkant vind dit terug aan de database.

Hoe ver is het project? (15 juli 2004)

de applicatie wordt geoptimaliseerd maar lijkt redelijk goed, (een optimalisatie werd voorgesteld door een vriend van mij om ipv select min(blocknr) from block where done=0 and inuse=0 and blockbuster=1 te veranderen in select blocknr from block where done=0 and inuse=0 and blockbuster=1 limit 0,1 dit om te zorgen dat MySQL niet de hele resultaattabel eerst gaat sorteren en vervolgens het eerste block vrij te geven aan een client). Verder zijn er nog wat andere blockbuster optimalisatie zaken te verwezelijken, maar dit heeft een mindere prioriteit dan het in gang zetten van het project.

Er zitten op dit moment 10 miljoen blokken in de database (database is 800 Mb groot), de blockbusters hebben 350.000 blokken gecontrolleerd en er 21 duizend als mogelijk potentieel magisch gekenmerkt (deze moeten onderzocht worden (wat dus 40 duizend minuten kost 27 computerdagen (P IV 2 Ghz) vierkanten gevonden. Er zijn door de magische clients nu 279 magische vierkanten gevonden.. De verwachting is dat er steeds meer potentiele blokken ontstaat naarmate er grotere getallen en complexere matrices worden geconstruceerd. Het is moeilijk te zeggen hoeveel potentiele blokken er onderzocht moeten worden. uitgaande van 10% van alle blokken. Zou het nog neerkomen op 25 miljoen blokken (van 2 minuten per block). Dat is ruim 95 computer jaren. (met 100 computers is het binnen een jaar opgelost. Dit gaat er wel vanuit dat er van de 250 miljoen blokken 10% zinvol zijn om te onderzoeken. Indien dit niet het geval is, (meer) dan kan het gerust langer duren.
hier een vierkant welke door het systeem gevonden is:

0 0 1 9
7 3 0 0
3 1 6 0
0 6 3 1

Voorbeeld van het programma: (met een saai gevonden magisch vierkant)

Meedoen?

Wil je ook meedoen met het vinden van magische vierkanten? Dat kan nog niet, ik ben nog aan het testen met een aantal computers. Tevens is mijn MySQL server nog niet snel genoeg om een grote stroom (meer dan 100) clients aan te kunnen. Als hier verandering in komt, lees je het hier!