Sudokuns gåta löst

2009-03-17 09:44  
Rapporten om sudokualgoritmen. (Klicka för större bild)

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.

”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.

Jan Melin

Mer om: Sudoku

Kommentarer

Välkommen att säga din mening på Ny Teknik.

Principen för våra regler är enkel: visa respekt för de personer vi skriver om och andra läsare som kommenterar artiklarna. Alla kommentarer modereras efter publiceringen av Ny Teknik eller av oss anlitad personal.

  Kommentarer

Debatt

Läs mer