Ved hjælp af et AI-system er det lykkedes forfatteren at løse en matematisk gåde, som havde været uløst i 18 år. Såkaldte magiske sekskanter kunne løses med standardhardware på en hidtil ukendt måde. Den AI, der blev brugt til dette, hjalp med at udvikle løsningsprogrammet. Resten var op til en ikke-matematikers egen intelligens.

Hvad handler den om?

Det vises, at med hjælp fra AI kan et tidligere uopklaret matematiske (NP-svære) problem løses af en datalog med mere underudviklede matematiske kundskaber. NP-svære er de sværste problemer, fordi de ved blot at prøve dem i regelmæssig tid ikke kan løses, og fordi der ikke findes en algoritme, der garanterer en løsning.

AI blev her brugt som et middel til at nå målet. Menneskelig indgriben var også nødvendig. Men uden AI ville den viste løsning aldrig være blevet realiseret.

I 18 år var der ingen løsning på problemet, men det er der nu. Med kunstig intelligens.

Bemærkelsesværdigt er, at løsningen her var meget sværere at finde end den bedste løsning, der allerede er 18 år gammel! Det oprindelige problem går tilbage til år 1887, hvor Stralsunder byarkitekt Ernst von Haselberg opdagede sin fascination for magiske hexagone. Senere gjorde Martin Gardner problemet verdenskendt.

Indledning

AI kan gøre enormt meget, hvis man bruger den rigtigt. Det følgende konkret casestudie viser med et virkeligt, for matematikken relevant resultat, hvordan AI kan lette arbejdet betydeligt. For det nævnte problem blev arbejdet ikke kun lettet, men løsningen overhovedet ikke muliggjort uden AI. Uden AI ville der ikke være nogen af de her præsenterede løsninger (fra N = 7).

Databeskyttelse, ophavsret, forretningshemmeligheder

Selv om der ikke er blevet behandlet personlige oplysninger: Den anvendte løsning kørte på en egen infrastruktur. Det handler også om noget i den retning af et „Forretningshemmelighed“. Vejen til løsningen for de magiske hexagoner synes ikke at være kendt i denne form.

Den der søger at indlægge et Wikipedia-billede på sin hjemmeside af nød, burde tænke ti gange om det. Grafikken i følgende afsnit er selv skabt. Den, der ønsker at hente et lignende hexagon (med en anden løsning) fra den tyske Wikipedia-side, vil støde på de juridiske krav til Oplysninger om ophavsret for licens CC-BY-SA-3.0. Sådan som forfatteren før 7 år siden. Dengang havde en selvudnævnt Plagiatsjäger (fotograf) efter falsk brug af billeder, han på Wikipedia "gratis" til rådighed havde stillet, søgt efter. I det vidste forfatteren, at Urheberangabe kun kunne følges af intime venner. Desværre havde Plagiatsjäger nogle personlige problemer med privatliv på sine hjemmesider og sværdigheder med Anbieterkennung. Så kom det til, at han trak sin regning tilbage, da han blev opmærksommet…

Magiske sekskanter

Det handler om magiske sekskanter. Hvad er magiske sekskanter?

Magiske hexagone er sekskanter med bestemte Egenskaber og har en ordenstal, der kaldes N. Dette ordenstal siger, hvor mange celler hver ydre kant af sekskanterne består af. Her et eksempel:

Denne magiske sekskant af orden N = 3 har 3 honningkager i hver yderkant. Antallet af bikager er 19 og følger formlen 3N²-3N+1. I alt består denne sekskant af 15 rækker. Disse 15 rækker er:

• 5 vandrette rækker
• 2 hoveddiagonaler
• 4 sidediagonaler udenfor
• 4 sidediagonaler indeni
• = 15 rækker

Nu kommer det Magiske: Et magisk hexagon (af orden 3) er kun magisk, hvis alle 15 rækker har samme sum og alle tal i cellerne er hel og hver af disse tal er taget fra en følge af tal og hver af disse tal er brugt præcis én gang. Antallet af rækker er også antallet af (afhængige) ligninger, der skal løses på samme tid. For et magisk sekskanter findes der altid flere løsninger.

Billedligt talt ser de 15 rækker i den mindste meningsfulde magiske sekskant sådan ud (vi udelader rækkefølge 1, fordi den tilsvarende sekskant består af præcis én bikage; rækkefølge 2 er ikke mulig):

