Voor even was ik gegrepen door sudoku, je weet wel, die cijferpuzzeltjes die je mensen overal ziet spelen. Je begint met een rooster van negen bij negen vakjes, waarin hier en daar al een cijfer is ingevuld. Dan moet je zó cijfers bijplaatsen, dat op de rijen, op de kolommen, én in ieder kleiner vierkant van drie bij drie de cijfers 1 tot en met 9 elk maar een keer voorkomen.

Afgelopen oktober was ik met mijn vriend op vakantie in Suriname, waar we de bruiloft van een vriend in Guyana bijwoonden. Zijn zussen (zie foto) vulden de tijd met het oplossen van sudoku's.

Toegegeven, het werkt verslavend: uiteindelijk zat ook ik in het hobbelige busje van Paramaribo naar Guyana, in een korjaal op de Essequibo, en op de vele veerponten te cijferen op verkreukelde sudokupapiertjes.

Terug op mijn werk in Gent filosofeerde ik met een collega over methodes om de sudoku's automatisch op te lossen; we kwamen op verschillende algoritmes, de een nog exotischer dan de andere. Een paar dagen later ging ik met de trein naar Lyon, en onderweg, verveeld, heb ik een doodsimpel computerprogrammaatje geschreven.

Honderden geeks zoals ik kwamen op dezelfde of betere methodes (zie bv. op wikipedia), maar in de trein had ik geen toegang tot internet... is dat een excuus voor mijn dubbel werk? Als eerste zet je in ieder leeg vakje de cijfers 1 t/m 9: je weet verder niets over de sudoku, dus kan op elk vakje nog elk mogelijk cijfer staan.

Daarna ga je kandidaatcijfers wegstrepen. Eerst voor de rijen: staat er in de zelfde rij een 8, dan kun je elders in de rij de achten wegstrepen. Immers, de acht mag maar een keer voorkomen. Als je hetzelfde hebt gedaan voor alle rijen, alle kolommen en alle vierkantjes, dan zijn er zeer waarschijnlijk vakjes waar nog maar één cijfer overblijft.

Aan de hand van deze bekend geworden cijfers kun je bij herhaling van de procedure opnieuw cijfers wegstrepen, en na een tiental herhalingen, die de computer niet meer dan een oogwenk kosten, zijn alle cijfers meestal wel bekend.

Zo simpel is het dus. Eigenlijk wel teleurstellend. Stiekem hoopte dat mijn programmaatje zich zou verslikken in de moeilijker sudoku's: die kwamen halverwege misschien op situaties waar mijn programma twee kanten op kon, en dus eigenlijk een paar stappen vooruit zou moeten denken.

Zeker, dat soort sudoku's bestaan, en ook de bijbehorende computeroplossingen, maar in mijn dagelijkse sudokuleverancier, de Vlaamse krant De Morgen, ben ik ze nog niet tegengekomen.

Volgend artikel in dit blog