Conclusie

Als gevolg van de resultaten kunnen we beschouwen dat een computer even geschikt is als onze hersennen voor het oplossen van een sudoku. Het moet stapsgewijs gebeuren en de computer doe het sneller, immers omdat het voor deze berekening werd "gespecialiseerd" aan de hand van een programma.

Het gaat om de oplossingen voor lege vakken steeds opnieuw te checken a.h.v. meerdere functie, waarbij de centrale hart van de programma de functie only_one() is. Deze zal immers oplossingen valideren. De andere functies zijn er dan om het aantal oplossingen te beperken door eliminatie.

In totaal krijgen we de hiërachie:

-readfile('tekst') #lees de tekst document
-classify('lijnen') #zet de lijnen om tot een lijst van matrices met een bepaalde sleutel (=dictionary)
-solve(grids): #meesterfunctie die de sudoku's zal oplossen. Eerst worden de lege vakken "geregistreerd".
      while not test = = empties: #de volgende functies werden in een loop gezet die op ieder moment checkt
                                              #als de functies nog iets veranderen aan de oplossingen
            #functie voor validatie van oplossingen
            -only_one(grid,empties)
            #functies voor eliminatie van oplossingen
            -X_Wings(empties)
            -align(empties)
            -double(empties)
-check('oplossingen') #ga na of er geen fout is opgetreden in de programma (bv. twee keer '4' in een rij)
-cum_sum('oplossingen','coördinaten') #berekent de totale som van de cijfers gevormd door bepaalde    
                                                           #vakken
-write_new('oplossingen','bestandsnaam') #schrijft de oplossingen in een nieuw tekst document

Er werden oorspronkelijk ook andere functies gemaakt maar deze werden verwijderd doordat ze overbodig waren. Voor sudoku's met een hogere moeilijkheidsgraad zullen ze misschien wel bruikbaar kunnen worden.

Tijd in functie van de sudokus

Hieronder bevindt zich een tabel met de tijd die het programma nodig heeft om bepaalde sudokus op te lossen. De moeilijkheidsgraad geeft aan hoe lang de computer ten opzichte van de langste tijd met een sudoku bezig was.

Sudoku|	t(s)	| Moeilijkheid
1	0,155	4,23%
2	0,161	4,40%
3	0,219	5,96%
4	0,167	4,56%
5	0,14	3,81%
6	1,237	33,70%
7	0,427	11,63%
8	0,168	4,59%
9	0,313	8,53%
10	2,284	62,26%
11	0,231	6,29%
12	0,161	4,40%
13	0,298	8,11%
14	0,184	5,01%
15	0,287	7,83%
16	0,112	3,04%
17	0,109	2,97%
18	0,188	5,12%
19	0,181	4,93%
20	0,165	4,49%
21	0,193	5,27%
22	0,279	7,61%
23	0,201	5,47%
24	0,207	5,65%
25	1,455	39,66%
26	0,316	8,61%
27	0,217	5,92%
28	0,213	5,82%
29	0,296	8,07%
30	0,225	6,13%
31	0,285	7,77%
32	0,224	6,11%
33	0,168	4,59%
34	0,172	4,70%
35	0,175	4,77%
36	0,171	4,67%
37	0,173	4,72%
38	0,174	4,73%
39	0,172	4,70%
40	0,173	4,71%
41	0,312	8,50%
42	2,861	77,96%
43	1,147	31,26%
44	0,42	11,46%
45	0,298	8,13%
46	0,331	9,01%
47	2,79	76,05%
48	0,428	11,67%
49	3,342	91,08%
50	3,669	100,00%
tot	28,27

Bron

Voor het vinden van sudokumethodes werd het volgende bron gebruikt:
http://ffsudoku.com/techniques.html

Het is een zeer bruikbare site voor wie aan sudoku's wil beginnen. Op deze methodes heb ik mijn verschillende functies gebaseerd en omgevormd tot een door de computer te begrijpen "taal".

Cumulatieve som

Met behulp van een zelfgemaakte functie cum_sum() heb ik de som van de getallen gevormd door de eerste drie cijfers van elke sudoku kunnen berekenen: deze is 24702.

#som van de cijfers gevorm door resp. vakken R1K1, R1K2 en R1K3
#van elke sudoku
>>> cum_sum(solutions,["00","01","02"])