Du kan se 5 diagonale rækker med røde markeringer, 5 diagonale rækker med grønne markeringer og 5 vandrette rækker med blå markeringer, hvilket giver 15 rækker. Hver af de 15 rækker skal derfor have den samme sum på tværs af alle kamme i den pågældende række. Positive tal bruges ofte til mindre ordrer, fordi de er lettere at visualisere. I eksemplet ovenfor og også i de følgende eksempler og nyproducerede resultater blev der dog brugt tal fra -X til X. For N = 3 svarer X til værdiområdet fra -9 til 9. Dette område kan bestemmes ved: (antal kamme – 1) / 2, dvs. (19 – 1)/2 = 9.

Fascinationen for disse magiske sekskanter begejstre mange. Så blev der f.eks. i 2022 udviklet en genetisk algoritme, til at løse mini-hexagoner af orden N = 3. Dette mini-hexagon har 19 felt og 15 rækker. Vi vil løse et hexagon, som har orden N = 9 og 217 felt samt 51 rækker! Kompleksiteten stiger altså med højere ordner betydeligt op.

For ovenstående symmetriske værdigruppe (-X til +X) følger som magisk sum M altid 0. Denne Magiske Konstante er ikke så nem at bestemme for andre gitterbeleggninger. Det er heller ikke klart, hvilke talområder en magisk sekskant af orden N hverken kan løses eller overhovedet findes. For eksempel følger der sikkert ingen løsning med tal større end 15 som mindste starttal. Derfor er M = 0 meget charmerende, fordi den først og fremmest kan beregnes, og det ser ud til, at denne sum kunne være mulig for hver orden N.

Løsninger

Je større et sekskantigt område bliver, desto sværere er det at finde dets magiske løsning. Det største kendte magiske sekskantige område er efter forfatterens opdagelse et med kantenlængden N = 8 (se også Wikipedia). Hvis nogen har fundet eller set større sekskantige områder, beder forfatteren om en information.

For magiske hexagone med kantlængde 3 til 6 er løsningen fundet ved brutal udprøvning meget hurtigt ("Brute Force"). Fra N = 7 bliver det spændende.

Der var ikke tidligere nogen løsning på magiske sekskanter af orden 9 (længden af hver yderkant). De har eksisteret siden 10/09/2024.

Kilde: Klaus Meffert og egen forskning.

Wikipedia viser præcis én løsning for N = 7. Løsningen bruger de 128 tal fra 2 til 127 og har den magiske sum af 365. Løsningen blev opdaget i 2006.

Ny løsning til magisk sekskant af orden 7

For at undgå problemer på grund af forkerte copyright-oplysninger har vi selv fundet en løsning:

Wikipedia viser også præcis én løsning for orden 8. Dette blev også opdaget i 2006 (!) af Louis Hoelbling.

Ny løsning til magisk sekskant N = 8

Forfatteren har også fundet sine egne løsninger for N = 8 med et selvudviklet program, der blandt andet er skabt ved hjælp af AI. Denne løsning er forskellig fra den på Wikipedia og lyder:

Den på Wikipedia registrerede løsning af Louis Hoelbling er derfor anderledes, fordi ikke kun nummerbehandlingen er anderledes, men også ikke symmetri er fremherskende. Symmetrisk ville være løsninger, hvis de kunne omformes ved at dreje, spegle eller også ved at vende tegnene på hinanden.

Farveintensiteten i de viste sekskanter angiver antallet af honningtavler, der hver især påvirkes af en honningtavle. Det er klart, at det centrale felt i sekskanten påvirker de andre felter mest. Det er derfor vist med den mørkeste farve. De ydre felter har mindst indflydelse på de andre felter. Mere om dette nedenfor.

Første løsning til magisk sekskant af orden 9

Ifølge forfatterens forskning er der ingen løsning på magiske sekskanter for N = 9. Forfatteren fandt denne løsning den 10/09/2024. Løsningen er:

Løsningen blev fundet af forfatterens løsningssystem, som blev skabt ved hjælp af AI og in-house udvikling. E-mailen med løsningen, som sendes automatisk af løsningssystemet, blev sendt kl. 00:08 den 10/09/2024.

Løsningstilstande består af 51 ligninger og 217 variabler. En variabel er her den tal på en vandrette linje i sekskanteret. Hverken variabel er en del af 3 af de 217 ligninger (da hver variabel svarer til en vandrette linie og hver vandrette linie er præcis en del af 3 rækker i hexagonet). Lyder det ret komplekst og er det også. Med blot at forsøge at gætte sig frem kommer man her ikke rigtigt til mål.

