Etikettarkiv: Datavetenskap

2018, Blogg

Språk och tolkning

6 april, 2018 Waffe Lämna en kommentar

Eftersom jag har kodat på ett skolprojekt under hela veckoslutet tänkte jag skriva en artikel om det. Uppgiften var att skriva en programtolk för det simpla MiniPL programmeringsspråket (tekniska specifikationen finns här för de nyfikna).

En vad?

En programtolk/interpretator (eng. interpreter) är ett program som tar in kod av ett specifikt språk och gör/kör det som koden begär. Detta är skillnad till en kompilator, som helt enkelt översätter kod från ett språk till ett annat. Programtolken är ofta uppdelad i 4 huvudsakliga delar: lexikal-, syntax- och semantisk analys, som tillsammans skapar en mängd programinstruktioner, och till sist själva körningen av instruktionerna.

Tolkningen börjar med lexikalanalys där karaktärer grupperas till ”symboler” eller ord (eng. tokens). Vi tar som exempel meningen ”Datorer har en von Neumann-arkitektur.” Karaktärerna kan grupperas till följande symboler: ”Datorer”, ”har”, ”en”, ”von Neumann”, ”-”, ”arkitektur” och till sist ”.”-tecknet. Till symbolerna tillsätts tilläggsdata, som att symbolen ”Datorer” är ett substantiv i plural, symbolen ”har” är ett verb osv.

Syntaxanalysen tar in dessa symboler, och försöker bygga upp satser och meningar av dessa, enligt specifierade grammatikregler. Satserna och meningarna sparas i ett så kallat (abstrakt) syntaxträd. Av exempelmeningen kan man bygga upp följande träd:

I programmeringsspråk är det ytterst viktigt att man kan tolka de givna symbolerna bara på ett visst sätt, dvs. språket får inte vara tvetydigt. Olikt en människa vet inte datorn vad den skall göra då en kod kan betyda två olika saker. Tvetydighet uppkommer oftast i syntaxanalysen, då man inte kan utgöra hurdant syntaxträd som ska byggas upp med hjälp av grammatikreglerna. Grammatiken måste omformas för att fixa problemet.

Efter att syntaxet är granskat så söker den semantiska analysen efter ”meningen” bakom meningarna — vad den givna koden eller texten betyder. En syntaktiskt korrekt mening behöver inte vara semantiskt korrekt. Ett typexempel är ”Färglösa gröna idéer sover häftigt.” Meningen är inte alls vettig (så länge man inte är alltför poetisk av sig), men följer ändå de svenska grammatikreglerna.

Vi tittar igen på exemplet ”Datorer har en von Neumann-arkitektur.” Den semantiska analysen för detta påstående kan bland annat bestå av att svara dessa frågor: Är datorer saker med en ”arkitektur”? Är ”von Neumann-arkitektur” en egenskap som en dator kan ha? Syntaxträdet omvandlas eller påfylls sedan med den information som man har samlat och rent syntaktiska element skärs bort, som punkter och bindestreck.

I semantisk analys av programmeringsspråk granskas det att variabel-/funktiontyperna är överensstämmande och att de variabler/funktioner som används är definierade. Syntaxträdet omvandlas samtidigt till en mängd programinstruktioner (oftast ändå i formen av ett träd) samt en ”symboltabell”, där definitionerna av variabler och funktioner sparas.

Efter allt detta kan instruktionerna köras. Under körningen sparas variabelvärden i symboltabellen, varifrån de kan återhämtas senare. Programtolken borde innehålla en liten mängd basfunktioner (som aritmetik och loopar) som sedan kan användas av programmerare för att bygga upp mer komplexa funktioner. Eller varför inte en ny programtolk?

2018, Blogg

Allt större flugsmällor för allt mindre flugor

29 mars, 2018 robert 2 kommentarer

Varning: Detta inlägg innehåller extremt dålig Java-kod.
Läs på egen risk.

Den som nån gång har läst Reddit-sidan ProgrammerHumor har kanske lagt märke till tendenserna att hitta på alldeles absurda lösningar till mycket simpla problem eller koncept.
Till exempel, för cirka 9 månader sedan var volume sliders ett återkommande skämt och därav skapades många vackra implementationer, bl.a:

Veva upp ljudnivån
Pumpa upp ljudnivån
Låt användaren demonstrera:

