Ett pris på 1 000 000 $ (773 100 Kr) kan bli ditt om du kan lösa detta till synes ”enkla” schackpussel.
De Clay Mathematics Institute (CMI) i Amerika erbjuder pengapriset till alla som kan komma på ett datorprogram för att lösa ett problem som kallas Queens pussel, uppfanns först 1850, vilket är en form av vad som kallas en P vs NP problem.
Pusslet verkar ganska enkelt; placera åtta damer på brädet på ett sätt så att inga två damer kan attackera varandra. Tvisten är dock att forskarna vill att algoritmen ska fungera på ett schackbräde på 1 000 gånger 1 000 kvadrat. När antalet rutor ökar, ökar också antalet damer du behöver placera.
Enligt nuvarande uppskattningar kan det ta tusentals år att placera 1 000 drottningar på ett bräde på 1 000 gånger 1 000 kvadrat – på grund av det stora antalet möjligheter att överväga.
Varje algoritm som kan lösa pusslet snabbt skulle också kunna knäcka de tuffaste säkerhetsåtgärderna online, har forskarna sagt, eftersom det skulle vara otroligt kraftfullt.
Det är ett exempel på ett Millennium Prize Problem, som det finns sju av totalt. Dessa pussel tillkännagavs vid ett möte år 2000 och sägs representera de svåraste problemen som matematiken står inför. CMI sa att detta var för att visa människor att det fortfarande fanns många obesvarade frågor i matematik.
CMI:s styrelse utsåg en prisfond på 7 miljoner USD för lösningarna på problemen, med 1 miljon USD till lösningen av varje problem. Den första av dessa löstes 2003 av Grigori Perelman, en rysk matematiker, men han tackade nej till priset.
University of St Andrews har nu lagt fram en utmaning för vem som helst att lösa detta pussel med hjälp av en dator.
University of St Andrews professor Ian Gent kom på idén efter att han blivit utmanad av en Facebookvän att själv lösa schackpusslet. Han och hans kollegor Dr Peter Nightingale och Dr Christopher Jefferson försökte skriva ett datorprogram själva.
Deras lösningar använder ”backtracking” – en algoritm som används i programmering där alla möjliga alternativ övervägs och sedan ”backas” från tills den korrekta lösningen hittas – och deras idéer beskrivs i en papper, publicerad i Journal of Artificial Intelligence Research.
Men så fort schackbrädet blev tillräckligt stort – 1 000 gånger 1 000 rutor – kunde algoritmen inte klara det. Dessa problem är så svåra för datorprogram eftersom det finns för många alternativ att överväga, och det kan ta många år.
”Om du kunde skriva ett datorprogram som kunde lösa problemet riktigt snabbt, skulle du kunna anpassa det för att lösa många av de viktigaste problemen som påverkar oss alla dagligen”, sa professor Gent. ”Detta inkluderar triviala utmaningar som att träna den största gruppen av dina Facebook-vänner som inte känner varandra, eller mycket viktiga som att knäcka koderna som håller alla våra onlinetransaktioner säkra.”
”I praktiken har ingen någonsin varit i närheten av att skriva ett program som kan lösa problemet snabbt”, säger Dr Nightingale. ”Så vad vår forskning har visat är att – för alla praktiska ändamål – det inte kan göras.”
