Sudoku

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Lege puzzel
Rijen, kolommen, en blokken

Een sudoku is een puzzel bestaande uit negen bij negen vakjes die gegroepeerd zijn als negen blokken van drie bij drie vakjes. In de vakjes moeten de cijfers 1 tot en met 9 Ingevuld worden op zo'n manier dat in elke horizontale lijn én in elke verticale kolom en in elk van de negen blokjes de cijfers 1 tot en met 9 één keer voorkomen. In een aantal vakjes zijn de cijfers al ingevuld. Een sudoku is dus een bijzonder geval van een Latijns vierkant.

Ontstaan[bewerken]

De puzzel is ontworpen door Howard Garns, een gepensioneerde architect en freelance puzzelmaker, en voor het eerst gepubliceerd in 1979 onder de naam Number Place. De puzzel werd in 1984 door Nikoli in Japan geïntroduceerd, waar hij ook de naam sudoku (samenvoeging van suuji wa dokushin ni kagiru, wat vertaald kan worden als: getallen blijven alleen ('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 doordat 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.

Moeilijkheidsgraad[bewerken]

Voor het oplossen van een sudoku zijn concentratie en systematisch denken het belangrijkste. Wiskundige kennis is niet vereist, aangezien de 9 symbolen hier geen betekenis hebben, behalve dat ze verschillend zijn; in plaats van cijfers had men ook andere symbolen kunnen gebruiken.

De moeilijkheidsgraad van een opgave is in tegenstelling tot wat vaak gezegd wordt niet echt afhankelijk van het aantal reeds ingevulde cijfers.[bron?] 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.

Het produceren van een sudoku-opgave[bewerken]

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 op te lossen 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 incidenteel 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.

Oplosstrategie 1[bewerken]

We nemen als voorbeeld de lege puzzel van hierboven.

Stap 1

Stap 1[bewerken]

  • 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.
Stap 2

Stap 2[bewerken]

  • Omdat nu alleen de 6 nog ontbreekt in deze rij, kun je die zo invullen.
Stap 3

Stap 3[bewerken]

  • 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 linksonder) staan, omdat in die rijen al een 7 staat.
  • In de onderste rij is maar een plaats vrij en daar komt de 7 .
Stap 4

Stap 4[bewerken]

  • 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.
Stap 5

Stap 5[bewerken]

  • Alleen de 5 in het blok linksonder ontbreekt nog, deze moet dus in het vakje rechtsmidden.

Oplosstrategie 2[bewerken]

Als de opgaven moeilijker zijn, zijn er meestal geen rijen die al bijna compleet ingevuld zijn. Dan is bijvoorbeeld deze strategie handig:

Stap 1

Stap 1[bewerken]

Zoek in een rij van drie blokken (horizontaal of verticaal) twee blokken met hetzelfde symbool. Bijvoorbeeld de 4-en in de rechter verticale rij.

Stap 2

Stap 2[bewerken]

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.

Vervolg

Vervolg[bewerken]

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.

En verder[bewerken]

De rest van de puzzel kan men zelf oplossen. Nog enkele tips:

  • De gebruiker dient zich op één cijfer te concentreren, bijvoorbeeld een cijfer dat al vaak voorkomt.
  • Er dient met een blok, rij of kolom te worden begonnen die al bijna vol is.
  • Strategieën dienen blijven te worden herhaald. Elke keer als er een cijfer is ingevuld blijven er minder mogelijkheden over.
  • Ook kan de gebruiker aantekeningen maken: de mogelijke getallen voor een hokje klein erin zetten. Zodra ergens anders in de kolom of rij een van deze getallen wordt ingevuld, zijn ze in dat hokje weg te strepen. Zo blijft er uiteindelijk één mogelijkheid over.

Bekijk de oplossing

Oplossingsschema[bewerken]

Een schema is een additoneel hulpmiddel bij de oplossing van een Sudokupuzzel. Er zijn negen vakjes in ieder waarvan de cijfers 1 tot en met 9 moeten worden ingevuld, op zodanige wijze dat in elke horizontale rij en verticale kolom ook alle cijfers 1 t/m 9 verschijnen. Bijvoorbeeld:

1 2 3
4 5 6
7 8 9
4 5 6
7 8 9
1 2 3
7 8 9
1 2 3
4 5 6
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .


Voor de oplossing kan gebruikgemaakt worden van een computer als aan de puzzel enige kolommen worden toegevoegd. Dit is hieronder uitgewerkt voor de bovenste drie vakken en de eerste regels van het daaronder gelegen vakkendrietal.

xxx ontbreekt A .... B .... C ontbreekt D .... E .... F ontbreekt G .... H .... I.
. 123 456 789 123 456 789 123 456 789
niet . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
xxx . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
xxx . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
xxx . . . . . . . . . . . . . . . . . .
. ontbreekt . . . . . ontbreekt . . . . . ontbreekt . . . . .
. 123 456 789 123 . 456 . 789 123 456 789

Het model kan als volgt worden gebruikt:

  1. Plaats de reeds ingevulde cijfers op de kruispunten van de rijen xxx met de kolommen A tot en met I.
  2. Markeer het veld linksboven de ingevulde cijfers met een B.
  3. Streep in de velden ontbreekt de in het daaronderliggende vak bekende cijfers door.
  4. Breng de niet doorgestreepte cijfers over naar alle velden van het vak waarin nog een cijfer moet worden ingevuld.
  5. Plaats naast en onder NIET de in de betreffende rij of kolom reeds ingevulde cijfers.
  6. Elimineer deze cijfers horizontaal en verticaal, maar niet uit de onder 1 genoemde rijen en kolommen.
  7. Blijft er ergens een eenzaam cijfer staan, breng dat dan over naar het onder 1 bedoelde vakje rechts onder.
  8. Elimineer dat cijfer horizontaal en verticaal.
  9. Als laatste stap kunnen de ontbrekende cijfers worden bepaald, zodanig dat men niet in conflict komt met de opzet van de puzzel.

Varianten[bewerken]

X-sudoku: ook de diagonalen bevatten de cijfers 1 t/m 9

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 (hexadoku), 25 bij 25 met blokken van 5 bij 5 (alfadoku) en 36 bij 36 met blokken van 6 bij 6 (alfanumski). Voor deze grotere varianten zijn 9 cijfers niet toereikend, zodat er ook gebruikgemaakt wordt van letters in plaats van cijfers. Ook combinaties van letters en cijfers komen hierbij voor. Een bekende variant is hexadoku, waarbij gebruikgemaakt wordt van hexadecimale symbolen, dit wil zeggen van 0 tot en met 9 en A 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 (ook Chaos 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 dan eenmaal voorkomen in andere diagonalen.
Aan de S-doku van Jelmer Steenhuis die elke week in Vrij Nederland te vinden is zijn nog meer extra voorwaarden verbonden. Elke kolom en elke rij van vetomrande vierkanten bevat negen gekleurde vakjes van de grote S-vorm. Ook in die zes groepen van negen vakjes moeten de cijfers 1 t/m 9 precies één keer voorkomen.
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.
Bij de SymboSudoku zijn de cijfers vervangen door symbolen (bv. cirkels, vierkantjes, driehoekjes, plustekens, mintekens, smileys, ...). De regels zijn dezelfde als voor de gewone sudoku.
  • Overlappende Sudoku puzzels
Door verschillende sudokupuzzels 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. In de Volkskrant verschijnt regelmatig een twinsudoku, waarbij twee sudoku's een overlappende kolom van 3 bij 3 vakjes hebben.
  • 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.
  • 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.
Tredoku: bij deze variant zijn de 3x3 vakjes in 3D geplaatst op deze manier worden de lijnen van 9 vakjes dikwijls gebogen.
  • Minder beperkingen
Horizontaal-verticaal: deze sudoku heeft geen blokken.

Sudokuspelcomputer[bewerken]

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.

Trivia[bewerken]

  • Een sudoku hoeft niet per se cijfers te bevatten. De puzzel kan ook met letters worden gedaan. In dat geval spreekt men van een wordoku. De gevraagde oplossing van een wordoku is soms een bestaand woord van 9 (verschillende) letters.

Zie ook[bewerken]