Mer nyligen var temat om hur man ”effektivast” kollar om ett givet heltal är jämnt eller udda. Funktioner som åstadkommer detta är lättare att implementera än volume sliders, så motiverad av mina nyfunna kunskaper i Tira (Tietorakenteet ja algoritmit) bestämde jag mig naturligtvis för att testa några i Java. Metoderna nedan är inspirerade av både ProgrammerHumor och egna idéer. Några av dem kan kräva kunskap om Java eller talteori för att förstå, så en TL;DR i meme- format finns längst ner för dem som inte bryr sig om tekniska detaljer.

Metod 1: Divisionsrest

Kolla talets divisionsrest med 2. Om resten är 0, så är talet jämnt, annars udda.

Tråkig normie lösning
Använder inte ens rekursion

public boolean isEven1(int n) {
    return n % 2 == 0;
}

Metod 2: Sista siffran

Vi undersöker talets sista siffra. Om den är 1, 3, 5, 7 eller 9 är talet udda, annars jämnt. Javas indexOf()- metod för listor returnerar -1 ifall det sökta objektet inte hittas i listan. Då gör vi ju så klart en lista av de udda siffrorna och kollar om metoden ger -1 för talets sista siffra.

Behöver inte utföra nån äcklig aritmetik
Konstant tidskomplexitet, fortfarande helt för effektiv

public boolean isEven2(int n) {
    List<Character> lastDigits
        = Arrays.asList('1', '3', '5', '7', '9');
    String number = Integer.toString(n);
    char last = number.charAt(number.length() - 1);
    
    return lastDigits.indexOf(last) == -1;
}

Metod 3: Induktion

Vi använder oss av matematisk induktion. Allmänt gäller att 0 är ett jämnt tal, efter varje jämnt tal följer ett udda, och efter varje udda följer ett jämnt. Vi bygger alltså iterativt upp en array av booleans tills vi nått det n:te elementet, som vi returnerar. Dock för att undvika en OutOfMemoryError måste vi tyvärr fuska lite och emellanåt skriva över gamla värden.

O(n) tidskomplexitet. Från Tira vet vi ju att O(n) är bra.
Induktionen kräver antagandet att 0 är ett jämnt tal. Detta kan verifieras med en av de andra metoderna.

public boolean isEven3(int n) {
    n = n < 0 ? -n : n;        //gör n positivt
    int idx = 0;
    boolean isCurrentEven = true;
 
    boolean[] evenOdd = new boolean[10000];
    while (idx <= n) {
        if (idx == 10000) {
            idx -= 10000;
            n -= 10000;
        }
 
        evenOdd[idx] = isCurrentEven;
        isCurrentEven = !isCurrentEven;
        idx++;
    }
    return evenOdd[idx - 1];
}

Metod 4: Overflow

Alla vet ju att rekursion är bra, så här har vi en härlig blandning av rekursion och error handling.

Vi antar som baskunskap att Javas Integer.MAX_VALUE,
dvs. 2^31 – 1, är ett udda tal. Detta kan igen verifieras med någon annan metod.
Om n = 2^31 – 1 är n udda. Annars kallar vi rekursivt på funktionen med parametern n + 2. Så klart, om n är ett jämnt tal borde den eventuellt hoppa över 2^31 – 1 och orsaka en OverflowException. Men eftersom Java hanterar den här situationen utan att klaga, måste vi använda Math.addExact()- metoden som explicit ger en Exception ifall vi går över 2^31 – 1.

Rekursionen upprepas i värsta fall ca 2^30 gånger, så en StackOverflowError orsakas långt före det. Vid detta skede avbryter vi rekursionen och startar om med en hjälpvariabel som säger hur långt vi kommit förut.

O(2^31 – n) tidskomplexitet. Större tal får snabbare svar.
isEven4(1200000000) svarade true på endast 23 sekunder.

int offset;
 
public boolean increment(int n) {
    if (n == Integer.MAX_VALUE) {
        return false;
    }
    try {
        n = Math.addExact(n, 2);
        offset += 2;
        return increment(n);
    } catch (ArithmeticException e) {
        return true;
    }
}
 
public boolean isEven4(int n) {
    offset = 0;
    while (true) {
        try {
            return increment(n + offset);
        } catch (StackOverflowError e) {
            //inget fel här, moving on...
        }
    }
}

Metod 5: Goldbach

