Sudoku Puzzels

Introductie

De laatste rage in puzzelland op dit moment is de Sudoku puzzel. Ook ik ben momenteel door het Sudoku virus getroffen. Een Sudoku puzzel bestaat uit een vierkant van 81 vakjes, verdeeld in 9 grote vierkanten van ieder 3×3 vakjes. In een lege puzzel staan in een aantal van de vakjes getallen van 1 t/m 9 ingevuld en het is de bedoeling de puzzel zo te vullen dat in iedere rij, kolom en blok van 3×3 ieder getal van 1 t/m 9 maar één maal voorkomt. Door logisch nadenken, combineren en elimineren kan de puzzel worden ingevuld.

Oplossen van een Sudoku puzzel

Hieronder staan een aantal stappen weergegeven die helpen bij het oplossen van een puzzel.

	A	B	C	D	F	G	H	I
1	6	1	8			4	4	5
2					4	1
3		4		1	6		9

De eerste stap is eenvoudig, zoek in alle rijen en kolommen van 3 3×3 blokken naar getallen die al in 2 blokken voorkomen en waarvoor in het derde blok maar één positie mogelijk is. In het voorbeeld hiernaast komt de 1 voor op positie D3 en G2 wat betekent dat in het blok A1C3 de 1 alleen nog geplaatst kan worden op positie B1, hiernaast weergegeven in het rood. Het cijfer 4 komt ook 2 maal voor (B3 en F2) en zal dus uiteindelijk in het blok G1I3 terecht komen op positie G1 of H1, maar dat kan nu nog niet worden ingevuld.

	A	B	C	D	F	G	H	I
1	6	1	8				4	5
2					4	1
3		4		1	6		9
4						5
5								7
6						4	6

Bij de volgende stap moeten gegevens uit de kolommen, rijen en blokken worden gecombineerd. In het verder uitgewerkte voorbeeld hiernaast staat in kolom G op G6 een 4. Dit betekent dat de 4 uit bovenstaand voorbeeld dus niet op G1 kan staan en dus op H1 terecht zal komen.

	A	B	C	D	E	F	G	H	I
1	6	1	8					4	5
2						4	1
3		4		1		6		9
4		6	6				5
5		2	9	8	6				7
6							4	6

In deze stap worden de gegevens uit meerdere rijen en kolommen gecombineerd. Omdat er in rij 6 een 6 staat op H6 en in kolom A op A1 betekent dit dat de 6 voor blok A4C6 alleen kan staan in rij 4 op B4 of C4. Voor het blok D4F6 betekent dit dat de 6 alleen kan staan op E5 of F5, maar de laatste wordt geblokkeerd door de 6 op F3. Hierdoor kan de 6 voor blok D4F6 alleen nog maar op E5 staan.

	A	B	C	D	E	F	G	H	I
1	6	1	8					4	5
2						4	1
3		4		1		6		9
4							5	1 2 3 8	1 2 8 9
5		2	9	8	6		3	1 3	7
6							4	6	1 2 8 9

Een andere mogelijkheid is om te kijken welke getallen nog nodig zijn in een bepaalde rij, kolom of blok en te zoeken of er conflicten ontstaan met andere rijen en kolommen. Als er zo een vak onstaat waar maar één getal staat moet dat daar worden ingevuld. In blok G4I6 kan de 1 alleen nog staan op H4, H5, I4 of I6. De 2 op H4, I4 of I6. De 3 op H4, G5 of H5. De 8 op H4, I4 of I6 en de 9 op I4 of I6. Hieruit blijkt dan dat voor G5 de 3 als enige mogeljke overblijft. Die 3 is dan niet meer mogelijk op H5 en daar blijft dan de 1 als enige mogelijke over.

Door dit steeds maar schrappen van mogelijke getallen en vervolgens weer de andere stappen te herhalen kan uiteindelijk de puzzel geheel worden ingevuld. Meer en uitgebreidere methodes voor het oplossen van de puzzel kunnen bijvoorbeeld op Sudoku Net worden gevonden.

Software voor het oplossen van een Sudoku puzzel

