Sudoku
Van Wikipedia
Een sudoku is een puzzel van negen bij negen vakjes met een klein aantal reeds ingevulde enkelvoudige cijfers. De kunst is de overige vakjes ook in te vullen op zo'n manier dat in elke horizontale lijn én in elke verticale kolom de cijfers 1 tot en met 9 één keer voorkomen. Bovendien is de puzzel onderverdeeld in negen blokjes van drie bij drie, die elk ook weer eenmaal de cijfers 1 tot en met 9 moeten bevatten.
Anders dan veel andere puzzels zijn sudoku's op te lossen door iedereen die bereid is zijn hersens enige tijd geconcentreerd te gebruiken en systematisch na te denken. Ook is het niet vereist enige wiskundige kennis te hebben, aangezien de symbolen geen betekenis hebben, behalve dat ze verschillend zijn. Andere symbolen kunnen ook.
De moeilijkheidsgraad van een opgave is in tegenstelling tot wat vaak gezegd wordt niet echt afhankelijk van het aantal reeds ingevulde cijfers. Een opgave met 19 gegevens kan heel eenvoudig zijn en een met 36 gegevens heel moeilijk. (Bij het willekeurig genereren van opgaven met 19 gegevens lijkt het aantal moeilijke puzzels zelfs een beetje lager dan dat bij 24 gegevens.) Er zijn sudoku's bekend met 17 gegevens (en een unieke oplossing), maar tot dusver niet met 16 gegevens.
Bij het maken van een opgave moet het computerprogramma eerst een oplossing genereren d.m.v. willekeurige verdelingen van de 9 cijfers en toetsing van de rij-kolom-blok-compatibiliteit. Zodra een nieuwe oplossing is gevonden moet ze omgezet worden naar een opgave door er (eveneens willekeurig) een aantal cijfers van vrij te geven. Het computerprogramma moet dan nagaan of de vrijgegeven cijfers een eenduidige oplossing toelaten. Is dat niet het geval, dan kan een bijkomend cijfer vrijgegeven worden (en telkens weer een volgend), tot de puzzel eenduidig oplosbaar is. Computerprogramma's die een uitgekiende oplossingsstrategie gebruiken zijn derhalve in staat moeilijker puzzels te produceren, want zij moeten minder snel een cijfer vrijgeven. Zo komt het voor dat puzzels met slechts 25 of occasioneel zelfs 24 vrijgegeven cijfers geproduceerd kunnen worden. Maar al bij al kunnen die soms minder moeilijk zijn dan een 26-cijfer-combinatie omdat daar toevallig redundante vrijgevingen zijn.
Inhoud |
[bewerk] Ontstaan
De puzzel is ontworpen door Howard Garns, een gepensioneerde architect en freelance puzzelmaker en werd voor het eerst gepubliceerd in 1979 onder de naam Number Place. De puzzel werd in 1984 door Nikoli in Japan geïntroduceerd waar het ook de naam sudoku (samenvoeging van Suuji wa dokushin ni kagiru (Dit betekent dat het beperkt is tot onafhankelijke, "ongetrouwde", getallen. 'su' betekent getal, 'doku' betekent onafhankelijk, ongetrouwd )) kreeg. Vanaf 1986 genoot sudoku populariteit in Japan. In 1997 zag Wayne Gould, een Nieuw-Zeelandse gepensioneerde, een sudoku en werkte vervolgens 6 jaar aan een computerprogramma om sudoku's op te stellen. Hij verkocht de hele zaak aan The Times die op 12 november 2004 begon met het publiceren van de puzzels. Een nieuwe rage was geboren. In de zomer van 2005 werd de puzzel ook geïntroduceerd in Nederland en kende al snel grote populariteit, onder meer omdat veel kranten dagelijks een sudoku begonnen af te drukken. Op 15 oktober 2005 werden de eerste Nederlandse kampioenschappen sudoku gehouden in het Scheepvaartmuseum te Amsterdam. Delia Keetman uit Heerhugowaard werd eerste...
[bewerk] Oplosstrategie 1
We nemen als voorbeeld de lege puzzel van hierboven.
[bewerk] Stap 1
- Zoek een rij met weinig lege vakjes. In dit geval de 3e rij van boven.
- De getallen die in die rij nog ontbreken zijn 2 en 6.
- De 2 kan niet in het eerste lege hokje staan, omdat in deze kolom al een 2 staat.
- De 2 moet dus in het laatste lege hokje staan.
[bewerk] Stap 2
- Omdat nu alleen de 6 nog ontbreekt in deze rij, kun je die zo invullen.
[bewerk] Stap 3
- In het blok links onder ontbreken nog de 5, de 6 en de 7. Neem bijvoorbeeld de 7.
- De 7 kan niet in de bovenste 2 rijen (van het blokje!) staan, omdat in die rijen al een 7 staat.
- De 7 kan ook niet in de eerste kolom staan, want daar staat ook al een 7.
- Ook kan de 7 niet rechtsonder staan, want daar staat al een 8.
- De 7 moet dus wel onder in het midden.
[bewerk] Stap 4
- Nu ontbreken in dit blok alleen de 5 en de 6 nog.
- De 6 kan niet in de rechterkolom, omdat daarin al een 6 staat.
- De 6 moet dus in het vakje linksmidden.
[bewerk] Stap 5
- Alleen de 5 in het blok linksonder ontbreekt nog, deze moet dus in het vakje rechtsmidden.
[bewerk] Oplosstrategie 2
Als de opgaven moeilijker zijn, zijn er meestal geen rijen die al bijna compleet ingevuld zijn. Dan is bijvoorbeeld deze strategie handig:
[bewerk] Stap 1
Zoek in een rij van drie blokken (horizontaal of verticaal) twee blokken met hetzelfde symbool. Bijvoorbeeld de 4-en in de rechter verticale rij.
[bewerk] Stap 2
Elk symbool komt één keer in ieder blok en in elke rij voor. Het blok rechtsboven mist nog een 4. De 4 past logischerwijs alleen in de eerste kolom. In die kolom is nog één mogelijkheid open.
[bewerk] Vervolg
Merk op dat nu in de eerste horizontale rij van drie blokken, twee blokken een 4 hebben gekregen. In het blok linksboven moet een 4 komen op de middelste regel. Door de 4 , die in het blok linksonder staat, kan die maar op één plek worden ingevuld.
[bewerk] En verder
De rest van de puzzel kunt u zelf oplossen. Nog enkele tips:
- Concentreer u op één cijfer, bijvoorbeeld een cijfer dat al vaak voorkomt.
- Begin met een blok, rij of kolom die al bijna vol is.
- Blijf strategieën herhalen. Elke keer als u een cijfer hebt ingevuld blijven er minder mogelijkheden over.
- Ook kunt u aantekeningen maken: de mogelijke getallen voor een hokje klein erin zetten. Zodra u ergens anders in de kolom of rij een van deze getallen invult, kunt u ze in dat hokje wegstrepen. Zo blijft er uiteindelijk één mogelijkheid over.
[bewerk] Varianten
Toen de Number Place puzzels voor het eerst in Dell's puzzelbladen verschenen, stonden er extra aanwijzingen buiten het puzzelveld. Later zijn de puzzels vereenvoudigd tot wat we nu standaard Sudoku noemen. De originele puzzels met extra aanwijzingen zouden we nu een variant noemen. Er zijn in de loop der tijd zeer veel varianten op Sudoku ontwikkeld, en hoewel enkele daarvan een vaste schare liefhebbers hebben verworven, heeft geen van deze varianten de populariteit van de standaard Sudoku kunnen evenaren.
- Variatie in grootte
- De standaard grootte van een Sudoku is 9 bij 9 met blokken van 3 bij 3. Kleinere varianten (subdoku) zijn 4 bij 4 met blokken van 2 bij 2, en 6 bij 6 met blokken van 3 bij 2. Grotere varianten (superdoku) zijn 12 bij 12 met blokken van 4 bij 3, 16 bij 16 met blokken van 4 bij 4 en 25 bij 25 met blokken van 5 bij 5. Voor deze grotere varianten zijn 9 cijfers niet toereikend, zodat er ook gebruik gemaakt wordt van letters in plaats van cijfers. Ook combinaties van letters en cijfers komen hierbij voor. Een bekende variant is hexadoku, waarbij gebruik gemaakt wordt van hexadecimale symbolen, dit wil zeggen van 0 tot en met F. Deze afwijkende formaten kunnen op zich weer de basis vormen voor andere varianten.
- Variatie in de symbolen
- De 9 cijfers in een sudoku kunnen door van alles vervangen worden. Deze varianten veranderen wel het uiterlijk van de puzzel, maar niet de wezenlijke kenmerken. Er zijn varianten bekend met letters, afbeeldingen, abstracte symbolen, kleuren en in stukken geknipte foto's.
- Variatie in de indeling
- Bij de jigsaw of vorm-sudoku zijn de 3x3 blokken vervangen door vlakken met een onregelmatige vorm, die als de stukjes van een legpuzzel in elkaar passen. Elk vlak bestaat uit 9 vakjes.
- De toroidal sudoku gaat nog een stapje verder. Hierbij lopen de extra vlakken over de randen van de puzzel heen, waardoor ze soms uit 2 of meer delen bestaan.
- Aanvullende beperkingen
- Bij een X-sudoku moeten ook de beide diagonalen de cijfers 1 tot en met 9 bevatten. In de argyle sudoku mogen dezelfde cijfers niet meer als eenmaal voorkomen in andere diagonalen.
- De Sudoku die elke week in NRC Handelsblad staat, bevat 4 extra blokken van 3 bij 3 vakjes, waarin de cijfers 1 tot en met 9 moeten voorkomen. Deze variant wordt ook wel windoku genoemd.
- Bij de DG-sudoku moeten alle vakjes die op dezelfde relatieve positie in een 3 bij 3 blok staan de cijfers 1 tot en met 9 bevatten. Een beperkte variant is de center-dot sudoku, waarin dit alleen geldt voor de vakjes in het midden van elk blok.
- Overlappende Sudoku puzzels
- Door verschillende sudoku puzzels gedeeltelijk over elkaar heen te plaatsen ontstaat er een grotere puzzel. Deze zogenaamde gattai puzzels komen voor in diverse vormen, waarbij de samurai met 5 overlappende sudoku's (één centrale en één in elke hoek) de meest bekende vorm is. Er bestaan zeer grote overlappende varianten, de shogun met 11 sudoku's, de sumo met 13 sudoku's en de shaolin met 25 sudoku's.
- Rekenkundige varianten
- Een zeer populaire variant is de Killer Sudoku (ook bekend als Som-Sudoku of samunamupure). Dit is een puzzel waarin elementen van sudoku en kakuro samengevoegd zijn. In plaats van gegeven cijfers bevat de puzzel onregelmatig gevormde gebieden waarvoor de som van de daarin voorkomende cijfers wordt gegeven. Verwant hieraan is de product-sudoku, waar het product van de cijfers wordt gegeven.
- Een som-Sudoku bestaat ook, er staan dan mallen op het vierkant met een getal erin: de som van de cijfers.
- Vorm varianten
- In deze varianten is de puzzel geen vierkant, maar heeft deze een andere vorm. Hierdoor zijn de rijen en kolommen niet meer even lang. De pseudoku Bestaat uit een aantal rijen in aflopende lengte. De hanidoku heeft zeskantige vakjes, waardoor er rijen in 3 richtingen ontstaan.
[bewerk] Sudokuspelcomputer
Vanwege de populariteit van sudoku's zijn sudokuspelcomputers op de markt verschenen. De prijzen van de spelcomputers variëren. De systemen van de spelcomputers verschillen: de een heeft pijltjestoetsen en een numeriek toetsenbord, de ander heeft een PDA-achtig systeem.
