|
|
|
\require{AMSmath}
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.
Herman
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
|
Vragen naar aanleiding van dit antwoord? Klik rechts..!
woensdag 13 mei 2020
|
|
home |
vandaag |
bijzonder |
gastenboek |
statistieken |
wie is wie? |
verhalen |
colofon
©2001-2024 WisFaq - versie 3
|