En välkänd hypotes inom talteorin är den s.k. Goldbach Conjecture, som säger att varje jämnt tal större än 2 kan uttryckas som summan av två primtal. Resultatet har inte bevisats för godtyckligt stora jämna tal, men det har verifierats med dator för tillräckligt stora tal för våra ändamål.
Det enda jämna primtalet är 2, dvs det största jämna talet som kan uttryckas som summan av två jämna primtal är 4. Alltså om vårt tal är större än eller lika med 6 söker vi udda primtal vars summa är vårt givna tal. Annars undersöker vi talet med Metod 4.

Hur kan vi då visa att ett givet tal är ett primtal? Vi använder så klart Wilson’s Theorem. Enligt denna sats är n ett primtal om och endast om talets (n-1)! divisionsrest med n är n-1, dvs.
$(n-1)!\ \equiv\ -1 \pmod n$
Till detta ändamål har vi hjälpfunktionerna modFactorial och isPrime.

Antagligen O(n^3) tidskomplexitet. Funktionen modFactorial är O(n) och isEven5 har en dubbel loop.
Körtiden varierar kraftigt mellan udda och jämna tal av ungefär samma storlek:
isEven5(4000) gav true på 2 sekunder och isEven5(4001) gav false på cirka 15 sekunder.
isEven5(10000) gav true efter 30 sekunder. Hur länge tog det för isEven5(10001)?
Använd alltså den här metoden om du redan anar att ditt tal är jämnt!

public int modFactorial(int p, int mod) {
    if (p < 1) {
        return -1;
    }
    long n = 1;
    for (int i = 1; i <= p; i++) {
        n = n*i % mod;
    }
    return (int) n;
}
 
public boolean isPrime(int n) {
    if (n < 2) {
        return false;
    } else {
        return modFactorial(n - 1, n) == n - 1;
    }
}
 
public boolean isEven5(int n) {
    n = n < 0 ? -n : n; //gör n positivt
    if (n < 6) {
        return isEven4(n);
    }
 
    for (int i = 3; i < n; i++) {
        if (!isPrime(i)) {
            continue;
        }
        for (int j = 3; j <= i; j++) {
            if (!isPrime(j)) {
                continue;
            }
            if (i + j == n) {
                return true;
            }
        }
    }
    return false;
}

Här tog kreativiteten och/eller tålamodet slut, för om vi vill kan vi göra godtyckligt ”effektiva” algoritmer, men de är inte nödvändigtvis så intressanta. Men nu har vi ju jobbat under premissen att vår metod ska ge ett svar för just det talet vi stoppar in, och att svaret ska vara rätt. Vad om vi ändrar på spelreglerna lite? En bonusmetod, isEven6, hittas under länken längst ner.

Det här inlägget kunde tolkas både som en uppmuntran och en varning. Avsiktligt dålig kod kan vara väldigt underhållande och lära en tänka på problem på nya sätt (om det här är en bra eller dålig sak är upp till läsarens tolkning). Å andra sidan är dessa metoder det oundvikliga resultatet av att spendera helt för mycket tid på Tira.

TL;DR

https://i.imgur.com/TUYX6Tq.jpg

2014, Blogg

Algoritmisk Sudokulösning

27 november, 2014 Spektraklet Lämna en kommentar

Sudoku, eller “Number Place” som det ursprungligen hette är i dagens läge ett mycket välkänt logiskt pussel:

Givet ett $9 \times 9$ rutfält delvis ifyllt av siffrorna $1-9$ skall du fylla i resten av rutorna med siffrorna $1-9$ så att varje siffra uppkommer endast en gång på varje rad/kolumn/liten ruta, vilka i exemplet omringas i bilden av de lite tjockare linjerna.

Sudoku pussel kan hittas överallt; många tidningar (t.ex. Hbl) publicerar sudokun dagligen, dessutom kryllar bokaffärerna av ”traditionella” och internet av elektroniska sudokun i varierande kvalitet. För de allra ivrigaste lösarna ordnas det årligen VM, med tusentals euron som pris. För den intresserade läsaren finns det i källorna ett par länkar om sudokuns historia, jag måste medge att jag hade trott att sudoku skulle härstamma från Japan, men den moderna varianten av sudoku skapades (högst troligen) av en 74-årig arkitekt från USA.

