Een sudoku (Japans 数独, sūdoku, afkorting voor 数字は独身に限る, sūji wa dokushin ni kagiru, isoleer de getallen) 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 en 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.
De puzzel is ontworpen door de Amerikaan 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 Maki Kaji van het bedrijf Nikoli in Japan geïntroduceerd, waar deze de sudoku werd genoemd, een samenvoeging van suuji wa dokushin ni kagiru, wat vertaald kan worden als getallen blijven alleen (su betekent getal, doku betekent onafhankelijk, ongetrouwd). 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 waarmee een nieuwe rage was geboren.
In de zomer van 2005 werd de puzzel ook geïntroduceerd in Nederland en België 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 in Amsterdam. Delia Keetman-Verhoef uit Heerhugowaard werd eerste.
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 hadden ook andere symbolen gebruikt kunnen worden. De moeilijkheidsgraad van een opgave is niet afhankelijk van het aantal al 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. In januari 2012 werd bewezen dat er minstens 17 gegevens moeten zijn om een unieke oplossing te hebben.[1][2]
Bij het maken van een sudoku met een computer moet het computerprogramma eerst een oplossing genereren door middel van willekeurige verdelingen van de 9 cijfers en toetsing van de rij-kolom-blok-compatibiliteit. Zodra een nieuwe oplossing is gevonden, moet deze 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.
Als de opgaven moeilijker zijn, zijn er meestal geen rijen die al bijna compleet ingevuld zijn. Dan is bijvoorbeeld deze strategie handig:
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.
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.
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.
Concentreer telkens op één cijfer, om te beginnen een cijfer dat al vaak voorkomt.
Begin met een blok, rij of kolom dat/die al grotendeels ingevuld is.
Herhaal een bepaalde strategie na het invullen van een cijfer; er blijven immers minder mogelijkheden over.
Noteer per vakje de nog mogelijke cijfers, bijvoorbeeld klein in een hoek van het vakje. Zodra elders in het betreffende blok, de kolom of de rij een van die cijfers wordt ingevuld, kan deze in dat vakje weggestreept worden. Zo blijft er uiteindelijk één mogelijkheid over.
X-sudoku: ook de diagonalen bevatten de cijfers 1 t/m 9
Toen de Number Place-puzzels voor het eerst in Dells 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 meestal niet de wezenlijke kenmerken. Er zijn varianten bekend met letters (waarbij soms een bestaand woord van 9 verschillende letters als oplossing wordt gevraagd), afbeeldingen, abstracte symbolen, kleuren en in stukken geknipte foto's.
Bij de kaodokuVoorbeeld van een kaodoku: in elke cel hoort een smiley met een vorm én een mond. is er wel een wezenlijk verschil: deze gebruikt smiley-symbolen met twee afzonderlijke kenmerken, de vorm (cirkel/vierkant/driehoek) en de mond (blij/droevig/neutraal), waarbij in veel cellen slechts een van deze kenmerken gegeven wordt. Moeilijke kaodokus bevatten zelfs geen enkel volledig symbool, zodat men verplicht wordt redeneringen op te bouwen met deze "halve" symbolen: men kan bijvoorbeeld een droevig mondje invullen in het lege vakje op het kruispunt van een rij met drie neutrale mondjes en een kolom met drie lachende mondjes, ook al weet men nog niet wat de vorm is. Het kaodoku-concept komt nog beter tot zijn recht wanneer het gecombineerd wordt met andere variaties zoals chaotische zones, diagonalen of andere beperkingen die nog complexere redeneringen mogelijk maken.
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 windoku, Hyper Sudoku of NRC Sudoku van Peter Ritmeester die sinds oktober 2005 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. Ritmeester publiceert zijn variant sinds april 2007 ook in The International New York Times (voorheen International Herald Tribune). In boekvorm verscheen hij voor het eerst in Will Shortz's Favorite Sudoku Variations (februari 2006). In dit boek werd de variant voor het eerst hyper sudoku genoemd. Er bestaan ook puzzelboekjes met alleen windoku's
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 sudokupuzzels gedeeltelijk over elkaar heen te plaatsen ontstaat er een grotere puzzel. Deze 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.
Vormvarianten
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.
Suguru: deze variant bestaat uit een diagram dat is opgedeeld in blokken van verschillende formaten.
Minder beperkingen
Horizontaal-verticaal: deze sudoku heeft geen blokken.
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. Daarnaast bestaan er sudoku-apps voor smartphone en tablet.
