![\"rank3Example\"](\"http:\/\/spektrum.fi\/spektraklet\/wp-content\/uploads\/2014\/11\/rank3example1.png\")
<\/a> ![\"rank3ExampleSolved\"](\"http:\/\/spektrum.fi\/spektraklet\/wp-content\/uploads\/2014\/11\/rank3examplesolved1.png\")
<\/a><\/p>\nGivet ett
Sudoku pussel kan hittas \u00f6verallt; m\u00e5nga tidningar (t.ex. Hbl) publicerar sudokun dagligen, dessutom kryllar bokaff\u00e4rerna av \u201dtraditionella\u201d och internet av elektroniska sudokun i varierande kvalitet. F\u00f6r de allra ivrigaste l\u00f6sarna ordnas det \u00e5rligen VM, med tusentals euron som pris. F\u00f6r den intresserade l\u00e4saren finns det i k\u00e4llorna ett par l\u00e4nkar om sudokuns historia, jag m\u00e5ste medge att jag hade trott att sudoku skulle h\u00e4rstamma fr\u00e5n Japan, men den moderna varianten av sudoku skapades (h\u00f6gst troligen) av en 74-\u00e5rig arkitekt fr\u00e5n USA.<\/p>\n
Det skulle kunna finnas ett antal olika aspekter att diskutera d\u00e5 det kommer till sudokun. Jag kommer att (igen) ta en datavetar-syn p\u00e5 det hela och unders\u00f6ka till vilken grad datorer kan anv\u00e4ndas f\u00f6r sudokul\u00f6sning. Det vill s\u00e4ga: hur sv\u00e5rt \u00e4r l\u00f6sning av sudokun f\u00f6r en dator och har m\u00e4nniskan n\u00e5gon chans klara sig mot dem? Mer specifikt s\u00e5 kommer jag att presentera tre olika algoritmer f\u00f6r sudokul\u00f6sning samt j\u00e4mf\u00f6ra dem med varandra.<\/p>\n
Sudokul\u00f6sning med datorhj\u00e4lp<\/strong><\/p>\n N\u00e4st g\u00e5r vi allts\u00e5 igenom tre alternativa algoritmer f\u00f6r att l\u00f6sa sudokun. F\u00f6r l\u00e4sbarhetens skull kommer jag inte att g\u00e5 in p\u00e5 detalj d\u00e5 det kommer till implementeringen av de mer komplicerade algoritmerna. Detaljerad f\u00f6rst\u00e5else f\u00f6r algoritmerna kr\u00e4vs inte i resten av texten och f\u00f6r de intresserade l\u00e4sarna finns det en bilaga med (lite) mer detalj.<\/p>\n Algoritm 1:\u00a0 SimpleSolver<\/p>\n Den f\u00f6rsta algoritmen vi unders\u00f6ker \u00e4r ocks\u00e5 den enklaste. Ifall jag skulle be 100 m\u00e4nniskor beskriva det simplaste s\u00e4ttet de kommer p\u00e5 f\u00f6r att l\u00f6sa sudokun, skulle de flesta h\u00f6gst troligen beskriva SimpleSolver. Det handlar n\u00e4mligen om att pr\u00f6va alla de (\u00e4ndligt m\u00e5nga) s\u00e4tten att fylla i de tomma rutorna. Algoritmen fungerar genom att g\u00e5 igenom alla tomma rutor en \u00e5t g\u00e5ngen och pr\u00f6va alla m\u00f6jliga siffror att s\u00e4tta i dem. Efter att ha fyllt rutan granskar algoritmen att alla sudokuregler fortfarande uppfylls. Om allt \u00e4r ok g\u00e5r algoritmen vidare till n\u00e4sta tomma ruta, annars pr\u00f6var algoritmen n\u00e4sta siffra. Om algoritmen tvingas pr\u00f6va alla siffror utan att kunna hitta en l\u00f6sning g\u00e5r den tillbaka till f\u00f6reg\u00e5ende tomma ruta och pr\u00f6var n\u00e4sta siffra.<\/p>\n Med denna taktik kommer algoritmen i n\u00e5got skede att ha pr\u00f6vat alla m\u00f6jligheter och d\u00e4rmed ocks\u00e5 hittat l\u00f6sningen. SimpleSolver \u00e4r v\u00e4ldigt simpel, implementation av den brukar vara en av r\u00e4kne\u00f6vningarna under grundprogrammeringskurserna i Gumt\u00e4kt.<\/p>\n Algoritm 2: DLXSudoku<\/p>\n Till skillnad fr\u00e5n f\u00f6rsta algoritmen \u00e4r de tv\u00e5 andra algoritmerna f\u00f6r sudokul\u00f6sning ursprungligen inte skapade f\u00f6r sudokun. Ist\u00e4llet baserar de sig p\u00e5 id\u00e9n att omvandla sudoku problemet till n\u00e5got annat (v\u00e4lk\u00e4nt) problem och sedan l\u00f6sa det andra problemet ist\u00e4llet. Orsaken till att vilja g\u00f6ra s\u00e5h\u00e4r \u00e4r att det ofta \u00e4r l\u00e4ttare att omvandla problem \u00e4n att l\u00f6sa dem. S\u00e5 om vi kan hitta andra problem som n\u00e5gon annan (lite fiffigare) m\u00e4nniska har utvecklat effektiva l\u00f6sningsalgoritmer f\u00f6r, kan vi dra nytta av dessa algoritmer genom att omvandla v\u00e5rt problem. Detta \u00e4r ofta tidseffektivare \u00e4n att tillbringa en massa tid p\u00e5 att utveckla specialiserade algoritmer f\u00f6r just sudokun. Inom datavetenskap kallar man ofta denna process f\u00f6r en reduktion av ett problem till ett annat. V\u00e5r andra algoritm \u00e4r baserad p\u00e5 en reduktion av sudokun till exact cover problemet och l\u00f6sning av exact cover med hj\u00e4lp av Algoritm X implementerad med dancing links: DLXSudoku.<\/p>\n Exact cover \u00e4r ett ganska abstrakt problem: Givet en matris best\u00e5ende av endast ettor och nollor \u00e4r uppgiften att v\u00e4lja ut en delm\u00e4ngd av raderna i matrisen s\u00e5 att det bland de rader vi v\u00e4ljer ut finns exakt en etta i varje kolumn (Obs! Detta \u00e4r inte den mest allm\u00e4nna formuleringen av exact cover, men tillr\u00e4cklig f\u00f6r v\u00e5rt behov). Ett sudoku problem kan relativt enkelt omvandlas till en exact cover matris :<\/p>\n Alla av dessa regler representeras av kolumnerna s\u00e5 att kolumnen inneh\u00e5ller en etta p\u00e5 alla rader som uppfyller regeln (se exempel nedan).<\/p>\n Efter denna konstruktion kan vi l\u00f6sa exakt cover problemet och omvandla l\u00f6sningen till en l\u00f6sning av sudokut helt enkelt genom att fylla i sudokut enligt de rader Rr#Cc#x som vi valt ut till exact cover l\u00f6sningen. Notera specifikt att kolumnerna i exact cover matrisen som representerar kravet \u201dvarje ruta p\u00e5 sudokubr\u00e4det f\u00e5r exakt ett v\u00e4rde\u201d f\u00f6rs\u00e4krar oss om att exact cover l\u00f6sningen inneh\u00e5ller f\u00f6r varje rad r och kolumn c p\u00e5 sudoku br\u00e4det, exakt en rad Rr#Cc#i fr\u00e5n exact cover matrisen. F\u00f6r den intresserade l\u00e4saren finns det som bilaga till denna text en beskrivning p\u00e5 hur DLX fungerar. H\u00e4r n\u00f6jer vi oss med att n\u00e4mna att algoritmen har populariserats av Donald Knuth, som \u00e4ven har utvecklat det (inom naturvetenskaper) mycket anv\u00e4nda LateX typs\u00e4ttningssystemet.<\/p>\n Exempel<\/strong>: Vi reducerar Algoritm 3: SATSudoku<\/p>\n Den sista av v\u00e5ra algoritmer reducerar sudoku till det kanske mest k\u00e4nda \u201dsv\u00e5ra\u201d problemet inom datavetenskap, n\u00e4mligen satisfiability (SAT). F\u00f6r att kunna beskriva SAT m\u00e5ste vi p\u00e5minna oss om logik kursen i gymnasiet och specifikt de delarna som handlade om propositionslogik.<\/p>\n Propositionslogik \u00e4r ett v\u00e4ldigt enkelt logiskt \u201dspr\u00e5k\u201d d\u00e4r man formar formler genom att binda ihop sanningsvariabler (dvs. variabler som antingen kan vara sanna eller falska) med hj\u00e4lp av D\u00e5 vi i denna text pratar om att l\u00f6sa SAT menar vi att hitta ett s\u00e4tt att ge v\u00e4rden \u00e5t variablerna i en given formel s\u00e5 att formeln blir sann. Vi kallar detta s\u00e4ttet f\u00f6r en ”l\u00f6sning” av SAT. (Notera att detta inte \u00e4r en allm\u00e4n definition av SAT problemet, men tillr\u00e4cklig f\u00f6r oss.)<\/p>\n SAT \u00e4r ett mycket v\u00e4lk\u00e4nt problem inom datavetenskap. I dagens l\u00e4ge existerar det effektiva algoritmer f\u00f6r att l\u00f6sa formler som best\u00e5r av hundratusentals variabler och miljontals delformler. F\u00f6r att kunna anv\u00e4nda dessa algoritmer f\u00f6r att l\u00f6sa sudokun m\u00e5ste vi fr\u00e5n ett givet sudokubr\u00e4de kunna forma en propositionsformel som till\u00e5ter oss omvandla en l\u00f6sning p\u00e5 SAT problemet till en l\u00f6sning p\u00e5 sudoku problemet.<\/p>\n F\u00f6r varje ruta, s\u00e4g p\u00e5 rad r kolumn c, introducerar vi 9 sanningsvariabler: 1) Varje ruta skall f\u00e5 exakt ett v\u00e4rde. F\u00f6r en fixerad ruta p\u00e5 rad r kolumn c beskrivs detta krav av en logisk representation av: 2) Varje rad skall f\u00e5 en av varje v\u00e4rde. F\u00f6r en fixerad rad R beskrivs detta av (del)formeln:<\/p>\n som omvandlas till propositionslogik precis som i punkt 1.<\/p>\n 3) Varje kolumn skall f\u00e5 en av varje v\u00e4rde. F\u00f6r en fixerad column C beskrivs detta av formeln:<\/p>\n 4) Varje liten ruta skall f\u00e5 en av varje v\u00e4rde. F\u00f6r t.ex. lilla rutan l\u00e4ngst upp till v\u00e4nster beskrivs detta av formeln:<\/p>\n 5) Varje redan f\u00e4rdigt ifylld ruta motsvaras av en formel som tvingar motsvarande variabel att s\u00e4ttas till sant. S\u00e5 ifall rutan p\u00e5 rad r kolumn c har f\u00e4rdigt ifyllt v\u00e4rdet k l\u00e4gger vi med delformeln V\u00e5r sista algoritm f\u00f6r sudokul\u00f6sning bygger upp ett SAT problem s\u00e5h\u00e4r och ger den \u00e5t en SAT algoritm. S\u00e5 l\u00e4nge ursprungliga sudokut har en l\u00f6sning kommer SAT algoritmen att hitta en l\u00f6sning p\u00e5 SAT problemet. Sedan omvandlas\u00a0 SAT l\u00f6sningen till en sudoku l\u00f6sning: rutan p\u00e5 rad r kolum c i sudokubr\u00e4det fylls i med det v\u00e4rde k f\u00f6r vilket variabeln Exempel<\/strong>: Vi forts\u00e4tter med samma exempel som tidigare. Fullst\u00e4ndiga propositionsformeln som beskriver detta exempel \u00e4r f\u00f6r l\u00e5ng f\u00f6r att skrivas ner f\u00f6r hand. Men h\u00e4r f\u00f6ljer en del illustrerande exempel\u00a0\u00a0\u00a0<\/em><\/p>\n Bilagan till denna artikel g\u00e5r in p\u00e5 (lite mer) detalj om hur en SAT algoritm oftast fungerar.<\/p>\n Vilken \u00e4r b\u00e4st?<\/strong><\/p>\n Nu \u00e4r det dags f\u00f6r den mest intressanta fr\u00e5gan; vilken \u00e4r b\u00e4st? F\u00f6r att kunna testa detta fick jag hj\u00e4lp av Toffe som implementera SimpleSolvern och Lasse som implementera DLXSudoku. Sj\u00e4lv implementerade jag SATSudoku. Tack till b\u00e5de Toffe och Lasse!<\/p>\n Innan vi g\u00e5r till resultaten vill jag p\u00e5peka att skillnaderna vi kommer att se i dessa algoritmer inte beror p\u00e5 implementationerna, resultaten kan inte och skall inte anv\u00e4ndas f\u00f6r att j\u00e4mf\u00f6ra v\u00e5ra kodningskunskaper.<\/p>\n Jag valde p\u00e5 m\u00e5f\u00e5 ut Det var ju lite tr\u00e5kigt inte sant? Till och med den simplaste algoritmen l\u00f6ser alla 3 p\u00e5 under 1.5s, de mer avancerade l\u00f6sarna tar under en tiondels sekund p\u00e5 sig. Detta illustrerar orsaken till varf\u00f6r jag bara hade tre sudokun; faktum \u00e4r att de allra flesta normala sudokun \u00e4r s\u00e5 gott som triviala f\u00f6r en dator. Det g\u00e5r att designa problem som v\u00e5r SimpleSudoku inte skulle kunna l\u00f6sa, men redan genom att ha SimpleSudoku\u00a0 pr\u00f6va siffror i slumpm\u00e4ssig ordning ist\u00e4llet f\u00f6r storleksordning s\u00e5 klarar \u00e4ven den av s\u00e5 gott som alla Det verkar allts\u00e5 klart att om man beh\u00f6ver f\u00e5 m\u00e5nga sudokun l\u00f6st snabbt \u00e4r det mer tidseffektivt att koda en l\u00f6sare \u00e4n att l\u00f6sa dem sj\u00e4lv. Dock kan man efter dessa resultat\u00a0 fr\u00e5ga sig varf\u00f6r man \u00f6ver huvudtaget borde s\u00e4tta ner tid p\u00e5 att implementera n\u00e5got som helst mer avancerat \u00e4n SimpleSudoku?<\/p>\n Ifall man bara \u00e4r intresserad av Resultaten finns ovan och nu b\u00f6rjar vi p\u00e5 riktigt m\u00e4rka skillnader i algoritmerna. SimpleSolvern klarade inte av en enda av dessa problem p\u00e5 under en timme (gr\u00e4nsen p\u00e5 l\u00f6sningstiden). D\u00e4remot klarar sig b\u00e5de SATSudoku och DLXSudoku ganska v\u00e4l, speciellt p\u00e5 ”enkla” sudokun. Av dessa tv\u00e5 klarar sig SATSudoku lite b\u00e4ttre \u00e4n DLX: den klarar av en ordning st\u00f6rre ”l\u00e4tt” problem och en ordning st\u00f6rre ”sv\u00e5rt” problem.<\/p>\n Vad l\u00e4r vi oss av detta? Jo, om du bara vill l\u00f6sa ett enda normal stort sudoku \u00e4r det fiffigare att ta papper och penna \u00e4n b\u00f6rja koda. Skall du l\u00f6sa 1000 normala sudokun kan du be datorn g\u00f6ra det p\u00e5 det enklaste m\u00f6jliga s\u00e4ttet. Skall du l\u00f6sa ett enkelt Slutligen vill jag l\u00e4mna er med det st\u00f6rsta<\/a> sudokut som v\u00e5ra algoritmer klarade av och det minsta<\/a> som de inte klarade. Om n\u00e5gon av er f\u00e5r n\u00e5gondera l\u00f6st kan ni l\u00e4mna en kommentar s\u00e5 s\u00e4tter jag med er i resultaten.<\/p>\n Jeremias<\/p>\n BILAGA:<\/p>\n Algorithm X, Conflict Driven Clause Learning and Dancing Links for Sudokusolving. <\/a><\/p>\n K\u00e4llor:<\/p>\n Sudoku, eller \u201cNumber Place\u201d som det ursprungligen hette \u00e4r i dagens l\u00e4ge ett mycket v\u00e4lk\u00e4nt logiskt pussel: Givet ett rutf\u00e4lt delvis ifyllt av siffrorna skall du fylla i resten av rutorna med siffrorna s\u00e5 att varje siffra uppkommer endast en g\u00e5ng p\u00e5 varje rad\/kolumn\/liten ruta, vilka i exemplet omringas i bilden av de lite tjockare … Forts\u00e4tt l\u00e4sa Algoritmisk Sudokul\u00f6sning<\/span> \n
\n
<\/a><\/p>\n<\/a> I bilden representerar f\u00f6rsta kolumnen kravet: ”Rutan p\u00e5 rad 2 kolumn 1 m\u00e5ste f\u00e5 exakt 1 v\u00e4rde”. Vi ser att kolumnen inneh\u00e5ller en etta p\u00e5 varje rad vars val fyller i rutan och 0 annars. Andra kolumnen representerar kravet ”N\u00e5gon ruta p\u00e5 rad tv\u00e5 m\u00e5ste inneh\u00e5lla en etta”, tredje kolumnen representerar: ”F\u00f6rsta kolumnen m\u00e5ste inneh\u00e5lla en fyra” och fj\u00e4rde ”lilla rutan uppe till h\u00f6ger m\u00e5ste inneh\u00e5lla en etta”, vi m\u00e4rker specifikt att fj\u00e4rde kolumnen inneh\u00e5ller en etta endast p\u00e5 f\u00f6rsta raden. Detta betyder att vi m\u00e5ste v\u00e4lja f\u00f6rsta raden till exact cover l\u00f6sningen vilket i sin tur betyder att rutan i kolumn 1 rad 2 kommer att inneh\u00e5lla en etta.<\/em><\/p>\n\n
<\/a><\/p>\n\n
<\/a><\/p>\n<\/a><\/p>\n\n