I illustrationen af den magiske sekskant af orden 9 viser farveintensiteten for hver bikube også, hvor mange andre bikuber der er påvirket. Indflydelse betyder, at en ændring i den numeriske værdi på bikuben har en effekt på de andre bikuber, der er påvirket af den numeriske ændring. Konkret ser indflydelsen for magiske sekskanter af orden 9 altid sådan ud:

Midterfeltet påvirker derfor 48 andre honningtavler. Hjørnetavlerne påvirker derimod kun 32 andre tavler. Hver honningtavle er en del af præcis tre rækker. Midterfeltet ligger i tre lige lange rækker, som hver er 17 tavler lang. De 17 er resultatet af 2N-1 (2*9-1). Da midterfeltet ikke tæller med, når det påvirker andre honningtavler, er 3 diagonaler * (17-1) = 3 * 16 = 48. Dette tal er antallet af honningtavler, der påvirkes af midterfeltet, hvilket også kan ses på figuren.

Verifikation af løsningen

Det er generelt en god idé at kontrollere programoutput. Det gælder både konventionelle programmer og AI-output.

Fordi forfatteren er datalog, tror han ikke på sit eget program og den løsning, der er vist ovenfor for sekskanten af orden 9. Den fundne løsning blev derfor genberegnet manuelt. Her er et uddrag af bestræbelserne på at undgå forlegenhed:

Undskyld til alle matematikere, som forhåbentlig ikke vil finde nogen grove fejl i forklaringerne, men helt sikkert formelle mangler, som vil irritere en matematiker.

En matematiker, en fysiker og en datalog er på togrejse gennem Skotland.

Alle tre sidder i samme kupé og kigger ud af vinduet.

Du ser en eng med får. Det ene får er sort.

Datalogen vil gerne komme med et videnskabeligt udsagn og indser det: "Der er sorte får i Skotland."

Fysikeren er oprørt, fordi datalogens udsagn er så upræcist. Ifølge fysikeren er det eneste, der virkelig kan bestemmes, følgende: "Der er mindst ét sort får i Skotland."

Matematikeren er på randen af et kredsløbskollaps. Han kan ikke forstå, at dataloger og fysikere er kommet med så upræcise udsagn. Han meddeler, at vi kun kan konkludere følgende: "I Skotland er der mindst ét får, som er sort på den side, der vender mod os."

Matematikere har altid ret, men det er som regel ikke relevant i praksis (en matematiker bliver spurgt i en flyvende fangenskabsballon, hvor vi er. Hans svar: "50 meter over jorden").

Fysikere har ikke noget at skamme sig over, se Albert Einstein som mesteren over alle klasser.

Informationsfolk har til tider ret, men sådan med praktisk relevans. Sådan er den personlige livserfaring for en informatiker.

Hvordan hjalp AI med løsningen?

Tidligere forsøg fra forfatteren et par år tilbage byggede på Back Tracking og Brute Force med udeladelse af kombinationer, der kunne erkendes som ulovlige fra starten. For N = 7 og N = 8 kunne ingen løsninger fundet blive, selv om programmet var ret godt udviklet. I mellemtiden ville denne tilgang måske være lovende for N = 7, da hardwaren er blevet bedre. Som sprog blev Java brugt, fordi det er en kompilerede sprog, der udføres meget hurtigere end tolkede sprog.

Den nuværende, succesfulde forsøg baserer sig på en rammeplan, der er skabt med AI. Dette program fungerede godt til mindre N allerede, men ikke for det målområde. En håndfuld manuelle justeringer bragte den endelige sejr. Som sprog blev python

Dette er en kommentar i Python, der forklarer hvad programmet gør.

print("Hej verden!") # Denne linje printer "Hej verden!" til skærmen. x = 5 # Her oprettes en variabel x med værdien 5 y = 3 # Her oprettes en variabel y med værdien 3 print(x + y) # Denne linje printer summen af x og y til skærmen brugt, nummer ét blandt AI-sprogene.

Den telefoniske joke på Wer wird Millionär skal snart være historie.

Vi har ikke gjort Python superschnell, så en optimering er blevet udført. Denne optimering baserer sig på et Just-In-Time Compiler (JIT). Programmeringen med det gør ingen sjov, hvis man vil være venlig. Man føler sig 20 år tilbage i tiden hvad angår komfort og tilgængelige funktioner. For at lette problemet blev igen AI brugt. Det var en anden byggemasse af løsningen.

