miniatura|Un trencla-closques del Sudoku (pitgeu sobre la imatge per a conèixer la solució) Sudoku (japonès: 数独 sūdoku; en traducció directa al català: Xifra soltera), sovint escrit també Su Doku, és un trencaclosques de combinatòria basat en la lògica.
En el sudoku clàssic, l'objectiu és omplir una graella de 9×9 files i columnes subdividida en 9 subgraelles de 3×3 anomenades regions. Donats uns quants números inicials, l'objectiu és col·locar un número de l'1 al 9 en cada cel·la de tal manera que mai coincideixin dos números iguals en cada línia horitzontal, vertical o en cada regió. Els numerals en els sudoku es fan servir només per conveniència, sense que existeixi cap relació aritmètica entre ells. De fet, poden fer-se servir en qualsevol tipus de símbols, lletres, formes, colors… sense alterar-ne el funcionament.
Els diaris francesos van impulsar variacions del sudoku al , i el trencaclosques va aparèixer a partir del 1979 en llibres de trencaclosques sota el nom "Number Place". No obstant, el sudoku modern només va començar a tenir certa popularitat a partir del 1986 quan en va publicar la companyia de trencaclosques japonesa Nikoli amb el nom sudoku.
Orígens El joc va ser inventat pel matemàtic suís Leonhard Euler al , qui va definir el concepte base d'aquests mots encreuats numèrics, en el qual cal omplir una quadrícula de blocs de 9x9 amb nou caselles en cada un en què cap columna contingui el mateix número de l'1 al 9. Però la seva popularitat no esclataria fins que l'editor japonès Maki Kaji, conegut com el “padrí dels sudoku” pel seu paper en la popularització d'aquests trencaclosques numèrics, va emprendre’n la publicació a partir de l'abril del 1984 en una secció de passatemps a la revista Monthly Nikolist, on va popularitzar el nom actual de Sudoku.
A l'època moderna, però, aquest joc va reprendre's com entreteniment abans, a finals dels anys 70 als Estats Units, a la revista publicada a Nova York Math Puzzles and Logic Problems, amb el nom de Number Place.
Quan va aparèixer al Japó el 1984 a la revista Monthly Nikolist ho va fer sota el nom de Suji wa dokushin ni kagiru (数字は独身に限る), que vol dir les xifres han de ser solteres. Més endavant es va abreujar el nom a su doku, literalment xifra soltera.
El 1986 hi van introduir dues modificacions que en van millorar la popularitat: el nombre de xifres donades com a pista era menor o igual a 30, i formaven una composició simètrica respecte al punt central.
Al Japó "Sudoku" és una marca registrada per Nikoli (l'editorial de trencaclosques de Kaji), de manera que altres editors usen noms diferents per al mateix joc.
Normes miniatura|Sudoku resolt. Cada fila, columna i regió de 3×3 caselles, conté tots els números de l'1 al 9 una sola vegada. El trencaclosques és una graella de 9×9 files i columnes formada per 9 subgraelles de 3×3, anomenades regions. A l'inici del joc algunes cel·les contenen ja xifres. L'objectiu és omplir les cel·les buides amb una xifra en cadascuna d'aquestes de tal manera que cada filera, cada columna i cada regió contingui tots els numerals de l'1 al 9 només una vegada.
L'atractiu del trencaclosques recau precisament en la senzillesa de les normes si bé el raonament per resoldre'ls pot arribar a ser complex. Els sudoku es publiquen generalment valorats en termes de dificultat i sovint s'expressa també el temps aproximat de resolució. Generalment es considera que, com més números venen donats ja inicialment, més fàcil és trobar-ne la solució; el contrari no és necessàriament cert, ja que la dificultat d'un sudoku depèn principalment de la dificultat de determinar lògicament els següents números.
Alguns professors recomanen el sudoku com un exercici de raonament lògic.
Mètodes de resolució L'estratègia per a resoldre un trencaclosca es pot considerar com la combinació de tres processos: escanerització, marcatge i anàlisi.
Escanerització L'escanerització es realitza des del principi i periòdicament, durant tota la resolució. L'escanerització pot haver de ser executat diverses vegades entre períodes d'anàlisi. L'escanerització consta de dues tècniques bàsiques: trama creuada i recompte, que poden usar-se alternativament.
miniatura|En aquesta jugada, es mostra com per escanerització, en la casella marcada en verd, només hi pot anar un 6. Trama creuada: es tracta de l'escanerització de files (o columnes) per a identificar quina línia en una regió particular pot contenir un nombre determinat mitjançant un procés d'eliminació. Aquest procés es repeteix amb les columnes (o files). Per obtenir resultats més ràpids, els nombres són escanejats de forma ordenada, segons la seva freqüència d'aparició. És important realitzar aquest procés sistemàticament, comprovant tots els dígits de l'1 al 9.
Recompte de l'1 al 9 per regions, files i columnes per identificar nombres perduts: el recompte basat en l'últim nombre descobert pot augmentar la velocitat de la recerca. També pot ser el cas (és típic en trencaclosques més difícils) que el valor d'una cel·la individual pugui ser determinat mitjançant un recompte invers, això és, escanejant la seva regió, fila o columna per a valors que no poden ser, per a veure quin és el que hi falta.
Els resoledors avançats busquen "contingències" mentre escanegen, això és, fiten la ubicació d'un nombre en una fila, columna o regió, o en dues o tres cel·les. Quan aquestes cel·les descansen totes en la mateixa fila (o columna) i regió, poden usar-se amb un propòsit d'eliminació durant la trama creuada i el recompte. Trencaclosques particularment desafiadors poden requerir el reconeixement de múltiples contingències, potser en múltiples direccions o fins i tot interseccions - relegant la majoria dels resoledors al marcat (com es descriu més avall). Els trencaclosca que poden ser resolts només mitjançant escaneig, sense requerir la detecció de contingències es classifiquen com a "fàcils"; altres de més difícils, per definició, no poden resoldre's únicament mitjançant escanerització.
Marcatge L'escanerització ve a interrompre's quan no poden descobrir-se nous nombres. En aquest punt és necessari centrar-se en alguna anàlisi lògica. La major part troba útil guiar aquesta anàlisi mitjançant el marcat de nombres candidats en les cel·les buides. Hi ha dues notacions populars: subíndexs i punts. En la notació de subíndex, els nombres candidats s'escriuen en petit en les cel·les. El desavantatge és que els trencaclosca originals són publicats en periòdics que habitualment no deixen massa espai per acomodar-hi gaires dígits. Si s'usa aquesta notació, els resoledors es preparen, sovint, una còpia més gran del sudoku i empren un llapis esmolat. La segona mena de notació és un patró de punts amb un punt en el cantó superior esquerra representant un 1 i un punt en el cantó inferior dreta representant un 9. Aquesta notació té com a avantatge que pot usar-se en el sudoku original. Cal destresa per a l'emplaçament dels punts, perquè punts lleugerament desplaçats o fins i tot marques involuntàries duen, inevitablement, a confusió i no són fàcils d'esborrar sense afegir encara més confusió.
Anàlisi Hi ha dos mètodes principals:
En el mètode d'eliminació, el progrés es realitza mitjançant la successiva eliminació de nombres candidats per a una o més cel·les, fins a deixar només una elecció. Després d'assolir cada resposta, cal fer una nova escanerització (habitualment comprovant l'efecte de l'últim nombre). Hi ha una sèrie de tàctiques d'eliminació. Una de les més comunes és l'esborrament "del candidat no coincident". Les cel·les amb idèntica configuració de nombres candidats es diu que coincideixen si la quantitat de nombres candidats en cadascuna és igual al nombre de cel·les que els contenen. Per exemple, es diu que cel·les coincideixen amb una particular fila, columna o regió si dues cel·les contenen el mateix parell de nombres candidats (p,q) i no altres, o si tres cel·les contenen el mateix triplet de nombres candidats (p,q,r) i no altres. Aquestes són, essencialment, contingències coincidents. Aquests nombres (p,q,r) que apareixen com a candidats en qualsevol lloc en la mateixa fila, columna o regió en cel·les no coincidents, poden ser esborrats.
En el mètode "i-si", se selecciona una cel·la amb només dos nombres candidats i es realitza una conjectura. Les etapes de dalt es repeteixen llevat que es trobi una duplicació; en aquest cas, el candidat alternatiu és la solució. En termes lògics aquest mètode es coneix com a reducció a l'absurd. "Nishio" és una forma limitada d'aquest mètode: per a cada candidat per a una cel·la, la qüestió que es planteja: entrarà un nombre particular d'una configuració en un altre emplaçament? Si la resposta és sí, aleshores aquest candidat pot ser eliminat. La tècnica "i-si" requereix un llapis i una goma. Aquesta aproximació pot ser desaprovada per puristes lògics per massa assaig i error però pot arribar a solucions de forma clara i ràpida .
Idealment, es necessita trobar una combinació de tècniques que evitin algun dels inconvenients dels elements de dalt. El recompte de regions, files i columnes pot resultar avorrit. Escriure nombres candidats en cel·les buides pot consumir massa temps. El plantejament "i-si" pot ser confús llevat que hom sia ben organitzat. El quid de la qüestió és trobar una tècnica que minimitzi el recompte, el marcat i l'esborrat.
Resolució per ramificació i poda El mètode de ramificació i poda permet resoldre el trencaclosques amb una sèrie d'algorismes.
Resolució mitjançant ordinadors Per a un programador informàtic és relativament senzill construir una cerca amb el mètode de Sudoku backtracking o "tornada enrere". El mecanisme consisteix a assignar un valor (l'1 o el més proper, per exemple) a la primera cel·la disponible (la superior esquerra, generalment) i llavors continuar assignant el següent valor disponible (seria el 2) a la següent cel·la possible. Això continuaria fins que descobrís una duplicació, en aquest cas, el següent valor alternatiu es col·locaria al primer camp alterat. En el cas que cap valor pogués complís la restricció es retrocediria a la casella anterior i es provarien altres nombres.
Encara que lluny de l'eficiència computacional, aquest mètode trobarà la solució amb bastant més temps que el següent mètode: el programa podria deixar una marca de valors potencials per a les cel·les, eliminant valors impossibles fins que només quedés un valor per una cel·la determinada. Llavors s'ompliria aquesta cel·la i s'utilitzaria aquesta informació per a més eliminacions i així successivament fins al final. Això emularia més exactament el que faria un jugador humà.
Codificar la cerca per a impossibilitats basades en contingències, i fins i tot múltiples contingències (com seria requerit per sudoku més difícils) és bastant complex de fer a mà. De totes maneres, aquestes complicacions són innecessàries si tot el que el programador vol fer és trobar la solució eficientment. Una forma més eficient de construir solucions comporta eines de programació avançada.
Alguns d'aquests programes construïts així, que emulen la resolució humana, permeten estimar la dificultat que tindrà la persona per trobar la solució.
Construcció