Sudokuns gåta löst
Av: Jan Melin
Publicerad
17 mars 2009 10:44
19 kommentarer
Senaste av N 24 mars 2009 16:31
En dataprofessor har löst Sudokuns gåta. Han har utvecklat en algoritm som ska kunna lösa alla Sudokupussel oavsett hur svåra eller stora de är.
Rapporten om sudokualgoritmen. (Klicka för större bild)
Läs mer
Mer att läsa på Ny Teknik.se
Länkar
”Sudoku är ett enkelt pussel att lösa”.
Det skriver den amerikanska dataprofessorn J.F. Crook i sin skrift ”A pencil-and-Paper Algorithm for Solving Sudoku Puzzles”.
”Anledningen till att det är trivialt att lösa pusslet är att det finns en algoritm för lösningarna”, skriver Crook i inledningen till sin rapport.
Algoritmen är ingen matematisk formel utan en trädbaserad sökalgoritm som bygger på att leta sig tillbaka i en trädstruktur tills man hittar lösningen.
- Det som Crook har gjort är att kodifiera vad människor gör omedvetet när de löser pusslet, säger Ram Murty som är matteprofessor vid Queen´s University i Ontario i Kanada till The Herald.
- Det är en viktig matematisk insats han gjort, säger Ram Murty.
Enligt J.F. Crook visar hans studie det första matematiska säkra sättet att lösa Sudoku, skriver USA Today.
Crook hävdar att hans metod kan lösa alla Sudoku enbart med hjälp av papper och penna.
Även de pussel som har fler eller färre rutor än de vanligaste med 9 x 9 rutor ska kunna lösas med den nya algoritmen.
”Metoden passar särskilt väl för de pussel som klassas som diaboliska”, skriver J.F. Crook.
Men algoritmen leder ändå till att det ibland finns två möjliga siffror att placera i en ruta. Då får man chansa och testa en av siffrorna i taget för att se vilken som leder till lösningen.
Bloggar som länkar hit
Nyheter/Teknikrevyn
- Med Epicors affärssystem kan du uppnå en låg TCO - på riktigt.En färsk rapport från Aberdeen Group visar att Epicors kunder överträffar genomsnittet både när det gäller TCO och ROI.
- Ny kombikylare MMC från KTR.En kombinerad kylare för olja, vatten och luft i samma enhet. Kombikylaren har sitt användningsområde särskilt i applikationer för mobil hydraulik.
- Modulärt DC system.konvektionsskylt N+1 system för 24V up till 125Vd.c. utspänning. 250W - 3kW i ett 19" subrack från Polyamp.
- Upplev fördelarna med digitala prototyper.Autodesk ®Inventor® hjälper dig att ta steget till digitala prototyper.
- Missa inte årets seminarium! För Dig som vill veta mer om Industriell Datakommunikation, välkommen att anmäla dig till vårt kostnadsfria halvdagsseminarium.
- Ny prisvärd värmekamera, 19.950 sek.Kimo instrument lanserar Flir i5. Möjlighet att kostnadsfritt låna för utvärdering.
- AS-i gör säkerhet enkelt.Med AS-i bygger man flexibla skyddssystem som är enkla att modifiera och minimerar kabeldragningen.
- Internationella patent.Vi har ett stort globalt nätverk och kan de internationella patentreglerna.
- Gratis handbok i termografi !Boken tar upp det viktigaste vid värmefotografering. Teori - praktisk användning - tips m.m. >>
- Mitec Instrument.Vi levererar kompletta lösningar inom dataloggning och fjärrmätning.
- Annonsera »
- Se alla annonser »
- Starta elinstallationsfirma.Som ytterst ansvarig behöver du allmän behörighet. Distans/lärarledd
- Kundorientera på riktigt !Certifierad process- & verksamhetsutvecklare. Verksamhetsutveckling styrd av kundernas behov. Ny utbildning!
- Vi ses väl på underhållsmässan?Kom och träffa Idhammar AB i monter B01:23 på Svenska Mässan i Göteborg den 9-11 mars!
- Lär solenergiteknik!Ettårigt magisterprogram i solel, solvärme/pellets m.m. erbjuds av Högskolan Dalarna.
- BiTA – utbildningar inom ITSM, ITIL, MOF och ISO 20000.BiTA erbjuder Sveriges bredaste kursutbud inom IT Service Management, ITIL, MOF och ISO/IEC 20000.
- NYTT OM BIOGASENS KLIMATNYTTA.Biogas från avfall ger 95% lägre utsläpp av växthusgas jämfört med bensin, visar forskning från LTH.
- ADVETA TeknikutbildningarEl, elektronik, behörighet, BB2,BB1, AB, automation mm, Stockholm, Göteborg, Malmö Distans/lärarledd
- Lär dig CAD!Anmäl dig till vårens CAD-kurser nu! Välj bland AutoCAD, Inventor, 3ds MAX, SolidWorks m fl.
- Tekniska högskolan vid Linköpings universitet !Ny utbildning! Civilingenjör i medicinsk teknik.
- Skog och träingenjörer får bra jobb !Utbildningen är unik i Sverige just nu med distansmöjligheter och bredden i utbildningen från skog till färdig produkt.
- Utveckla nya produkter !Mekatronik suddar ut gränsen mellan maskin data och elektronik och skapar helt nya produkter.
- Projektledaren i den agila processen. Seminarieserie i 5 delar - Start 29 mars.Behövs förarbete i agila projekt? Kommunicera lättrörliga krav. Kvalitet genom Lean - en projektledares perspektiv, Projektet är slut. Dags att hämta hem effekten, Agila projekt behöver också projektledas - fast på ett annat sätt.
- Lean Produktutveckling 7,5 hpNya kursstarter i vår på Chalmers Industrihögskola. Klicka här för mer information.
- Annonsera »
Kommentarer
Senaste inlagd av N 24 mars 2009 16:31 Sortera: Senaste överst
Farsan
Min far "kodade" ihop en enkel soduko-lösare i excel :)
Svar till Mike
I min släkt anlitar vi specialister som löser såväl sudoku som korsord åt oss. Så vi hinner med att göra viktigare saker.
SvaraSvar till von Oben
Skulle också behöva hjälp med mina sudokon finns det något konsultbolag man kan anlita ?
SvaraSvar till Mike
Så vadå, det gjorde jag med.
SvaraSvar till von Oben
I min familj så gör vi de viktigare sakerna först, tjänar tillräckligt med pengar för att pensionera oss och sen sätter vi oss under varsin palm på en söderhavsö och löser sudoku hela dagarna.
Svarasudokuhints.com
och andra ställen har ju funktioner som löser sudokus. Vari består det nya med den amerikanske professorns insatser?
Svar till Magnus
Jag funderade på samma sak. Jag har en polare som för 5 år sedan gjorde en sudoku-lösare i Python där man kunde ta ett foto av ett soduko, och så fyllde den i de tomma rutorna åt en i en ruta på skärmen.
SvaraMen skillnaden kanske är att:
1) Det är en matematisk beskrivning, hur det nu kan vara det när de samtidigt skriver "det är ingen formel". Men det kanske är en diskret och alltid gällande beskrivning.
2) Den löser alla storlekar. De på nätet kanske bara klarar av 9x9.
trivialt
Artikeln lyckades inte få fram vad som eventuellt var unikt med det där. Eftersom det står att hans algoritm inte funkar alltid utan att man måste "chansa" ibland, så blir det ÄNDÅ en trädsökning i det allmänna fallet, med rejält med logik för att beskära meningslösa grenar.
Skulle tro att tusentals hobbyister har gjort liknande grejor - jag har en kollega som ägnat sig åt just det. Själv har jag försökt lösa Eternity II istället. Lite mer utmaning, kan man säga.
Svar till jeppen
Tufft, jag hade aldrig hört talas om Eternity II. Måste kollas upp!
SvaraSvar till AzP
Varning - det pusslet är troligen inte rimligt att lösa med dagens datorteknik. :-)
SvaraSvar till jeppen
Ett Soduku går alltid att lösa utan datakraft på ett eller annat sätt.
SvaraVarför ödsla el på det då det är en utmaning om än svårt. Jag håller med skrivaren om pytonscriptet vore en baggis att sätta ihop det på max 2 dagar, Verifierat testat och klart.
tentatal
Om jag minns rätt så var det ett gammalt tentatal på KTH :-)
Svar till student
Jo, jag har gjort en sådan tenta på kth, så det stämmer.
SvaraPappersalgoritm
Det är väl för sent för tryck nu, men det hade kanske varit bra att förtydliga i artikeln att detta handlar om en generell metod att lösa sudokus, oavsett svårighetsgrad eller utformning, på just papper. Vilket Crooks rubrik faktiskt berättar.
Som många redan påpekat är det ganska vanligt att lösa dem med datakraft.
Svar till Leuc
Vilken datakraft syftar du på? Tredje statsmakten skapar en massa data och har ibland kraft att störta exempelvis politiker men de är nog inte bättre på sudoku än vilken genomsnittlig människa som helst.
SvaraSjälv skulle jag använda en dator om jag absolut måste lösa ett sudoku!
Helt otroligt..
.. att detta är publicerat i en matematisk tidskrift!
tänker bara på
vad en dam sa i en intervju. Man lär sig inget av sudoku på samma sätt som av ett klassiskt korsord
Svar till KG
Svar till KG, Håller inte riktigt med då jag anser att korsord och siffror sitter på olika utbildningsnivåer.
SvaraJag tittar inte på TV som är ett mäste i korsord, Däremot så kan jag programera nästan vad som helst i dom programmen jag jobbat med.
Svar till KG
Svar till KG,
SvaraLite rättelse du har nog rätt med ditt påstående om damen.
//Roland.