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.