Det skulle kunna finnas ett antal olika aspekter att diskutera då det kommer till sudokun. Jag kommer att (igen) ta en datavetar-syn på det hela och undersöka till vilken grad datorer kan användas för sudokulösning. Det vill säga: hur svårt är lösning av sudokun för en dator och har människan någon chans klara sig mot dem? Mer specifikt så kommer jag att presentera tre olika algoritmer för sudokulösning samt jämföra dem med varandra.

Sudokulösning med datorhjälp

Näst går vi alltså igenom tre alternativa algoritmer för att lösa sudokun. För läsbarhetens skull kommer jag inte att gå in på detalj då det kommer till implementeringen av de mer komplicerade algoritmerna. Detaljerad förståelse för algoritmerna krävs inte i resten av texten och för de intresserade läsarna finns det en bilaga med (lite) mer detalj.

Algoritm 1: SimpleSolver

Den första algoritmen vi undersöker är också den enklaste. Ifall jag skulle be 100 människor beskriva det simplaste sättet de kommer på för att lösa sudokun, skulle de flesta högst troligen beskriva SimpleSolver. Det handlar nämligen om att pröva alla de (ändligt många) sätten att fylla i de tomma rutorna. Algoritmen fungerar genom att gå igenom alla tomma rutor en åt gången och pröva alla möjliga siffror att sätta i dem. Efter att ha fyllt rutan granskar algoritmen att alla sudokuregler fortfarande uppfylls. Om allt är ok går algoritmen vidare till nästa tomma ruta, annars prövar algoritmen nästa siffra. Om algoritmen tvingas pröva alla siffror utan att kunna hitta en lösning går den tillbaka till föregående tomma ruta och prövar nästa siffra.

Med denna taktik kommer algoritmen i något skede att ha prövat alla möjligheter och därmed också hittat lösningen. SimpleSolver är väldigt simpel, implementation av den brukar vara en av räkneövningarna under grundprogrammeringskurserna i Gumtäkt.

Algoritm 2: DLXSudoku

Till skillnad från första algoritmen är de två andra algoritmerna för sudokulösning ursprungligen inte skapade för sudokun. Istället baserar de sig på idén att omvandla sudoku problemet till något annat (välkänt) problem och sedan lösa det andra problemet istället. Orsaken till att vilja göra såhär är att det ofta är lättare att omvandla problem än att lösa dem. Så om vi kan hitta andra problem som någon annan (lite fiffigare) människa har utvecklat effektiva lösningsalgoritmer för, kan vi dra nytta av dessa algoritmer genom att omvandla vårt problem. Detta är ofta tidseffektivare än att tillbringa en massa tid på att utveckla specialiserade algoritmer för just sudokun. Inom datavetenskap kallar man ofta denna process för en reduktion av ett problem till ett annat. Vår andra algoritm är baserad på en reduktion av sudokun till exact cover problemet och lösning av exact cover med hjälp av Algoritm X implementerad med dancing links: DLXSudoku.

Exact cover är ett ganska abstrakt problem: Givet en matris bestående av endast ettor och nollor är uppgiften att välja ut en delmängd av raderna i matrisen så att det bland de rader vi väljer ut finns exakt en etta i varje kolumn (Obs! Detta är inte den mest allmänna formuleringen av exact cover, men tillräcklig för vårt behov). Ett sudoku problem kan relativt enkelt omvandlas till en exact cover matris :

Varje tom ruta i sudokubrädet motsvaras av 9 rader i matrisen. Vi kallar dessa rader för $Rr\#Cc\#1, \ldots, Rr\#Cc\#9$ där den tomma rutan i fråga finns på rad r kolumn c.
Kolumnerna i matrisen representerar de olika sudoku reglerna:
1. Varje ruta i sudokubrädet skall få exakt 1 siffra
2. Varje kolumn på sudokubrädet skall bli ifylld av exakt en av varje siffra
3. Varje rad i sudokubrädet skall skall bli ifylld av exakt en av varje siffra.
4. Varje liten ruta skall bli ifylld av exakt en av varje siffra.

Alla av dessa regler representeras av kolumnerna så att kolumnen innehåller en etta på alla rader som uppfyller regeln (se exempel nedan).

