Matematik i Sudoku leder till 'Richter Scale' av pusselhårdhet

Den globala fascinationen för Sudoku har lett till ett plötsligt intresse för pusslets matematiska egenskaper. Under de senaste månaderna på den här bloggen har vi tittat på hur matematiker har löst det minimala Sudoku-problemet och till och med hur de har använt Sudoku-matematiken för att kryptera bilder.

Idag får vi en annan syn på Sudoku tack vare Maria Ercsey-Ravasz arbete vid Babes-Bolyai University i Rumänien och Zoltan Toroczkai vid University of Notre Dame i Indiana.

De här killarna har utvecklat ett sätt att mäta svårigheten för ett visst Sudoku-pussel och säger att deras Richter-skala av pussel svårighetsgrad kan tillämpas på ett brett utbud av andra spel.

Först lite bakgrund om Sudoku. Detta är ett nummerpussel som består av ett 9 x 9 rutnät där vissa celler innehåller ledtrådar i form av siffror från 1 till 9. Lösarens jobb är att fylla i de återstående cellerna så att varje rad, kolumn och 3×3 ruta rutnätet innehåller alla nio siffrorna. Dessutom kan varje rutnät bara ha en lösning.

Sudoku-pussel klassificeras i allmänhet som lätta, medelhöga eller svåra, med pussel som har fler startledtrådar i allmänhet men inte alltid lättare att lösa. Men att kvantifiera svårigheten matematiskt är svårt.

Nu säger Ercsey-Ravasz och Toroczkai att de har utarbetat ett sätt att göra det med hjälp av algoritmisk komplexitetsteori. De påpekar att det är lätt att designa en algoritm som löser Sudoku genom att testa varje kombination av siffror för att hitta den som fungerar. Den typen av brute force-lösning garanterar dig ett svar men inte särskilt snabbt.

Istället letar algoritmdesigners efter smartare sätt att hitta lösningar som utnyttjar problemets struktur och begränsningar. Dessa algoritmer och deras beteende är mer komplexa men de får ett svar snabbare.

Den centrala poängen med Ercsey-Ravasz och Toroczkais argument är att eftersom en algoritm speglar problemets struktur, är dess beteende – de vändningar som den följer genom tillståndsrummet – ett bra mått på problemets svårighetsgrad.

För att visa detta tar de sig an exemplet med Sudoku. Istället för brute force-lösningen designar de en mycket mer elegant algoritm som utnyttjar de olika begränsningarna i pusslet, som det faktum att varje radkolumn och underrutnät måste innehålla alla siffror från 1 till 9.

På så sätt förvandlar de problemet till en typ som är känd för komplexitetsteoretiker som ett k-sat-problem.

De börjar med att infoga en slumpmässig uppsättning siffror i rutnätet och följer algoritmens bana genom tillståndsrymden när den söker efter en lösning. För ett enkelt problem är den banan enkel, som visas i den övre av de två figurerna överst i detta inlägg.

Men allt det förändras för ett svårt problem. Ercsey-Ravasz och Toroczkai testar sin algoritm mot ett Sudoku-rutnät så hårt att det har sitt eget namn: den platinablonda. Resultatet visas i den nedre halvan av figuren. Det är betydligt mer komplext och tar tio gånger så lång tid att lösa.

Ercsey-Ravasz och Toroczkai säger att för svåra problem blir banan kaotisk innan man bestämmer sig för en lösning. Faktum är att tiden det tar att fly detta kaotiska tillstånd är ett enkelt mått på svårighet.

På den grunden skapar de en 'Richterskala' av pussel svårighetsgrad baserat på flykthastigheten. Skalan går från 1 till 4, där en är den enklaste och 4 är extremt hård.

De säger att denna skala korrelerar förvånansvärt bra med de subjektiva mänskliga betygen med 1 som motsvarar enkla pussel, 2 till medelstora pussel och 3 till svåra pussel. Den platinablonda har en svårighetsgrad på 3,5789.

En intressant följd är att inget Sudoku-pussel är känt med en svårighetsgrad på 4. Och antalet ledtrådar är inte heller alltid ett bra mått på svårighetsgraden. Ercsey-Ravasz och Toroczkai säger att de testade många pussel inklusive flera med de 17 ledtrådarna, det minsta antalet och några med 18 ledtrådar.

Dessa var alla lättare att lösa än den platinablonda, som har 21 ledtrådar. Det beror på att hårdheten i pusslet inte bara beror på antalet ledtrådar utan också på deras position.

En intressant fråga nu är om ett ultrahårt pussel med svårighetsgraden 4 faktiskt existerar och hur det kan hittas.

Mer betydelsefullt än detta är att Ercsey-Ravasz och Toroczkais metod generaliserar till alla k-sat-problem av samma klass som Sudoku. Så svårigheten med dessa problem kan alla klassificeras med liknande Richter-skalor.

Det lämnar bara en fråga - vad ska svårighetsgraden för pussel kallas? Det uppenbara svaret är Ercsey-Ravasz och Toroczkai skalan eller ERT skalan. Andra förslag i kommentarsfältet nedan.

Ref: arxiv.org/abs/1208.0370 : Kaoset inom Sudoku

Dölj