Het oplossen van een Sudoku is dankzij brute kracht een eitje voor de computer. Dat wordt anders als we de computer menselijke logica willen leren. In deze aflevering het eerste resultaat van vele uren programmeren.
Henk van de Kamer
In de vorige aflevering wilde ik via Python een serie Sudoku’s maken waarvoor een bijzonder patroon nodig is voor het oplossen. In het verleden heb ik Python af en toe gebruikt en met name het strakke inspringen en de “zinsbouw” die mij aan Pascal doet denken, spreken mij aan. Als het project slaagt, is Python ook handig voor een ander idee waar ik al een paar jaar mee rondloop.
Documenteren
Als eerste heb ik een van de gevonden voorbeelden om Sudoku’s te maken, verbouwd tot een versie die ik begrijp. Wie programmeren op school leert, hoort de docent altijd hameren op documenteren van de code. Persoonlijk gebruik ik een veel beter alternatief. Namelijk in de code uitvoer opnemen die een rapport maakt waarmee duidelijk is hoe het programma verloopt. Een programma maken om een Sudoku op te lossen, is niet gemakkelijk en via het rapport kon ik regelmatig bugs oplossen door het punt te vinden waar het mis ging. Ofwel documenteren van code waarin onze invoer wordt gebruikt.
Een geïnterpreteerde taal is altijd trager dan een gecompileerde versie. Echter, ik had niet verwacht dat het genereren van een Sudoku gemiddeld 1,75 seconde kost. Vergelijk dat maar eens met de 40 milliseconde die het oplossen van diezelfde Sudoku met brute kracht kost. Of de circa 135 milliseconde die ‘menselijke’ oplosmethodes gebruikt. Na het bestuderen van de uitvoer weet ik hoe het genereren slimmer kan, maar dát programmeren ben ik nog niet aan toegekomen.
Boekhouding
De afgelopen maand heb ik zeker honderd uur gewerkt aan een programma om Sudoku’s op te lossen met logica in plaats van brute kracht. Verder nog eens veertig uur met het naspelen van Sudoku’s om uit te vogelen wat de volgende stap zou kunnen zijn, of het oplossen van de vele bugs. Want met name díe programmeren ben ik erg goed in. Dankzij de gemaakte set van twintigduizend Sudoku’s via een oplossing, kon ik die laatste gebruiken om te controleren of een via de logica opgeloste Sudoku inderdaad correct is.
In een eerste versie programmeerde ik het scannen van cellen waar overduidelijk maar één cijfer ingevuld kan worden. Dat kan op meerdere manieren en ik koos voor de boekhoudmethode. Als je de website met de stap-voor-stap Sudoku-oplosser die ik in de vorige aflevering noemde, heeft bezocht, weet je wat ik bedoel. En anders verwijs ik je naar de afbeelding. Dit is dezelfde Sudoku als de vorige keer, maar nu zijn in alle lege vakjes de cijfers 1 tot en met 9 ingevuld. Vervolgens verwijderen we secuur de kandidaten die niet meer mogelijk zijn. Ofwel de 9 in de eerste rij kan in alle acht cellen verwijderd worden. Dit zonder fouten doen is voor ons mensen lastig, maar een eitje voor de computer.
 |