Efter denna konstruktion kan vi lösa exakt cover problemet och omvandla lösningen till en lösning av sudokut helt enkelt genom att fylla i sudokut enligt de rader Rr#Cc#x som vi valt ut till exact cover lösningen. Notera specifikt att kolumnerna i exact cover matrisen som representerar kravet ”varje ruta på sudokubrädet får exakt ett värde” försäkrar oss om att exact cover lösningen innehåller för varje rad r och kolumn c på sudoku brädet, exakt en rad Rr#Cc#i från exact cover matrisen. För den intresserade läsaren finns det som bilaga till denna text en beskrivning på hur DLX fungerar. Här nöjer vi oss med att nämna att algoritmen har populariserats av Donald Knuth, som även har utvecklat det (inom naturvetenskaper) mycket använda LateX typsättningssystemet.

Exempel: Vi reducerar $4 \times 4$ sudokut ovanför till exact cover. För detta sudoku får vi en exact cover matris med $8$ (antalet tomma rutor) $\times 4$ rader. Bilden nedan visar en del av den:

I bilden representerar första kolumnen kravet: ”Rutan på rad 2 kolumn 1 måste få exakt 1 värde”. Vi ser att kolumnen innehåller en etta på varje rad vars val fyller i rutan och 0 annars. Andra kolumnen representerar kravet ”Någon ruta på rad två måste innehålla en etta”, tredje kolumnen representerar: ”Första kolumnen måste innehålla en fyra” och fjärde ”lilla rutan uppe till höger måste innehålla en etta”, vi märker specifikt att fjärde kolumnen innehåller en etta endast på första raden. Detta betyder att vi måste välja första raden till exact cover lösningen vilket i sin tur betyder att rutan i kolumn 1 rad 2 kommer att innehålla en etta.

Algoritm 3: SATSudoku

Den sista av våra algoritmer reducerar sudoku till det kanske mest kända ”svåra” problemet inom datavetenskap, nämligen satisfiability (SAT). För att kunna beskriva SAT måste vi påminna oss om logik kursen i gymnasiet och specifikt de delarna som handlade om propositionslogik.

Propositionslogik är ett väldigt enkelt logiskt ”språk” där man formar formler genom att binda ihop sanningsvariabler (dvs. variabler som antingen kan vara sanna eller falska) med hjälp av $\land$ (OCH), $\lor$ (ELLER) och $\neg$ (INTE). (Obs. det finns ett antal olika sätt att definiera propositionslogik, vi använder det simplaste möjliga som räcker för vårt behov). Givet en propositionslogisk formel går SAT problemet ut på att hitta ett sätt att ge sanningsvärden (sant eller falskt) åt variablerna som gör att hela formeln blir sann. Sanningsvärdet för en formel definieras utgående från sanningsvärden för de delformler den innehåller:

Om formeln endast består av en enda variabel är dess sanningsvärde lika med sanningsvärdet för variabeln.
Sanningsvärdet för $\lnot A$ är motsatsen till sanningsvärdet för formeln $A$
Formeln $A \land B$ är sann ifall både formlerna $A$ och $B$ är sanna
Formeln $A \lor B$ är sann ifall antingen $A$ eller $B$ (eller båda) är sanna.

Då vi i denna text pratar om att lösa SAT menar vi att hitta ett sätt att ge värden åt variablerna i en given formel så att formeln blir sann. Vi kallar detta sättet för en ”lösning” av SAT. (Notera att detta inte är en allmän definition av SAT problemet, men tillräcklig för oss.)

SAT är ett mycket välkänt problem inom datavetenskap. I dagens läge existerar det effektiva algoritmer för att lösa formler som består av hundratusentals variabler och miljontals delformler. För att kunna använda dessa algoritmer för att lösa sudokun måste vi från ett givet sudokubräde kunna forma en propositionsformel som tillåter oss omvandla en lösning på SAT problemet till en lösning på sudoku problemet.

För varje ruta, säg på rad r kolumn c, introducerar vi 9 sanningsvariabler: $v^{rc}_1, \ldots, v^{rc}_9$ . Meningen med dessa variabler är: ” $v^{rc}_k$ är sann om och endast om rutan på rad r kolumn c får värdet k i sudokulösningen”. Vår formel kommer att bestå av 5 olika delformler, fyra olika beskrivningar på de olika sudokureglerna och en som beskriver de siffror som är färdigt ifyllda:

