Sudoku Solver

Veel AI-algoritmes gaan over het vinden van een oplossing en hoe je deze zo effectief en effcient mogelijk weet te vinden. Sudoko is bij uitstek een spelletje waar je dit soort zoekalgoritmen kunt toepassen.

Bij sudo moet je een combinatie van getallen vinden in een veld van 9x9 zodanig dat:
- in iedere rij een getal tussen 1 en 9 maar één keer voorkomt
- in iedere kolom een getal tussen 1 en 9 maar één keer voorkomt
- in iedere 3x3 box een getal tussen 1 en 9 maar één keer voorkomt.

Er zijn bij de start van het spel altijd al enkele getallen gegeven.

Een manier om een sudoku op te lossen is om alle combintatie uit te proberen en te checken welke aan de eisen voldoet. Deze manier werkt, maar er zijn nogal wat mogelijkheden 9 in ieder cel namelijk en we hebben 81 cellen, dus er zijn 9 tot de macht 81 mogelijkheden!


In het dit programma wordt een iets intelligentere (efficientere) strategie gebruikt.  Het is geschreven in Java. Het is een ingewikkeld stukje software omdat het gebruikt maakt van recursie en backtracking.  Verder is er wat gegoogeld met rij en kolom nummers in de vorm van 1x1 arrays omdat java deze by reference doorgeeft in niet zoals standaard by value.






De werking van het zoek-algoritme is als volgt:

 Find row, col of an unassigned cell
  If there is none, return true
  For digits from 1 to 9
    a) If there is no conflict for digit at row,col
        assign digit to row,col and recursively try fill in rest of grid
    b) If recursion successful, return true
    c) Else, remove digit and try another // backtracking gedeelte
  If all digits have been tried and nothing worked, return false