WisFaq!

Hoe bewijs je dat een sudoku maar 1 oplossing heeft?

Ik doe mijn PWS over de sudoku, en zo kwam ik op de vraag hoe je bewijst dat een sudoku maar 1 oplossing heeft. Ik heb al gekeken naar allemaal soorten bewijzen, maar ik kom niet echt verder.

Ik neem aan dat ik zoiets nodig heb:

bewijs door opsplitsing van het onderstelde:

Een mogelijkheid zou de volgende kunnen zijn:
We splitsen p $\Leftrightarrow$ q in p $\Rightarrow$ q en q $\Rightarrow$ p

Iets soortgelijks is als je moet bewijzen dat er een unieke oplossing is voor een bepaald probleem. Je zou dan eerst kunnen bewijzen dat er een oplossing bestaat, en daarna dat die oplossing uniek is.

Zelf had ik al gedacht dat je eerst een algoritme moet bedenken voor het oplossen van een sudoku. (dit heb ik min of meer gedaan, wel vergelijkbaar met de NWD methode). En dat de sudoku dan 1 oplossing heeft, als die d.m.v. de algoritme oplosbaar is. (namelijk als die niet oplosbaar zal zijn zou die meer dan 1 oplossingen hebben, en dus geen 'echte' sudoku zijn.)
Dit is dan ook de reden van mijn vraag, want elke 'goede/echte' sudoku is wel oplosbaar. Ik wil juist weten wanneer een sudoku een 'goede/echte' sudoku is.
(Zo wil ik namelijk kijken of ik een idee kan krijgen wat het minst aantal startwaardes van een sudoku is)

Harmen

harmen
19-12-2009

Antwoord

Dit is een heel moeilijk probleem en het is nog (steeds) niet opgelost. In het tijdschrift `Notices of the American mathematical Society' (zie de link hieronder) stond een tijdje geleden een artikel waarin het probleem in termen van grafen werd geformuleerd maar dat leidde nog niet tot een bruikbaar antwoord.

Zie Notices of the American Mathematical Society [http://www.ams.org/notices/200706/index.html]

kphart
22-12-2009