24702

Align Align... Align Align...

Eindelijk heb ik de laatste functie kunnen aanmaken: de functie align(). 

Het methode berust op het feit dat als er binnen een grote vak (=regio) één cijfer alleen maar mogelijk is binnen een bepaalde rij of kolom, dan is dit cijfer niet mogelijk voor de vakken van dezelfde rij of kolom buiten de regio.

Gebruik makend van deze laatste functie bekom ik:

>>> solve(grids)

solved grids:  50/50

time:  34.887 s

Daarna heb ik een verificatiefunctie check() aangemaakt. Deze geeft mij aan als er een of meerdere problemen zijn in de verschillende sudoku's en of alles juist is.

>>> check(solutions)

All completed

Double was a double agent...

Nadat ik eventjes de oplossingen die ik kreeg bij het toepassen van mijn functie double() bekeek, zag ik met veel teleurstelling dat iets niet klopte. Ik ben dus op de definitie van de doubletmethode terug gegaan en zag dat ik de variant slecht had begrepen: er moet immers geen andere vak bestaan die in dezelfde entiteit de ene of de andere waarde bevat van de twee vakken (zie post: It gets harsh!).

Ik heb dit aangepast en zelfs de functies triple() en quad() op basis daarvan aangemaakt. Het is dezelfde principe als bij de double() functie maar dan met drie/vier waarden en vakken.

Het resultaat was onthutsend:

>>> solve(grids)



solved grids:  49/50
time:  32.956 s

Tot nu toe gebruikte stappenplan.

Op het laatste moment heb ik opgemerkt dat ik mijn stappenplan ben vergeten op te schrijven. Ik dacht immers geen "exacte plan" te gebruiken maar gewoon functies één per één aan te maken die mij tot mijn doel zouden kunnen brengen. Kort zou ik mijn stappenplan kunnen formuleren als volgt:

