WisFaq!

\require{AMSmath} geprint op vrijdag 29 maart 2024

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
12-5-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 [https://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Backtracking]

kphart
13-5-2020


© 2001-2024 WisFaq
WisFaq - de digitale vraagbaak voor het wiskunde onderwijs - http://www.wisfaq.nl

#89857 - Kansrekenen - Ouder