Contact | Programmeertips

PHP script voor het oplossen van een Magic square met afbeeldingen


Het doel van het spel is om de 9 kaarten zo neer te leggen dat de (halve) afbeeldingen op de kaarten matchen met de (halve) afbeelding op de kaart die er naast ligt (en onder) ligt. Er staan 4 verschillende afbeeldingen verdeeld over de kaarten. De kaarten kunnen ook steeds een kwartslag gedraaid worden.
Tips die mij verder hielpen

1 - Geef de vier halve plaatjes op elke kaart een nummer van 1 t/m 8 in de volgende combinaties: 1/8, 2/7, 3/6, 4/5. Dit betekent dat als de som van de twee naast elkaar liggende kaarten 9 is, de kaarten goed liggen.

2 - Begin met alle mogelijkheden voor de eerste kaart in een array te zetten. Daarna ga je bij al deze mogelijkheden een tweede kaart zoeken. Als er bij de eerste kaart geen tweede gevonden kan worden verwijder je die mogelijkheid uit de array. Dan op zoek naar de derde kaart.

Eerste poging:
Mijn eerste poging was om te beginnen met een willekeurige kaart, daar een tweede bij te zoeken (de eerste die klopte), dan een derde kaart erbij zoeken enzovoort. Het was dan mijn bedoeling om als er geen kaart meer gevonden werd die klopte een stap terug te gaan en daar een andere kaart bij te zoeken en dan weer verder te gaan. Je zou dan vanzelf steeds verder terug gaan en uiteindelijk de juiste combinatie krijgen. In theorie moet het lukken, ik raakte alleen al gauw verstrikt in de if-jes en je zou een heleboel gegevens moeten gaan onthouden zodat je weet welke stap je bent en waar je naar toe moet als je geen match vindt. Na een vijftal avonden heb ik dit maar opgegeven.

Brute Force:
Alle mogelijke kaartcombinaties (300 miljard ofzo) langs gaan en steeds controleren of de kanten die moeten matchen inderdaad matchen. Het was nodig om de timelimit en de memorylimit zo hoog mogelijk te zetten en dan nog ging het niet goed. Na 2,5 uur was het script klaar, maar de browser kon het niet aan en crashte.

Derde poging:
Met tip 2 in gedachten weer met frisse moed begonnen. Dit bleek de gouden tip te zijn, want hiermee lukte het. Het was nog wel een heel gedoe om de array zo te krijgen dat ik er gemakkelijk mee kon werken en om de rotaties te vertalen naar code, maar het resultaat was goed.

De oplossing wordt verbluffend snel gevonden. In 0.1 seconde heeft het script ontdekt wat de goede combinatie is. Eigenlijk zijn er 4 combinaties mogelijk, maar dat zijn dezelfde alleen anders geroteerd.
Oplossing Magic Square

Bij een andere gelijksoortige puzzel zijn er 4 oplossingen, dit komt omdat er twee kaarten identiek zijn.

Reactie *
Naam *