Python - sudokusolver 2/2

• Informatica
• Middelbare school
• vwo
• Leerjaar 5

Python

Sudokusolver 2/2

• Je kan in een python grid (lijst in lijst) controleren of een getal in de x-as of de y-as voorkomt
• Je kan een algoritme schrijven dat gebruik maakt van backtracking

3. getal mag één keer voorkomen in een blok

1. Getal mag één keer voorkomen in een rij

2. Getal mag één keer voorkomen in een kolom

Sudoku solver

Eerst drie deelproblemen oplossen om erachter te komen of een getal op een bepaalde plek is toegestaan.

NumberInRow

Output

Wat is de output?

NumberInColumn

Output

Wat is de output?

NumberInBox

Output

Wat is de output?

NumberPossible

Output

Wat is de output?

Sudoku solver

We hebben nu de drie/vier belangrijkste deelproblemen opgelost.

Hoe kunnen we nu de sudoku oplossen?

Opdracht

Schrijf op papier een oplossing die je zou kunnen programmeren. Probeer systematisch te werk te gaan; bedenk een algoritme!

Maak een foto van je oplossing en load deze hier up ^ ^

Backtracking

Een voorbeeld van de oplossing die we gaan programmeren zie je hier. Je ziet hier goed dat het programma aan het uitproberen is. Er worden getallen ingevuld zolang het kan. Kan een getal niet, dan gaat het programma terug naar het vorige vakje en probeert het met een ander getal. Dit heet backtracking

https://repl.it/@TimLogtenberg/sudokusolver-backtracking

Solve

Hier gebeurt iets bijzonders. Er wordt gebruik gemaakt van ... om voor elk vakje te berekenen of het getal mogelijk is. Zodra een getal niet meer mogelijk is wordt er een return uitgevoerd. Daardoor gaat de code "uit" de functie en verder op regel 68 en wordt het getal weer op 0 gezet.

Huiswerk

Opdrachten voor soduko in repl.it. Behalve de laatste want daar heb je backtracking voor nodig..

lgg

Bronnen

• https://www.youtube.com/watch?v=G_UYXzGuqvM
• https://www.youtube.com/watch?v=8lhxIOAfDss

lgg