1) Txt-bestand met de sudoku's omzetten tot een lijst van 9x9 matrices.
2) Lijst aanmaken van candidaten van de lege vakken, gekoppeld met hun positie in de matrices.
3) Sudokumethodes vinden en omzetten in bruikbare functies. (t.e.m. het einde)
4) Eens dat er oplossingen gevonden zijn, deze in een nieuw txt-document opschrijven
5) Een testfunctie aanmaken die uittest als de oplossingen wel kloppen.
6) Optellen van elke 3-cijfers nummer in de linkertop van elke sudokus. (extra, als alle sudoku's zijn opgelost)

It gets harsh! Time to work double!

Wat merkwaardig is met de sudokus is dat hoe meer methodes je zoekt om ze te oplossen, hoe moeilijker en ingewikkeld de methodes worden!
Maar gelukkig kwamen er overtuigende resultaten na enkele dagen hard werken. Ik ben namelijk op een van de belangrijkste methodes na de basismethodes gevallen: de doubletten!

Deze berust op het feit dat als twee vakken binnen een entiteit (zelfde rij, kolom of grote vak) elk alleen maar twee keer dezelfde mogelijkheden bevatten (d.i. a =/= b met a,b ∈ [1,9] ∩ ℕ), alle andere vakken binnen deze entiteit deze twee mogelijkheden juist niet kunnen bevatten.

Er is ook een variant daarop waarbij als twee vakken binnen een entiteit de enige vakken zijn die twee bepaalde mogelijkheden bevatten, alle andere mogelijkheden binnen deze twee vakken kunnen worden uitgesloten.



Dit principe heb ik dus vervat in een functie met naam double(). Het is toch opmerkelijk dat het voltooiing van het tweede deel van de functie (de variant) veel meer tijd nodig heeft. Ik heb uiteindelijk ook gekozen om de niet volledig opgeloste sudokus op het scherm te laten verschijnen om ze later te kunnen analyseren.


>>> solve(grids)



solved grids:  47/50
time:  37.046 s

X-Wings: we solved two more...

Na eventjes zoeken op het internet ben ik op een zeer nuttige techniek gevallen: de X-Wings methode. Het is een techniek die meestal bij moeilijke sudokus wordt toegepast.

De methode houdt in dat we twee rijen/kolommen moeten vinden waarbij er per rij/kolom maximaal twee vakken bestaan die een bepaalde cijfer als mogelijkheid bevatten in overeenkomstige kolommen/rijen. In totaal krijgen we dan vier vakken die een rechthoek vormen. Het plaatsen van dit cijfer in een van de vier vakken impliceert noodzakeljik dat de vakken in de aanliggende hoekpunten dit cijfer juist niet kunnen bevatten en dat de vak in de overeenstaande hoekpunt opnieuw dit cijfer moet bevatten. Hierdoor kunnen de overblijvende vakken van de twee kolommen/rijen dit cijfer dus ook niet bevatten.
Dit principe heb ik dus nagebootst met mijn functie X_Wings(), die de nodige rijen of kolommen opzoekt.

Voor een betere tijdsefficiëntie heb ik ook beslist om de functie only_of() in de loop van de functie only_one() te plaatsen, zodat de ene wordt toegepast als de andere niet kan.


>>> solve(grids)



solved grids:  42/50
time:  14.755 s

40 op 50!

Nadat een timer en een counter werd toegevoegd aan mijn functie solve(), heb ik met verbazing opgemerkt dat mijn functie al 40 van 50 gegeven sudokus kon oplossen!

mijn functie is namelijk o.a. onderverdeeld in twee "test"-functies, only_one() en only_of().


only_one() gaat na of er maar een mogelijkheid is voor een vak terwijl only_of() nagaat of een mogelijkheid voor een vak nergens voorkomt in de mogelijkheden voor vakken in dezelfde rij, kolom of grote vak.


#try to solve all grids and write(partially) solved sudokus in a text-file
>>> solve(grids)


solved grids:  40/50
time:  14.739 s

click op meer lezen voor de functies  only_one() en only_of()

Mijn eerste opgeloste sudoku!

Met de functie solve() die ik aan het maken ben heeft Python de eerste sudoku opgelost, gewoon door het nagaan van alle mogelijkheden in ieder leeg vakje. Dit gaat door te zien welke cijfers noch  in dezelfde rij, noch in dezelfde kolommen, noch in dezelfde grote vakken voorkomen.

>>> grids[1]
[[0, 0, 3, 0, 2, 0, 6, 0, 0],
 [9, 0, 0, 3, 0, 5, 0, 0, 1],
 [0, 0, 1, 8, 0, 6, 4, 0, 0],
 [0, 0, 8, 1, 0, 2, 9, 0, 0],
 [7, 0, 0, 0, 0, 0, 0, 0, 8],
 [0, 0, 6, 7, 0, 8, 2, 0, 0],
 [0, 0, 2, 6, 0, 9, 5, 0, 0],
 [8, 0, 0, 2, 0, 3, 0, 0, 9],
 [0, 0, 5, 0, 1, 0, 3, 0, 0]]


>>> solve(grids,[1])
[[4, 8, 3, 9, 2, 1, 6, 5, 7],
 [9, 6, 7, 3, 4, 5, 8, 2, 1],
 [2, 5, 1, 8, 7, 6, 4, 9, 3],
 [5, 4, 8, 1, 3, 2, 9, 7, 6],
 [7, 2, 9, 5, 6, 4, 1, 3, 8],
 [1, 3, 6, 7, 9, 8, 2, 4, 5],
 [3, 7, 2, 6, 8, 9, 5, 1, 4],
 [8, 1, 4, 2, 5, 3, 7, 6, 9],
 [6, 9, 5, 4, 1, 7, 3, 8, 2]]

Een txt-document omzetten naar een matrix: hoe?

Om een sudoku te laten lezen op een automatische manier en die om te zetten in een door Python leesbare matrix moest ik eerst eventjes zoeken in de basis van het openen en schrijven van documenten: de functie open().

Op basis daarvan heb ik dan een functie readfile() gemaakt die de tekst opent en omzet in een lijst van lijnen. Om de verschillende sudokus gemakkelijk te kunnen manipuleren heb ik een functie classify() gemaakt die de lijnen lezen en de verschillende sudokus groeperen in een dictionnary.

Om de functies te zien, klik op meer lezen.

Onderzoeksvraag OC

De onderzoeksvraag van mijn OC luidt als volgt:
Hoe kan men een sudoku oplossen met een computer?


Om daarop een antwoord te geven zal ik bij voorkeur gebruik maken van het programmeertaal Python, voor zijn flexibiliteit.