WisFaq!

\require{AMSmath} geprint op zaterdag 28 januari 2023

Het oplossen van een sudoku is een NP-compleet probleem

Ik moet voor een opdracht een algemene formule vinden voor het oplossen van een sudoku. Dus ik moet door middel van een formule weten welk getal op welke plek moet komen te staan. Heeft iemand een idee hoe ik dat moet doen?
Ik ben begonnen naar het kijken van magische vierkante/tovervierkanten. De magische constante (15) en de som van alle getallen (45) weet ik. Maar dan weet je nog niet op welke plek welk getal moet komen te staan..
Kan iemand mij helpen?

Aapje
22-1-2006

Antwoord

Met magische vierkanten heeft het (denk ik) weinig te maken. Je zou de puzzels zelfs met plaatjes kunnen doen! Toch zijn er natuurlijk wel algoritmen te bedenken die een sudoku kunnen oplossen...
Zie bijvoorbeeld Speciale Sudoku.

Het algemene probleem om een nxn sudoku puzzel op te lossen is een zogenaamd NP-compleet probleem. NP-complete problemen zijn heel lastige problemen, waarvan het erg onwaarschijnlijk is dat ze ooit snel met een computer zijn op te lossen.

Zie Sudoku - Kennislink [http://www.kennislink.nl/web/show?id=133739]

WvR
23-1-2006


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

#43194 - Puzzels - Leerling bovenbouw havo-vwo