1) Varje ruta skall få exakt ett värde. För en fixerad ruta på rad r kolumn c beskrivs detta krav av en logisk representation av: $\sum_{j=1}^9 v^{rc}_j = 1$ . Det finns olika sätt att representera detta som propositionslogik. Ett av de simplaste är att använda formeln: $v^{rc}_1 \lor v^{rc}_2 \lor ldots \lor v^{rc}_9$ för att se till att rutan får minst ett värde och $27$ formler av formen: $\lnot (v^{rc}_i \land v^{rc}_j) \quad \forall i < j$ för att se till att den får högst ett värde. I vår implementation använder vi oss av ett lite annorlunda sätt att representera samma sak (kallas för sequential counter). För den intresserade läsaren finns det referenser.

2) Varje rad skall få en av varje värde. För en fixerad rad R beskrivs detta av (del)formeln:

$\bigwedge_{k=1}^9 \left(\sum_{c=1}^9 v^{Rc}_k = 1\right)$

som omvandlas till propositionslogik precis som i punkt 1.

3) Varje kolumn skall få en av varje värde. För en fixerad column C beskrivs detta av formeln:

$\bigwedge_{k=1}^9 \left( \sum_{r=1}^9 v^{rC}_k = 1 \right)$

4) Varje liten ruta skall få en av varje värde. För t.ex. lilla rutan längst upp till vänster beskrivs detta av formeln:

$\bigwedge_{k=1}^9 (v^{11}_k + v^{12}_k + v^{13}_k + v^{21}_k + v^{22}_k+v^{23}_k+v^{31}_k+v^{32}_k+v^{33}_k = 1)$

5) Varje redan färdigt ifylld ruta motsvaras av en formel som tvingar motsvarande variabel att sättas till sant. Så ifall rutan på rad r kolumn c har färdigt ifyllt värdet k lägger vi med delformeln $v^{rc}_k$ till hela formeln.

Vår sista algoritm för sudokulösning bygger upp ett SAT problem såhär och ger den åt en SAT algoritm. Så länge ursprungliga sudokut har en lösning kommer SAT algoritmen att hitta en lösning på SAT problemet. Sedan omvandlas SAT lösningen till en sudoku lösning: rutan på rad r kolum c i sudokubrädet fylls i med det värde k för vilket variabeln $v^{rc}_k$ är sann i SAT lösningen. Delformeln vi satt med i punkt 1 här ovan försäkrar oss om att det finns exakt en sådan för varje tom ruta.

Exempel: Vi fortsätter med samma exempel som tidigare. Fullständiga propositionsformeln som beskriver detta exempel är för lång för att skrivas ner för hand. Men här följer en del illustrerande exempel

Rutan på rad 2 kolumn 1 skall få exakt ett värde: $(v^{21}_1 \lor v^{21}_2 \lor v^{21}_3 \lor v^{21}_4) \land \lnot (v^{21}_1 \land v^{21}_2) \land \lnot (v^{21}_1 \land v^{21}_3) \land \lnot (v^{21}_1 \land v^{21}_4) \land \lnot (v^{21}_2 \land v^{21}_3) \land \lnot (v^{21}_2 \land v^{21}_4) \land \lnot (v^{21}_3 \land v^{21}_4)$ .
Kolumn 1 måste innehålla en etta: $(v^{11}_1 \lor v^{21}_1 \lor v^{31}_1 \lor v^{41}_1) \land \lnot (v^{11}_1 \land v^{21}_1) \land \lnot (v^{11}_1 \land v^{31}_1) \land \lnot (v^{11}_1 \land v^{41}_1) \land \lnot (v^{21}_1 \land v^{31}_1) \land \lnot (v^{21}_1 \land v^{41}_1) \land \lnot (v^{31}_1 \land v^{41}_1)$ .
Rad 1 måste innehålla en två: $(v^{11}_2 \lor v^{12}_2 \lor v^{13}_2 \lor v^{14}_2) \land \lnot (v^{11}_2 \land v^{12}_2) \land \lnot (v^{11}_2 \land v^{13}_2) \land \lnot (v^{11}_2 \land v^{14}_2) \land \lnot (v^{12}_2 \land v^{13}_2) \land \lnot (v^{12}_2 \land v^{14}_2) \land \lnot (v^{13}_2 \land v^{14}_2)$ .
Vissa rutor är färdigt ifyllda: $v^{11}_3 \land v^{12}_4 \land v^{13}_1 \land v^{22}_2 \land v^{33}_2 \land v^{42}_1 \land v^{43}_4 \land v^{44}_3$ .

Bilagan till denna artikel går in på (lite mer) detalj om hur en SAT algoritm oftast fungerar.

