\require{AMSmath}
WisFaq - de digitale vraagbaak voor wiskunde en wiskunde onderwijs


Printen

Sudoku

Als ik van links naar rechts in elke cel een random getal plaats die ik test op redundantie aangaande rij, kolom en blok (3·3). Dus 3 testen voor elk random getal. Mocht er redundantie optreden wordt het getal opnieuw willekeurig gekozen.

Mijn vraag is hoeveel keren de 3 testen doorlopen moeten worden voor een sudoku puzzel. Mijn vermoeden is meer dan 1 miljoen.

Jan
Ouder - dinsdag 12 mei 2020

Antwoord

Wat je beschrijft komt zo te zien neer op backtracking. Dat kan veel tijd kosten maar ik heb er geen diepzinnige analyse van gezien.

Je kunt een bovengrens geven. Het is bekend dat er minimaal zeventien cijfers gegeven moeten zijn voor een consistente puzzel bij zo'n puzzel heb je $64$ lege vakjes en als je elk vakje altijd alle negen cijfers probeert kom je op $9^{64}$ probeersels en dat is wel erg veel.

In de praktijk probeer je alleen cijfers die nog niet in de rij/kolom/blok staan en dat scheelt al wat en naar het eind toe hoef je nog maar weinig te proberen. Het lijkt er op dat een miljoen zelden gehaald wordt.

Hier is een puzzel die in het begin veel tijd kost maar aan het eind snel gevuld is.

En op deze site staan wat programma's om mee te experimenteren.

Zie Wikipedia: Sudoku, backtracking

kphart
woensdag 13 mei 2020

©2001-2024 WisFaq