Nogle af de producerede resultater var Løsninger i nærheden. Den Magiske Konstante M blev ikke præcist nået, men næsten. Med hjælp fra to matematik-AI-modeller blev i det mindste overfladisk undersøgt, om man her ikke kunne komme videre med noget heuristik. Ideen var at gøre den Beinahe-Lösung til en rigtig løsning ved skarp omformning. De spurgte matematik-modeller kunne ikke finde en løsning herfor. Det hjalp dog, til at anerkende denne sandsynlige fejlvej som sådan og indsætte ressourcer i en bedre løsningssammenhæng.

Med en egen AI er så mange ting muligt. Eksempelvis telefonjokker-appen: Snart vil dette AI-system nærmere beskrives. Det kan: Spørge via Microsoft og tale modtage, tale til tekst omforme, spørge LLM om, svar fra LLM til tale omforme, svar læse for brugeren frem. Alt lokalt, alt uden Winzigweich's Azure og ChatGPT. Dertil også at tænke på internettet hvis nødvendigt. Eller automatisk kvalitativt højeste indhold fra tillidsværdige kilder til svar indføre, hvis nødvendigt. Man spørger sig selv: Når vil telefonjokker være væk fra "Hvem bliver millionær"?

Konklusion

Med AI kan man finde løsninger, som tidligere var skjulte. Man kan også undgå problemer med ophavsret (let ironi til sidst).

Men i det mindste kan løsningerne i mange tilfælde fremskyndes betydeligt.

Eksemplet med den Magiske Hexagon kunne vise, at nye løsninger med AI-understøttelse selv til NP-svære problemer kan findes. For det første: Den foregående, væsentlig lettere løsning var fra 2006. Den nye løsning blev fundet i 2024, 18 år senere.

Som hardware blev dagens standard anvendt. I alt var to AI-servere samt et AI-laptop og en Low-Cost Server udsted parallelt. De servere er alle i Tyskland af en tysk leverandør været. De servere arbejdede kun uden for åbningstid på problemet, så dagens forretningsgang ikke blev påvirket. Løsningen var fundet efter få dage og et par runder af optimering.

Den næste Udvidelsesfasen af det fundede program til at løse magiske hexagone ville være en fuldstændig parallelisering (CUDA). Præcis til dette formål findes AI-grafikskort. Beregningen vil sikkert gå 40 gange hurtigere frem. Ikke helt uden betydning, når beregninger kan tage uge eller måneder i tid. Denne parallelisering af søgeresultater er både matematisk og programmeringsteknisk kompleks og skal derfor udskydes til senere.

Hvornår løser din virksomhed problemer med AI?

Forfatter til de magiske sekskanter

Klaus Meffert, Idstein, Tyskland

Yderligere oplysninger på Research Gate.

Billedlicens til magiske sekskanter

Alle billeder af magiske sekskanter fra denne artikel må bruges, så længe billederne ikke ændres (skalering eller komprimering af billederne er naturligvis tilladt).

ændrede versioner af billederne må under angivelse af en link på dr-dsgvo.de/magic anvendes.

For velgørende projekter (o.a.) som Wikipedia må følgende billeder anvendes under opgivelse af forfatteren. For andre projekter står de ovenstående billeder med den ovenstående licens til rådighed.

Hvis der er tvivl ved brugen af billeder, så spørg efter: klaus.meffert@dr-dsgvo.de

Forfatteren ville også være glad for at blive informeret, hvis I nævner det magiske syv-uddelte (9) seksten. Tak til Thorsten Müller for at have leveret sin stemme til taleversionen. Bemærkning: Taleversionen er blevet forbedret ved hjælp af en optimering.

Nøglebudskaber i denne artikel

En kunstig intelligens har løst en 18 år gammel uløst matematisk gåde.

Ved hjælp af AI var det muligt at løse dette puslespil, som tidligere ikke kunne løses ved hjælp af traditionelle metoder som backtracking eller brute force.

Magiske sekskanter er sekskanter, hvor hver række har den samme sum, og alle tal i bikagerne bruges.

Hvert tal i bikuben bruges præcis én gang.

Det ordinære tal (N) angiver, hvor mange bikager der er på hver yderkant.

For en magisk sekskant af orden 3 skal der f.eks. fyldes 15 rækker med en bestemt sum.

Den 10. september 2024 blev der fundet en løsning til en magisk sekskant af orden 9, efter at der ikke tidligere havde eksisteret en sådan løsning.

Hver variabel i den magiske sekskant af orden 9 påvirker præcis 48 andre bikager.

Om disse centrale udsagn