Vilken är bäst?

Nu är det dags för den mest intressanta frågan; vilken är bäst? För att kunna testa detta fick jag hjälp av Toffe som implementera SimpleSolvern och Lasse som implementera DLXSudoku. Själv implementerade jag SATSudoku. Tack till både Toffe och Lasse!

Innan vi går till resultaten vill jag påpeka att skillnaderna vi kommer att se i dessa algoritmer inte beror på implementationerna, resultaten kan inte och skall inte användas för att jämföra våra kodningskunskaper.

Jag valde på måfå ut $3$ sudokun av storlek $9 \times 9$ och tog tid på hur länge var och en av våra algoritmer tog på sig för att lösa dem. Resultaten finns nedan:

Det var ju lite tråkigt inte sant? Till och med den simplaste algoritmen löser alla 3 på under 1.5s, de mer avancerade lösarna tar under en tiondels sekund på sig. Detta illustrerar orsaken till varför jag bara hade tre sudokun; faktum är att de allra flesta normala sudokun är så gott som triviala för en dator. Det går att designa problem som vår SimpleSudoku inte skulle kunna lösa, men redan genom att ha SimpleSudoku pröva siffror i slumpmässig ordning istället för storleksordning så klarar även den av så gott som alla $9 \times 9$ sudokun snabbare än vad det skulle ta för människan att skriva ner en färdig lösning. Så det ser inte så hemskt lovande ut för oss människor.

Det verkar alltså klart att om man behöver få många sudokun löst snabbt är det mer tidseffektivt att koda en lösare än att lösa dem själv. Dock kan man efter dessa resultat fråga sig varför man över huvudtaget borde sätta ner tid på att implementera något som helst mer avancerat än SimpleSudoku?

Ifall man bara är intresserad av $9 \times 9$ sudokun är svaret: man borde inte. Men, om vi tillåter större sudokun blir saker och ting intressantare. Forskningsresultat inom sudokulösning (ja, det finns sådana) pratar ofta om ordningen (rank) av ett sudoku. En normal sudoku är av ordning 3 och allmänt så skall en sudoku av ordning $n$ lösas på ett $n^2 \times n^2$ bräde. Så en $4 \times 4$ sudoku är av ordning $2$ och en $16 \times 16$ sudoku är av ordning $4$ . Alla av våra algoritmer kan användas för att lösa sudokun av vilken ordning som helst. Dessutom borde större sudokun vara bättre för att jämföra algoritmer, intuitivt känns det ju ganska klart att ett större sudoku borde vara svårare än ett mindre.

Resultaten finns ovan och nu börjar vi på riktigt märka skillnader i algoritmerna. SimpleSolvern klarade inte av en enda av dessa problem på under en timme (gränsen på lösningstiden). Däremot klarar sig både SATSudoku och DLXSudoku ganska väl, speciellt på ”enkla” sudokun. Av dessa två klarar sig SATSudoku lite bättre än DLX: den klarar av en ordning större ”lätt” problem och en ordning större ”svårt” problem.

Vad lär vi oss av detta? Jo, om du bara vill lösa ett enda normal stort sudoku är det fiffigare att ta papper och penna än börja koda. Skall du lösa 1000 normala sudokun kan du be datorn göra det på det enklaste möjliga sättet. Skall du lösa ett enkelt $15^2 = 225 \times 225$ sudoku, så går det också att fixas, dock med lite mer möda. Men om du vill lösa ett svårt $49 \times 49$ sudoku? Då är det dags att ta fram pennan igen, skriva ett stort ”LÖS SJÄLV” på hela brädet, och ta en öl istället.

Slutligen vill jag lämna er med det största sudokut som våra algoritmer klarade av och det minsta som de inte klarade. Om någon av er får någondera löst kan ni lämna en kommentar så sätter jag med er i resultaten.

Jeremias

BILAGA:

Algorithm X, Conflict Driven Clause Learning and Dancing Links for Sudokusolving.

Källor:

^ C. Colbourn (1984). ”The complexity of completing partial latin squares”. Discrete Applied Mathematics 8: 25–30. doi:10.1016/0166-218X(84)90075-1.
Carsten Sinz: Towards an Optimal CNF Encoding of Boolean Cardinality Constraints. CP 2005: 827-831
http://www.worldpuzzle.org/championships/wsc/
http://plus.maths.org/content/os/issue38/features/aiden/index