Sudoku 17 aanwijzingen Gemiddeld
Laatste scorelijst voor #21528
Laatste scorelijst voor Sudoku 17 aanwijzingen
Hoe speel je Sudoku 17 aanwijzingen
Het is bewezen dat een standaard Sudoku-puzzel minimaal 17 aanwijzingen moet hebben om een unieke oplossing te hebben.
Sudoku-regels:
-
Vul de cijfers 1-9 in elke rij, kolom en 3x3 subraster in een 9x9 raster.
-
Elk getal kan slechts één keer voorkomen in elke rij, kolom en 3x3 subraster.
-
Vul de lege ruimtes in met de cijfers 1-9, zodat elke rij, kolom en 3x3 subraster alle cijfers 1-9 bevat.
Sudoku is een op logica gebaseerde puzzel voor het plaatsen van getallen. Het doel is om een 9x9-raster te vullen met de cijfers 1-9, zodat elke rij, kolom en 3x3-subraster alle negen getallen precies één keer bevat.
In 2009 bewezen Gary McGuire en zijn team dat elke Sudoku-puzzel met 16 aanwijzingen minstens twee oplossingen moet hebben. Ze deden dit door gebruik te maken van een techniek die 'dode patronen' wordt genoemd.
Een dood patroon is een Sudoku-configuratie die twee of meer mogelijke oplossingen heeft. McGuire en zijn team ontdekten dat elke Sudoku-puzzel met 16 aanwijzingen minstens één dood patroon moet bevatten. Daarom moeten deze puzzels minstens twee oplossingen hebben.
Dit resultaat heeft verschillende implicaties. Ten eerste betekent dit dat er niet zoiets bestaat als een Sudoku-puzzel van 16 aanwijzingen met een unieke oplossing. Ten tweede betekent het dat elke Sudoku-puzzel met 16 aanwijzingen op meerdere manieren kan worden opgelost. Ten derde betekent dit dat er een oneindig aantal Sudoku-puzzels met 16 aanwijzingen zijn.
Hier is een meer technische uitleg van het bewijs dat Sudoku-puzzels minstens 17 aanwijzingen moeten hebben om een unieke oplossing te hebben:
Het bewijs begint met het beschouwen van een Sudoku-puzzel met 16 aanwijzingen. We kunnen deze puzzel beschouwen als een reeks beperkingen voor de getallen die in de lege vierkanten kunnen worden geplaatst.
We kunnen dan een techniek gebruiken die 'backtracking' wordt genoemd om te proberen een oplossing voor de puzzel te vinden. Backtracking is een recursief algoritme dat alle mogelijke combinaties van getallen in de lege vierkanten probeert totdat het een oplossing vindt.
Als er een unieke oplossing voor de puzzel bestaat, zal backtracking die uiteindelijk vinden. Als er echter meerdere oplossingen zijn, zal backtracking wellicht nooit een oplossing vinden.
McGuire en zijn team gebruikten backtracking om te laten zien dat als er een Sudoku-puzzel van 16 aanwijzingen is met een unieke oplossing, er een manier moet zijn om het backtracking-algoritme zo te starten dat het altijd de oplossing vindt.
Toen lieten ze zien dat dit niet mogelijk is. Ze deden dit door een set van 16 aanwijzingen te construeren die naar een dood patroon leiden. Dit dode patroon betekent dat er twee mogelijke oplossingen voor de puzzel zijn en dat er geen manier is om het backtracking-algoritme zo te starten dat het altijd dezelfde oplossing vindt.
Dit resultaat laat zien dat elke Sudoku-puzzel met 16 aanwijzingen minstens twee oplossingen moet hebben.