Sudoku puzzels, net als andere cijfer puzzels trouwens, lenen zich uitstekend om te worden opgelost door een computer. En ik vind het dan voor mij, als iemand die werkzaam is in de IT, een uitdaging om een stuk software te schrijven die dergelijke puzzels kan oplossen. Het gaat mij dan niet zozeer om de oplossing van de puzzel als wel de uitdaging om algoritmen te bedenken om een cijfer puzzel op te lossen. Een zoektocht op het internet leert dat dat voor meer mensen een uitdaging is. De meeste programma's echter maken gebruiken van brute-force. Ze vullen net zolang getallen in in vakjes tot er een conflict optreedt en gaan dan terug om het met een ander getal te proberen en doen dat net zolang tot er geen conflicten meer zijn en dan is de puzzel opgelost. Dit zijn vrij eenvoudige programma's en deze methode kan voor iedere cijfer puzzel worden gebruikt. De uitdaging voor mij is om een programma te schrijven die de puzzel op dezelfde manier oplost als een mens. Alleen bij heel complexe puzzels neemt het programma als hij het niet verder op de manier van combineren en wegstrepen kan oplossen als allerlaatste stap zijn toevlucht tot de brute-force methode.

Hieronder vindt je een zipfile met daarin een EXE file voor de PC, het programma draait in een dos box met als input een puzzeldefinitie file (*.sdk). Ook kun je in de windows explorer een SDK file droppen op de executable. Het programma genereert een HTML file in dezelfde folder als waar de SDK file staat met dezelfde naam, maar met de extensie .htm ipv .sdk. Deze HTML file kan in een moderne browser worden ingelezen om de oplossing van de puzzel te zien en om eventueel de stappen te zien hoe het programma tot die oplossing is gekomen. Daarnaast bevat de zipfile een aantal voorbeeld puzzels en een readme file. Voor de geïnteresseerden zit de C sourcecode er ook bij. Het programma is geschreven in standaard ANSI-C zodat het ook met bijvoorbeeld gcc op *nix een executable kan worden gebouwd (gcc sudoku.c -o sudoku). Vanaf versie 2.0 detecteert het programma ook dat er eventueel meerdere oplossingen mogelijk zijn voor een bepaalde sudoku puzzel, in dat geval is uiteraard de puzzel niet correct.

Op 10 en 11 maart 2006 werd in het Italiaanse Lucca het WK Sudoku gehouden. De finale Sudoku stond op 13 maart in het AD en deze heb ik vervolgens direct in het programma ingevoerd. Met als resultaat dat de puzzel alleen middels de brute-force methode kon worden opgelost. Ik kon hem echter zelf met de hand zonder brute-force oplossen, dus het programma moet dat dan ook kunnen. Na analyse van het resultaat waar het programma stopte heb ik het programma aangepast met als resultaat dat de finale sudoku nu wel kan worden opgelost zonder brute-force methode. Een bijkomend voordeel is dat nu ook andere puzzels sneller kunnen worden opgelost. In onderstaande zipfile is de finale sudoku ook opgenomen. Dit alles is met versie 2.1 van het programma aangepast. In deze versie is tevens het maximaal aantal oplossingen (uit versie 2.0) beperkt tot 25, dit om te voorkomen dat als er een lege puzzel wordt aangeboden het programma tot in het oneindige blijft zoeken naar alle mogelijke oplossingen.

Versie 2.2 voegt een extra oplos methode toe, zodat nog meer puzzels kunnen worden opgelost zonder dat gebruik hoeft te worden gemaakt van de brute-force methode. De extra oplos methode is de zogenaamde Method D oplossing.

	Bestand:	sudoku.zip
	Versie:	2.2
	# Downloads:	6633
	Grootte:	39 KBytes

Hoeveel mogelijke Sudoku puzzels zijn er?

