211service.com
Wiskunde van Sudoku leidt tot 'Richter-schaal' van puzzelhardheid
De wereldwijde fascinatie voor Sudoku heeft geleid tot een plotselinge interesse in de wiskundige eigenschappen van de puzzel. In de afgelopen maanden hebben we op deze blog gekeken hoe wiskundigen het minimale Sudoku-probleem hebben opgelost en zelfs hoe ze de wiskunde van Sudoku hebben gebruikt om afbeeldingen te coderen.
Vandaag krijgen we een andere kijk op Sudoku dankzij het werk van Maria Ercsey-Ravasz aan de Babes-Bolyai University in Roemenië en Zoltan Toroczkai aan de University of Notre Dame in Indiana.
Deze jongens hebben een manier ontwikkeld om de moeilijkheidsgraad van een bepaalde Sudoku-puzzel te meten en zeggen dat hun schaal van Richter voor de moeilijkheidsgraad van de puzzel kan worden toegepast op een groot aantal andere spellen.
Eerst wat achtergrondinformatie over Sudoku. Dit is een cijferpuzzel bestaande uit een raster van 9 x 9 waarin sommige cellen aanwijzingen bevatten in de vorm van cijfers van 1 tot 9. Het is de taak van de oplosser om de resterende cellen in te vullen zodat elke rij, kolom en 3×3 vak in het raster bevat alle negen cijfers. Bovendien kan elk raster maar één oplossing hebben.
Sudoku-puzzels worden over het algemeen geclassificeerd als gemakkelijk, gemiddeld of moeilijk, waarbij puzzels over het algemeen meer startaanwijzingen hebben, maar niet altijd gemakkelijker op te lossen. Maar het wiskundig kwantificeren van de moeilijkheid is moeilijk.
Nu zeggen Ercsey-Ravasz en Toroczkai dat ze een manier hebben gevonden om dit te doen met behulp van algoritmische complexiteitstheorie. Ze wijzen erop dat het gemakkelijk is om een algoritme te ontwerpen dat Sudoku oplost door elke combinatie van cijfers te testen om degene te vinden die werkt. Dat soort brute force-oplossing garandeert je een antwoord, maar niet erg snel.
In plaats daarvan zoeken algoritmeontwerpers naar slimmere manieren om oplossingen te vinden die gebruikmaken van de structuur en beperkingen van het probleem. Deze algoritmen en hun gedrag zijn complexer maar krijgen sneller antwoord.
Het centrale punt van het argument van Ercsey-Ravasz en Toroczkai is dat, omdat een algoritme de structuur van het probleem weerspiegelt, zijn gedrag – de kronkels die het door de toestandsruimte volgt – een goede maatstaf is voor de moeilijkheidsgraad van het probleem.
Om dit aan te tonen pakken ze het voorbeeld van Sudoku aan. In plaats van de brute force-oplossing ontwerpen ze een veel eleganter algoritme dat gebruikmaakt van de verschillende beperkingen van de puzzel, zoals het feit dat elke rijkolom en elk subraster alle cijfers van 1 tot 9 moet bevatten.
Op deze manier transformeren ze het probleem in een type dat bij complexiteitstheoretici bekend staat als een k-sat-probleem.
Ze beginnen met het invoegen van een willekeurige reeks getallen in het raster en volgen het traject van het algoritme door de toestandsruimte terwijl het naar een oplossing zoekt. Voor een eenvoudig probleem is dat traject eenvoudig, zoals weergegeven in de bovenste van de twee figuren bovenaan dit bericht.
Maar dat verandert allemaal voor een moeilijk probleem. Ercsey-Ravasz en Toroczkai testen hun algoritme zo hard tegen een Sudoku-raster dat het zijn eigen naam heeft: de platinablond. Het resultaat wordt weergegeven in de onderste helft van de afbeelding. Het is aanzienlijk complexer en duurt tien keer zo lang om op te lossen.
Ercsey-Ravasz en Toroczkai zeggen dat voor moeilijke problemen het traject chaotisch wordt voordat er een oplossing wordt gevonden. In feite is de tijd die nodig is om aan deze chaotische toestand te ontsnappen een eenvoudige moeilijkheidsgraad.
Op basis daarvan creëren ze een 'Richter-schaal' van puzzelmoeilijkheid op basis van het ontsnappingspercentage. De schaal gaat van 1 tot 4, waarbij één de gemakkelijkste is en 4 ultrahard.
Ze zeggen dat deze schaal verrassend goed correleert met de subjectieve menselijke beoordelingen, waarbij 1 overeenkomt met gemakkelijke puzzels, 2 tot middelgrote puzzels en 3 met moeilijke puzzels. De platinablonde heeft een moeilijkheidsgraad van 3,5789.
Een interessant gevolg is dat er geen Sudoku-puzzel bekend is met een moeilijkheidsgraad van 4. En het aantal aanwijzingen is ook niet altijd een goede moeilijkheidsgraad. Ercsey-Ravasz en Toroczkai zeggen dat ze veel puzzels hebben getest, waaronder een aantal met de 17 aanwijzingen, het minimum aantal, en een paar met 18 aanwijzingen.
Deze waren allemaal makkelijker op te lossen dan de platinablonde, die 21 aanwijzingen heeft. Dat komt omdat de hardheid van de puzzel niet alleen afhangt van het aantal aanwijzingen, maar ook van hun positie.
Een interessante vraag is nu of er echt een ultraharde puzzel met een moeilijkheidsgraad van 4 bestaat en hoe deze te vinden is.
Belangrijker dan dit is dat de methode van Ercsey-Ravasz en Toroczkai generaliseert naar alle k-sat-problemen van dezelfde klasse als Sudoku. Dus de moeilijkheidsgraad van deze problemen kan allemaal worden geclassificeerd door vergelijkbare schalen van het Richter-type.
Dat laat slechts één vraag over: hoe moet de moeilijkheidsgraad van de puzzel worden genoemd? Het voor de hand liggende antwoord is de Ercsey-Ravasz en Toroczkai-schaal of ERT-schaal. Eventuele andere suggesties in de opmerkingen hieronder.
Referentie: arxiv.org/abs/1208.0370 : De chaos binnen Sudoku