Löst med AI: 18 år gammalt matematiskt pussel dechiffrerat

Med hjälp av ett AI-system har författaren lyckats lösa en matematisk gåta som varit olöst i 18 år. Så kallade magiska hexagoner kunde lösas med standardhårdvara på ett tidigare okänt sätt. Den AI som användes för detta hjälpte till att utveckla lösningsprogrammet. Resten var upp till en icke-matematikers egen intelligens.

Vad handlar den om?

Det visas att med hjälp av AI ett tidigare obesvarat matematiskt (NP-svårt) problem kan lösas av en datalog med ganska underutvecklade matematiska kunskaper. NP-svårigheter är de svåraste problemen, eftersom de vanligtvis inte kan lösas inom en begränsad tid genom att bara prova olika saker och för att det inte finns någon algoritm som garanterar att den ger rätt svar.

AI användes här som ett medel för att nå ett mål. Det krävdes också mänsklig inblandning. Men utan AI hade den lösning som visades aldrig kunnat förverkligas.

I 18 år fanns det ingen lösning på problemet, men nu finns det en. Med AI.

Bland annat ska nämnas att lösningen här var svårare att hitta än den bästa tidigare lösning som redan är 18 år gammal! Det ursprungliga problemet går tillbaka till år 1887, då Stralsunders stadsbyggmästare Ernst von Haselberg upptäckte sin fascination för magiska hexagoner. Senare gjorde Martin Gardner problemet världsberömt.

Inledning

AI kan presta enormt mycket om man använder den rätt. Det följande konkret fallstudie visar med ett verkligt, för matematiken relevant resultat hur AI kan underlätta arbetet kraftigt. För det angivna problemet blev arbetet inte bara underlättat utan lösningen blev till och med möjlig. Utan AI hade vi inte haft några av de här presenterade lösningarna (från N = 7).

Dataskydd, upphovsrätt, affärshemligheter

Även om ingen personuppgift har behandlats: Lösningen kördes på en egen infrastruktur. Det handlar också om något slags "commercial secret". Lösningens väg för de magiska hexagonen verkar inte vara känd i denna form.

Den som av ren nödlidande vill infoga ett Wikipedia-bild på sin webbplats, borde nog tio gånger fundera över det. Grafiken i följande avsnitt har skapats själv. Den som däremot vill ta ett liknande hexagon (med en annan lösning) från den tyska Wikipedia-sidan, kommer att misslyckas med de rättsliga Urheberangaberna för licensen CC-BY-SA-3.0, precis som författaren gjorde för sju år sedan. Då hade en självutnämnd Plagiatsjägare (fotograf) sökt efter plagiatet efter att ha använt bilder från Wikipedia på fel sätt. I vetskapen om att Urheberangaberna bara kan följas av nära vänner, hade Plagiatsjägaren haft problem med integritetslagar och svårigheter med upphovsrättsidentifieringarna. Så kom det sig att han drog tillbaka sin faktura när han blev påmind om detta…

Magiska hexagoner

Det handlar om magiska hexagoner. Vad är magiska hexagoner?

Magiska hexagon är sexkanter med vissa Egenskaper och har en ordningstal som kallas N. Detta ordningstal säger hur många celler (vävnader) varje yttre kant på sexkanterna består av. Här ett exempel:

Denna magiska hexagon av ordning N = 3 har 3 honungskakor i varje ytterkant. Antalet bikakor är 19 och följer formeln 3N²-3N+1. Totalt består denna hexagon av 15 rader. Dessa 15 rader är:

• 5 horizontale Reihen
• 2 huvuddiagonaler
• 4 sidodiagonaler utvändigt
• 4 sidodiagonaler inuti
• = 15 rader

Nu kommer det Magiska: Ett magiskt hexagon (av ordningen 3) är bara magiskt om alla 15 rader visar samma summa och alla siffror i cellerna är heltal och varje av dessa siffror har hämtats från en uppföljande rad och varje siffra används exakt en gång. Antalet rader är också antalet (mellan varandra beroende) ekvationer som måste lösas samtidigt. För ett magiskt sexkant finns det alltid flera lösningar.

Bildligt talat ser de 15 raderna i den minsta meningsfulla magiska hexagonen ut så här (vi utelämnar ordning 1 eftersom motsvarande hexagon består av exakt en bikaka; ordning 2 är inte möjlig):