Oplossen Sudoku’s dankzij boekhouding
De vorige keer hadden we, dankzij de tip in de tweede rij en kolom zeven en negen, een 2 genoteerd. De computer zegt nu dat de 2 de enige mogelijkheid is in de zevende rij en negende kolom. Deze cel ziet namelijk alle andere cijfers via de rij, kolom of het vierkant. De 4, 8, 1 en 5 zijn reeds aanwezig in de rij, de 3, 7 en 6 – de 5 hadden we al via de rij – via de kolom de 9 ten slotte via het vierkant. Daarmee blijft inderdaad alleen de 2 over. Dit tellen kan handig zijn als veel cellen reeds zijn ingevuld, maar de meeste mensen zullen dit niet doen als we aan een Sudoku beginnen.
Naakte alleenstaande
De 2 hiervoor noemen we in het Engels naked single. Die toevoeging maakt duidelijk dat er ook een andere vorm bestaat: hidden single. In zo’n cel zijn volgens de boekhouding nog meerdere kandidaten mogelijk, maar zijn deze op één na allemaal onmogelijk via de bekende Sudoku-regels. De 2 in de zesde rij is een goed voorbeeld. De enige kolom in deze rij waar het cijfer 2 voorkomt, is eveneens de zesde.
Deze kun je indirect ook via de tip vinden. Dat heb ik de vorige keer niet gebruikt en hebben we de 2 in de zesde kolom in de vierde en zesde rij genoteerd. Als je wat oefent met de tip, zie je tijdens het scannen bijna vanzelf dat de 2 in de vierde rij alleen nog maar in het zesde vierkant mogelijk is. Dit noemen we een pointing number en daarmee blijft voor 2 in het vijfde vierkant alleen nog maar de zesde rij over. Je ziet dat we op verschillende manieren tot dezelfde oplossing komen.
Programma
Hiervoor hebben we drie technieken laten zien waarmee we de boekhouding kunnen vereenvoudigen. De eerste stap is het vinden van de naked singles. In het voorbeeld is dat de hierboven beschreven 2 en verder een 6 en 8 in het vierde vierkant. Na invullen moet de computer deze als kandidaat verwijderen in dezelfde rij, kolom en vierkant waarin deze cel zich bevindt. De laatste twee zorgen voor nieuwe naked singles. Oftewel: we blijven dit herhalen totdat er geen nieuwe meer ontstaan. Dat is het punt dat je in het midden van de afbeelding ziet.
De volgende stap is het zoeken naar de hidden singles, zoals de 2 in de zesde rij. Deze functie in het programma doet niets anders dan kijken of een kandidaat nog maar in één cel van een rij, kolom of vierkant kan voorkomen. Zo ja, dan worden alle andere kandidaten in deze cel verwijderd zodat een naked single overblijft. Nadat dit voor alle cijfers is gedaan, wordt de hierboven beschreven functie aangeroepen. Het resultaat is het rechtse deel van de afbeelding. Er zijn wederom nieuwe naked singles ontstaan, dus we roepen ook nu deze functie recursief aan totdat er geen nieuwe worden gevonden of – en dat is voor deze het geval – de Sudoku is opgelost.
Resultaten
Zoals gezegd, heb ik een set van driehonderd moeilijke Sudoku’s die ik met de tip – in feite een afgeslankte versie van de boekhouding – allemaal kan oplossen. Met alleen naked singles lost de computer er twintig op. Door het zoeken naar hidden singles toe te voegen en dan recursief aanroepen van het zoeken naar naked singles worden er 71 opgelost. Niet indrukwekkend? Wat als we het zoeken naar hidden singles recursief aanroepen? Noteer nu uw gok. Het juiste antwoord is 227 stuks. Mijn programma codeert de oplossing als volgt:
U53,S3,S2,S3,S4,S5,S3,A10,A2,A4,A3,A2,A1,A4,A5,A2
U53,S1,A11,A2,A3,a7,A7,A1,A1,A2,A3,A2,A3,A1,A1,a10,A7,A6,A2
U53,S3,S3,S3,S1,A9,U34
De eerste is de Sudoku uit de afbeelding. Alle drie beginnen met 53 lege cellen, ofwel 28 gegeven oplossingen. De S en andere hoofdletters zijn het recursief aanroepen van het invullen van naked singles. Het getal erachter is het aantal dat in deze stap wordt gevonden. Ofwel de Sudoku uit de afbeelding vind 20 naked singles in zes keer recursief aanroepen. Daarna wordt het vinden van hidden singles aangeroepen. Als hierdoor naked singles ontstaan, gebruiken we de hoofdletter A en anders een kleine a.
Het cijfer achter die laatste geeft aan hoeveel kandidaten in deze stap zijn verwijderd. Zo lang dat niet nul is, heeft het zin om het vinden van hidden singles te herhalen. In de tweede Sudoku wordt dit twee keer met succes gedaan en worden weer een serie naked singles gevonden. Met uiteindelijk een opgeloste Sudoku. De laatste vindt in een nieuwe poging geen hidden singles en daarmee zijn alle geprogrammeerde technieken – in dit geval twee stuks – uitgeput. Er zijn nog 34 lege cellen aanwezig. Je ziet dat het aantal gegeven cijfers niets zegt over de moeilijkheid...
Tot slot
Met het toevoegen van pointing numbers worden alle driehonderd stuks opgelost. De set van twintigduizend stuks die ik zelf heb gegenereerd, wordt door deze drie technieken gereduceerd tot 2.163 onopgeloste. Daarin zal ik op zoek moeten naar de gewenste X-wing als benodigde techniek.
Hiervoor noemde ik het recursief aanroepen van zichzelf en de volgende stap. Dat bleek lastig en regelmatig stopte Python met een RecursionError, ofwel te vaak aanroepen zonder terugkeren naar de voorgaande aanroep. Uiteindelijk heb ik een het aanroepen gecodeerd in een hele serie if then regels die ik dankzij de uitvoer documentatie kon maken. Ik heb nu genoeg informatie om de genoemde fout te voorkomen, maar dat is nog niet geprogrammeerd. Ofwel: op dit moment is het niet iets wat ik wil publiceren, maar wie nieuwsgierig is kan een kopie krijgen om zelf mee te experimenteren.
