Sudoku

De Viquipèdia
Dreceres ràpides: navegació, cerca
Un trencla-closques del Sudoku (pitgeu sobre la imatge per a conèixer la solució)

Sudoku (japonès: 数独 sūdoku), sovint escrit també Su Doku, és un trencaclosques de col·locació que requereix només paciència i una certa habilitat lògica, si bé alguns trenca-closques poden ser realment difícils de resoldre.

El joc es compon d'una graella de 9×9 cel·les 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.

Orígens[modifica | modifica el codi]

Aquest joc sorgí inicialment 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), però esdevingué popular al Japó el 1986 i aconseguí popularitat internacional el 2005.

Al Japó hi van aparèixer per primer cop l'abril del 1984, en la revista Monthly Nikolist 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 (un editor de trencaclosques) i altres editors usen noms diferents.

Normes[modifica | modifica el codi]

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 cel·les formada per 9 subgraelles de 3×3, anomenades regions. 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 exactament només una vegada.

L'atractiu del trencaclosques recau precisament en la senzillesa de les normes si bé el raonament per a resoldre'ls pot arribar a ser complex. Els sudokus 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 vénen 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ó[modifica | modifica el codi]

L'estratègia per a resoldre un trencaclosques es pot considerar com la combinació de tres processos: escaneig, marcat i anàlisi.

Escaneig[modifica | modifica el codi]

L'escaneig es realitza des del principi i periòdicament, durant tota la resolució. L'escaneig pot haver de ser executat diverses vegades entre períodes d'anàlisi. L'escaneig consta de dues tècniques bàsiques: trama creuada i recompte, que poden usar-se alternativament.

En aquesta jugada, es mostra com per escaneig, en la casella marcada en verd, només hi pot anar un 6.
  • Trama creuada: es tracta de l'escaneig 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 trencaclosques 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 escaneig.

Marcat[modifica | modifica el codi]

L'escaneig 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 majoria troba útil guiar aquesta anàlisi mitjançant el marcat de nombres candidats en les cel·les buides. Hi ha dues notacions populars: subíndexos i punts. En la notació de subíndex, els nombres candidats s'escriuen en petit en les cel·les. El desavantatge és que els trencaclosques 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 avantatge que pot usar-se en el sudoku original. Es requereix 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[modifica | modifica el codi]

Hi ha dues aproximacions principals: eliminació i "i-si".

  • En 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 un nou escaneig (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'esborrat "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 l'aproximació "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 reducció a l'absurd. "Nishio" és una forma limitada d'aquesta aproximació: 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. L'aproximació "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. L'aproximació "i-si" pot ser confusa llevat que siguis 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[modifica | modifica el codi]

Article principal: Sudoku ramificació i poda

El mètode de ramificació i poda permet resoldre el trencaclosques amb una sèrie d'algorismes.[1]

Resolució mitjançant ordinadors[modifica | modifica el codi]

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 sudokus 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ó.

Variants[modifica | modifica el codi]

Sudoku amb subregions de colors.
Exemple de sudoku on les diagonals principals també han de tenir nombres únics.

Els sudokus més comuns (els originals) són els de 9×9 amb regions de 3×3, tot i això hi ha sudokus de mides diferents, de fins a 25×25, alguns dels quals amb noms especials.

En alguns s'ha afegit la regla en què els nombres de les diagonals principals també han de ser únics. Hi ha variants també on algunes cel·les estant ombrejades i hi ha d'haver nombres parells. En algunes sudokus les cel·les tenen diferents colors i a més de complir-se la regla de fila, columna i regió, no hi pot haver cap nombre repetit en les cel·les del mateix color. Hi ha sudokus, com el killer su doku del diari The Times on certs segments han de tenir un resultat mitjançant operacions matemàtiques.

Un trenclaclosques del KenKen.

A més hi ha sudokus irregulars de diferents mides on les regions no són quadrats.

També hi ha sudokus que no tenen regions: només files i columnes. Les mides més coneguts són: 6×6, 9×9, 16×16, 25×25, 30×30, 36×36 i 49×49.

Hi ha versions que inclouen lletres en comptes de nombres, i en alguns casos aquestes lletres formen mots. També és conegut el sidoku on es canvien els nombres per les notes musicals.

També guarda relació amb els sudokus el sudokuto, on dos jugadors van escrivint nombres en una taula fins que un aconsegueix completar una columna, fila o regió amb tots els nombres o s'equivoca en escriure'ls.

El kenken, inventat el 2004 pel professor de matemàtiques japonès Tetsuya Miyamoto, és una variant on es fa servir també el càlcul.

Competicions[modifica | modifica el codi]

La primera competició mundial va tenir lloc a Lucca, Itàlia, del 10 al 12 de març del 2006. La guanyadora va ser Jana Tylova, una noia de 31 anys de la República Txeca. La competició va incloure variants del sudoku; n'hi ha una llista completa aquí Noia 64 mimetypes pdf.pngPDF (anglès).

La The United States Sudoku Association Inc. és una corporació que organitza tornejos arreu dels Estats Units.

Vegeu també[modifica | modifica el codi]

Referències[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Sudoku Modifica l'enllaç a Wikidata
  1. Martí, Narciso; Verdejo, Alberto; Ortega Yolanda. Estructuras de datos y métodos algorítmicos: ejercicios resueltos (en castellà). Madrid: Prentice Hall, 2003.