Du kan se 5 diagonala rader med röda markeringar, 5 diagonala rader med gröna markeringar och 5 horisontella rader med blå markeringar, vilket ger 15 rader. Var och en av de 15 raderna måste därför ha samma summa för alla kammar i respektive rad. Positiva tal används ofta för mindre order eftersom de är lättare att visualisera. I exemplet ovan och även i följande exempel och nyproducerade resultat användes dock siffror från -X till X. För N = 3 motsvarar X värdeintervallet från -9 till 9. Detta intervall kan bestämmas genom: (antal kammar – 1) / 2, d.v.s. (19 – 1)/2 = 9.

Fascinationen för dessa magiska sexkanter fascinerar många. Så utvecklades till exempel 2022 en genetisk algoritm för att lösa mini-hexagon av ordningen N = 3. Detta mini-hexagon har 19 fält och 15 rader. Vi kommer att lösa ett hexagon som har ordningen N = 9 och 217 fält samt 51 rader! Komplexiteten ökar betydligt med högre ordningar.

För den ovan nämnda symmetriska värdeområdet (-X till +X) resulterar som magisk summa M alltid i 0. Denna Magiska Konstant är för andra mönsteruppsättningar inte enkelt att beräkna. Det är dessutom inte klart, för vilka talområden ett magiskt sexkantigt nätverk av ordning N överhuvudtaget är lösbar. För N = 5 finns till exempel sannolikt ingen lösning med tal större än 15 som minsta starttal. Därför är M = 0 mycket charmant, för att först och främst vara beräkningsbar och det andra så verkar som om denna summa kunde vara möjlig för varje ordning N.

Lösningar

Ju större ett sexkantigt polygon blir, desto svårare är det att hitta dess magiska lösning. Det största som hittats till dags dato är ett med sidan N = 8 (se även Wikipedia). Om någon har funnit eller sett större sexkantiga polygoner, ber den här författaren om en information.

För magiska hexagon med kantlängd 3 till 6 är lösningen genom brutalt utprovande rätt snabbt hittad ("Brute Force"). Från N = 7 blir det spännande.

Det fanns tidigare ingen lösning för magiska hexagoner av ordning 9 (längden på varje ytterkant). De har funnits sedan 20/09/1024.

Source: Klaus Meffert och egen forskning.

Wikipedia listar exakt en lösning för N = 7. Lösningen använder de 128 talen från 2 till 127 och har den magiska summan 365. Lösningen upptäcktes 2006.

Ny lösning för Magic Hexagon av ordning 7

För att undvika problem på grund av felaktig upphovsrättsinformation har vi själva hittat en lösning:

Wikipedia listar också exakt en lösning för ordning 8. Detta upptäcktes också 2006 (!) av Louis Hoelbling.

Ny lösning för magisk hexagon N = 8

Författaren har också hittat egna lösningar för N = 8 med ett egenutvecklat program som bland annat skapats med hjälp av AI. Denna lösning skiljer sig från den på Wikipedia och lyder:

Den på Wikipedia uppgivna lösning av Louis Hoelbling är därför annorlunda, eftersom inte bara siffrorna har en annan placering, utan också ingen symmetri förekommer. Symmetriskt sett skulle lösningar vara om de kunde omvandlas till varandra genom att vrida, spegla eller även genom att växla tecken.

Färgintensiteten i de hexagoner som visas anger antalet bikakor som var och en påverkas av en bikaka. Det är uppenbart att det centrala fältet i hexagonen påverkar de andra fälten mest. Det visas därför i den mörkaste färgen. De yttre fälten har minst inflytande på andra fält. Mer om detta nedan.

Första lösningen för en magisk hexagon av ordning 9

Enligt författarens forskning finns det ingen lösning för magiska hexagoner för N = 9. Författaren hittade denna lösning den 10/09/2024. Lösningen är:

Lösningen hittades av författarens lösningssystem, som skapades med hjälp av AI och egen utveckling. E-postmeddelandet med lösningen, som skickas automatiskt av lösningssystemet, skickades kl. 00:08 den 10/09/2024.

Lösungsbedingningarna består av 51 ekvationer och 217 variabler. En variabel är här den siffra på en vev i sexsidan. Varje variabel ingår i 3 av de 217 ekvationerna (eftersom varje variabel motsvarar en vev och varje vev ingår exakt i 3 rader i hexagonet). Lyder rätt komplex och är det också. Med blotta försök kommer man inte här till målet.

