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
Leerling bovenbouw havo-vwo - zondag 22 januari 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 n²xn² 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

maandag 23 januari 2006

©2001-2024 WisFaq