Iedere puzzel heeft maar één mogelijke oplossing, maar op een gegeven moment vroeg ik me af hoeveel mogelijke puzzels er nu eigenlijk zijn. Ik ben geen wiskundige, dus in eerste instantie had ik geen idee hoe dit te berekenen. Totdat ik bedacht dat je eenvoudig voor ieder hokje in een puzzel moet bepalen hoeveel mogelijke getallen je er in kan vullen, daarbij kijkend naar de restrictie dat ieder getal van 1 t/m 9 maar één maal kan voorkomen in iedere rij, kolom en blok van 3×3. Beginnend links bovenaan en daarna van links naar rechts en van boven naar beneden kun je de volgende getallen invullen. Voor vakje A1 is ieder getal van 1 t/m 9 mogelijk dus 9 mogelijkheden, voor B1 dan 1 minder en zo door tot I8 waarvoor maar 1 getal meer mogelijk is. Voor rij 2 moet op A2 6 worden ingevuld ivm de restrictie van het blok A1C3 waarvoor al 3 getallen zijn ingevuld op A1, B1 en C1. Op B2 dan dus 5 en op C2 4. Op D2 weer 6 (restrictie voor zowel rij 2 als blok D1F3), op E2 5, enz. Het cijfer wat je op een bepaalde positie (R,K) (R = [1,9], K = [1,9], K in dit geval ook 1 t/m 9 ipv A t/m I) kan op de volgende manier worden bepaald:

	A	B	C	D	E	F	G	H	I
1	9	8	7	6	5	4	3	2	1
2	6	5	4	6	5	4	3	2	1
3	3	2	1	3	2	1	3	2	1
4	6	6	6	6	5	4	3	2	1
5	5	5	4	5	5	4	3	2	1
6	3	2	1	3	2	1	3	2	1
7	3	3	3	3	3	3	3	2	1
8	2	2	2	2	2	2	2	2	1
9	1	1	1	1	1	1	1	1	1

f_rij(R,K) = 9 - (K-1)

f_kolom(R,K) = 9 - (R-1)

f_blok(R,K) = 9 - ((K-1) % 3 + 3 * ((R-1) % 3))

Bovenstaande drie formules houden alleen rekening met de restricties in 1 richting, dus f_rij(R,K) houdt alleen rekening met de restricties binnen rij R, f_kolom(R,K) met die binnen kolom K en f_blok(R,K) met die binnen het blok van 3×3 waarbinnen (R,K) valt. Het getal wat vervolgens op een bepaalde positie (R,K) moet worden ingevuld is het minimum van deze drie functies:

f(R,K) = min(f_rij(R,K), f_kolom(R,K), f_blok(R,K))

Vullen we een puzzel in volgens bovenstaande formule dan ziet het aantal mogelijkheden per vakje er uit als in de puzzel is weergegeven. Willen we nu weten hoeveel mogelijkheden er zijn dan volgt dat uit de vermenigvuldiging van alle mogelijkheden per vakje:

	9	9
N =	∏	∏	f(R,K)
	R=1	K=1

Het totaal aantal mogelijkheden N wordt dan: 15.284.122.844.890.207.459.737.600.000.000. Uit te spreken als: 15 quintiljoen 284 quadriljard 122 quadriljoen 844 triljard 890 triljoen 207 biljard 459 biljoen 737 miljard 600 miljoen. Let wel op: dit getal is inclusief geroteerde en gespiegelde puzzels en puzzels met verwisselde cijfers (als je in een puzzel bv alle 1-en en 2-en verwisseld heb je eigenlijk dezelfde puzzel, al deze verwissel mogelijkheden zijn echter wel in bovenstaand getal meegenomen).

Heeft iemand aan- of opmerkingen over deze berekening dan hoor ik dat graag. Stuur me dan een email.

Inmiddels heb ik de afgelopen tijd al diverse opmerkingen gehad mbt bovenstaande berekening en hij klopt inderdaad niet. In het blok G7I9 bv kunnen alleen maar 1-en staan omdat daarvoor de getallen al worden bepaald door de kolommen erboven en de rijen ervoor. En voor bv de getallen D2-F2 geldt niet in alle gevallen dat daar 6,5,4 mogelijkheden zijn. Dat klopt wel als alleen naar het blok D1F3 wordt gekeken, maar ook de getallen in A2-C2 hebben invloed op het aantal mogelijkheden voor de getallen in D2-F2. En dit geldt voor meerdere blokken. Het bovengenoemde getal is dus niet correct.

Sudoku Links

Hieronder nog wat links naar andere sites mbt Sudoku puzzels:

Heb jezelf een site mbt Sudoku puzzels en wil je hier een link naar je pagina, neem dan op je eigen pagina een link op naar deze pagina en stuur mij een email.