Opgelost met AI: 18 jaar oude wiskundige puzzel ontcijferd

Met behulp van een AI-systeem is de auteur erin geslaagd een wiskundige puzzel op te lossen die al 18 jaar onopgelost what. De zogenaamde magische zeshoeken konden op een voorheen onbekende manier worden opgelost met standaard hardware. De AI die hiervoor werd gebruikt hielp bij het ontwikkelen van het oplossingsprogramma. De rest what te danken aan de eigen intelligentie van een niet-wiskundige.

Waar gaat het over?

Het wordt aangetoond dat met behulp van kunstmatige intelligentie een tot nu toe onoplosbaar wiskundig (NP-schwer) probleem door een informaticus met onderontwikkelde wiskundekennis kan worden opgelost. NP-schwer zijn de moeilijkste problemen, omdat ze meestal niet in eindige tijd kunnen worden opgelost door alleen maar te proberen, en omdat er geen algoritme is dat een garantie biedt voor het vinden van een oplossing.

AI werd hier gebruikt als middel om een doel te bereiken. Menselijke interventie what ook nodig. Zonder AI zou de getoonde oplossing echter nooit zijn gerealiseerd.

18 jaar lang what er geen oplossing voor het probleem, maar nu wel. Met AI.

Naast dit wordt er nog vermeld dat de oplossing hier duidelijk moeilijker te vinden what dan de beste oplossing tot nu toe, die al 18 jaar oud is! Het oorspronkelijke probleem gaat terug tot het jaar 1887, toen de Stralsunder stadsbouwmeester Ernst von Haselberg zijn fascinatie voor magische hexagons ontdekte. Later maakte Martin Gardner dit probleem wereldberoemd.

Inleiding

AI kan enorm veel presteren als men haar goed gebruikt. Het volgende concreet voorbeeld laat zien met een echt, voor de wiskunde relevant resultaat hoe AI het werk aanzienlijk kan vergemakkelijken. Voor dit genoemde probleem werd het werk niet alleen vergemakkelijkt, maar werd de oplossing zelfs mogelijk gemaakt. Zonder AI zouden er geen van deze hier voorgestelde oplossingen (vanaf N = 7) zijn geweest.

Gegevensbescherming, auteursrecht, handelsgeheimen

Auch al zijn geen persoonsgegevens verwerkt: De oplossing liep op een eigen infrastructuur. Het gaat ook om zoiets als een „Handelsgeheim“. De oplossingsweg voor de magische hexagone lijkt in deze vorm niet bekend te zijn.

Wie je iemand uit verlegenheid een Wikipedia-afbeelding op zijn website wil inbinden, zou hij beter tien keer na moeten denken. De grafiek in de volgende paragraaf is zelf gemaakt. Wie echter een vergelijkbaar hexaagon (met een andere oplossing) van de Duitse Wikipedia-pagina wilt nemen, zal aan de juridisch noodzakelijke rechtvaardigingsverklaringen voor de licentie CC-BY-SA-3.0 stranden. Net zoals de auteur zeven jaar geleden deed. Toen had een zelfbenoemde plagiatsjager (fotograaf) na verkeerde gebruik van de door hem op Wikipedia "gratis" beschikbaar gestelde afbeeldingen gezocht. In het besef dat de rechtvaardigingsverklaring alleen door intieme kennissen correct kan worden gevolgd. Helaas had de plagiatsjager enige problemen met de bescherming van zijn persoonlijke gegevens op zijn websites en moeite met de identificatie van de aanbieder. Zo kwam het dat hij zijn rekening terugtrok, toen hij werd gewezen…

Magische zeshoeken

Het gaat over magische zeshoeken. Wat zijn magische zeshoeken?

Magische hexagone zijn zeshoeken met bepaalde Eigenschappen en hebben een ordegetal, dat N genoemd wordt. Dit ordegetal zegt uit hoeveel cellen (wabben) elke buitenrand van het zeshoek bestaat. Hier is een voorbeeld:

Deze magische zeshoek van orde N = 3 heeft 3 honingraten in elke buitenrand. Het aantal honingraten is 19 en volgt de formule 3N²-3N+1. In totaal bestaat deze zeshoek uit 15 rijen. Deze 15 rijen zijn:

• 5 horizontale rijen
• 2 Hauptdiagonalen
• 4 zijdiagonalen buiten
• 4 zijdiagonalen binnen
• = 15 rijen

Nu komt het Magisch: Een magisch hexagon (van orde 3) is alleen magisch als alle 15 rijen dezelfde sommen hebben en alle getallen in de cellen geheel zijn en elke van deze getallen afkomstig is uit een op elkaar volgende rij en elk getal precies één keer gebruikt werd. Het aantal rijen is eveneens het aantal (van elkaar afhankelijke) vergelijkingen die tegelijkertijd opgelost moeten worden. Voor een magisch zesdegtal zijn er altijd meerdere oplossingen.

Figuurlijk gesproken zien de 15 rijen in de kleinste betekenisvolle magische zeshoek er zo uit (volgorde 1 laten we weg omdat de corresponderende zeshoek uit precies één honingraat bestaat; volgorde 2 is niet mogelijk):

Je ziet 5 diagonale rijen met rode markeringen, 5 diagonale rijen met groene markeringen en 5 horizontale rijen met blauwe markeringen, dus 15 rijen. Elk van de 15 rijen moet dus dezelfde som hebben over alle kammen in de betreffende rij. Positieve getallen worden vaak gebruikt voor kleinere orders omdat ze gemakkelijker te visualiseren zijn. In het bovenstaande voorbeeld en ook in de volgende voorbeelden en nieuw geproduceerde resultaten zijn echter getallen van -X tot X gebruikt. Voor N = 3 komt de X overeen met het waardebereik van -9 tot 9. Dit bereik kan worden bepaald door: (aantal kammen – 1) / 2, dus (19 – 1)/2 = 9.

De fascinatie voor deze magische zesjes bevalt veel mensen. Zo werd bijvoorbeeld in het jaar 2022 een genetische algoritme ontwikkeld om mini-hexagons van de orde N = 3 op te lossen. Dit mini-hexagon heeft 19 velden en 15 rijen. We zullen een hexagon oplossen, dat de orde N = 9 en 217 velden alsmede 51 rijen heeft! De complexiteit neemt dus aanzienlijk toe bij hogere ordeningen.

Voor de bovenstaande symmetrische waarde