I illustrationen av den magiska hexagonen av ordning 9 visar färgintensiteten för varje bikaka också hur många andra bikakor som påverkas. Påverkan innebär att en förändring av det numeriska värdet på bikakan har en effekt på de andra bikakorna som påverkas av den numeriska förändringen. Specifikt ser påverkan för magiska hexagoner av ordning 9 alltid ut så här:

Mittfältet påverkar därför 48 andra vaxkakor. Hörnvaxkakorna påverkar däremot bara 32 andra vaxkakor. Varje vaxkaka är en del av exakt tre rader. Mittfältet ligger i tre lika långa rader, som var och en är 17 vaxkakor lång. De 17 är resultatet av 2N-1 (2*9-1). Eftersom mittfältet i sig inte räknas när det påverkar andra vaxkakor, blir 3 diagonaler * (17-1) = 3 * 16 = 48. Detta antal är antalet vaxkakor som påverkas av mittfältet, vilket också framgår av figuren.

Verifiering av lösningen

Det är i allmänhet en god idé att kontrollera programutgångarna. Detta gäller både konventionella program och AI-utgångar.

Eftersom författaren är datavetare tror han inte på sitt eget program och den lösning som visas ovan för hexagonen av ordning 9. Den lösning som hittades räknades därför om manuellt. Här är ett utdrag av ansträngningarna för att undvika pinsamheter:

Vi ber om ursäkt till alla matematiker, som förhoppningsvis inte kommer att hitta några grova fel i förklaringarna, men säkert formella brister som irriterar en matematiker.

En matematiker, en fysiker och en datavetare reser med tåg genom Skottland.

Alla tre sitter i samma kupé och tittar ut genom fönstret.

Du ser en äng med får. Ett får är svart.

Datavetaren vill göra ett vetenskapligt uttalande och inser det: "Det finns svarta får i Skottland."

Fysikern är upprörd över att datavetarens uttalande är så oprecist. Enligt fysikern är det enda som verkligen kan bestämmas följande: "Det finns minst ett svart får i Skottland."

Matematikern är på gränsen till en cirkulationskollaps. Han kan inte förstå att datavetare och fysiker har gjort så felaktiga uttalanden. Han meddelar att vi bara kan dra följande slutsatser: "I Skottland finns det minst ett får som är svart på den sida som vetter mot oss."

Matematiker har alltid rätt, men det är oftast inte relevant i praktiken (en matematiker tillfrågas i en flygande fångenskapsballong var vi befinner oss. Hans svar: "50 meter ovanför marken").

Fysiker har inget att skämmas för, se Albert Einstein som mästaren i alla klasser.

Informationsingenjörer har ibland rätt, då dock med praktisk anknytning. Sådan är den personliga livserfarenheten hos en informationsingenjör.

Hur bidrog AI till lösningen?

Förra försök av författaren från några år sedan byggde på Back Tracking och Brute Force med uteslutning av kombinationer som kunde identifieras som oacceptabla från början. För N = 7 och N = 8 kunde inga lösningar hittas, trots att programmet var ganska utvecklat. Nu skulle denna metod kanske vara lovande för N = 7, eftersom hårdvaran har blivit bättre. Som språk användes Java, eftersom det är en kompilatoriskt språk som kördes betydligt snabbare än tolkade språk.

Den nuvarande, framgångsrika försöken baseras på ett ramprogram som skapats med AI. Detta program fungerade bra för mindre N redan tidigare, men inte för det önskade området. En del manuella justeringar ledde till den slutliga framgången. Som språk användes Källkoden: Python, nummer ett bland AI-språk.

Telefonjokern på Vem vill bli miljonär kommer snart att vara historia.

Vi har inte gjort Python supersnabb, så en optimering har genomförts. Denna optimering baseras på ett Just-In-Time Compiler (JIT). Programmeringen med det är ingen nöje, för att uttrycka sig artigt. Man känner sig 20 år tillbaka i tiden vad gäller komfort och tillgängliga funktioner. För att lösa problemet har man återigen använt sig av AI. Det var en ytterligare pusselbit i lösningen.

Vissa av de producerade resultaten var nästan-lösningar. Den magiska konstanten M uppnåddes inte exakt, men nästan. Med hjälp av två matematik-AI-modeller undersöktes åtminstone på ytan om man inte kunde komma fram till något heuristik här. Idén var att göra den nästan-lösningen till en riktig lösning genom skickligt omformande. De frågade matematikmodellerna kunde inte ge någon lösning för detta. Det hjälpte dock till att upptäcka och erkänna denna sannolika felväg som sådan och investera resurser i en bättre lösningssatsning.

Med en egen AI är så många saker möjliga. Till exempel Telefonjoker-appen: Snart kommer detta AI-system att beskrivas närmare. Det kan: Fråga per Microsoft och språk ta emot, omvandla språk till text, ställa fråga till LLM, omvandla LLM:s svar till språk, läsa upp svaret för användaren. Allt lokalt, allt utan Winzigweich's Azure och ChatGPT. Dessutom kan man också ansluta till internet när det behövs. Eller automatiskt inkludera kvalitativt högkvalitativa innehåll från förtrodda källor för svaret, om det behövs. Man undrar: När kommer Telefonjoker att avskaffas i Wer wird Millionär?

Sammandrag

Med AI kan man hitta lösningar som tidigare varit dolda. Det kan också göra att man slipper upphovsrättsproblem (lite ironi i slutet).

Åtminstone kan dock lösningarna i många fall påskyndas avsevärt.

Med hjälp av Magiska Hexagonen kunde det visas att nya lösningar med AI-stöd faktiskt kan hittas för NP-svåra problem. För referens: Den tidigare, betydligt lättare att hitta lösningen var från 2006. Den nya lösningen hittades 2024, 18 år senare.

Som hårdvara användes idagens standard. I stort sett var två AI-servrar samt ett AI-laptop och en Low-Cost Server parallellt installerade. Servrarna är alla värdar i Tyskland av ett tyskt företag. Servrarna arbetade bara utanför kontorstid på problemet för att inte störa det dagliga arbetet. Lösningarna var hittade efter några dagar och en del justeringssessioner.

Den nästa Expansionsfas av det program som hittat lösningar till magiska hexagoner skulle vara en fullständig parallellisering (CUDA). Precis för detta finns AI-grafikkort. Beräkningen borde med detta sannolikt gå omkring 40 gånger snabbare. Inte helt oväsentligt vid beräkningar som ibland kan ta veckor eller månader. Denna parallellisering av resultatssökandet är både matematiskt och programtekniskt komplicerad och måste därför skjutas upp till en senare tidpunkt.

När löser ditt företag problem med AI?

Författare till de magiska hexagonerna

Klaus Meffert, Idstein, Tyskland

Ytterligare information på Research Gate.

Bildlicens för magiska hexagoner

Alla bilder av magiska hexagoner från den här artikeln får användas så länge bilderna inte ändras (skalning eller komprimering av bilderna är naturligtvis tillåtet).

Förändrade versioner av bilderna får användas med angivande av en länk till dr-dsgvo.de/magic.

För välgörenliga projekt (o.a.) som Wikipedia får följande bilder användas med uppgift om fotografen. För andra projekt finns de ovanstående bilderna tillgängliga under den ovan nämnda licensen.

Om du är osäker om hur du får använda bilden, vänligen fråga: klaus.meffert@dr-dsgvo.de

Författaren skulle också vara glad om ni nämner det magiska nio-vecket av ordning. Tack till Thorsten Müller för att han har gett sin röst åt språkversionen. Notis: Språkversionen har blivit bättre tack vare en optimering.

Viktiga budskap i denna artikel

En AI har löst en 18 år gammal olöst matematisk gåta.

Med hjälp av AI kunde man lösa detta pussel, som tidigare inte kunnat lösas med traditionella metoder som backtracking eller brute force.

Magiska hexagoner är hexagoner där varje rad har samma summa och alla siffror inom bikakorna används.

Varje siffra i bikakan används exakt en gång.

Ordningsnumret (N) anger hur många bikakor som finns på varje ytterkant.

För en magisk hexagon av ordning 3 måste t.ex. 15 rader fyllas med en viss summa.

Den 10 september 2024 hittades en lösning för en magisk hexagon av ordning 9, efter att ingen sådan lösning tidigare hade funnits.

Varje variabel i den magiska hexagonen av ordning 9 påverkar exakt 48 andra bikakor.

Om dessa grundläggande uttalanden