Sudoku
De Viquipèdia
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 composa 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 s'usen només per conveniència, sense que existeixi cap relació aritmètica entre ells. De fet, poden usar-se qualsevol tipus de símbols, lletres, formes, colors... sense alterar-ne el funcionament.
Taula de continguts |
[edita] Orígens
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 sudoku, 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 el punt central.
Al Japó sudoku és una marca registrada per Nikoli (un editor de trencaclosques) i altres editors usen noms diferents.
[edita] Normes
El trencaclosques és per 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 ser complex. Els sudokus es publiquen generalment valorats en termes de dificultat i sovint s'expressa també el temps aproximat de solució. Generalment es considera que, com més números venen donats ja inicialment, més fàcil és 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.
[edita] Mètodes de Resolució
L'estratègia per a resoldre un trencaclosques es pot considerar com la combinació de tres processos: escaneig, marcat i anàlisi.
[edita] Escaneig
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àlisis. L'escaneig consta de dues tècniques bàsiques: trama creuada i recompte, que poden usar-se alternativament.
- 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 llavors amb les columnes (o files). Per a 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 del 1 al 9.
- Recompte 1-9 per regions, files i columnes per a 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 puzles 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 qual 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 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. Puzles 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 baix). Els puzles que poden ser resolts només mitjançant escaneig, sense requerir la detecció de contingències es classifiquen com puzles “fàcils”; altres puzles més difícils, per definició, no poden resoldre's únicament mitjançant escaneig.
[edita] Marcat
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 puzles originals són publicats en periòdics que habitualment no deixen massa espai per a acomodar més d'uns pocs dígits. Si s'usa aquesta notació, els resoledors creen, sovint, una còpia més gran del sudoku i empren un llapis afilat. La segona 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 desplaçats o marques distretes duen, inevitablement, a confusió i no són fàcils d'esborrar sense afegir més confusió.
[edita] Anàlisi
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 son, essencialment, contingències coincidents. Aquests nombres (p,q,r) que apareixen com 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 altre emplaçament? Si la resposta és sí, llavors 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 clara i ràpidament.
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 bé organitzat. El quid de la qüestió és trobar una tècnica que minimitzi el recompte, el marcat i l'esborrat.
[edita] Resolució mitjançant ordinadors
Per a un programador informàtic és relativament senzill construir una cerca amb el mètode de 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 esquerre, 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 de 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 del 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 el final. Això emularia més exactament el que faria un humà.
Codificar la cerca per a impossibilitats basades en contingències i inclòs múltiples contingències (com seria demanat per sudokus més difícils) és bastant complexe de construir a mà. De totes maneres, aquesta 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ó.
[edita] Variants
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 que 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ó en les cel·les del mateix color no hi pot haver cap nombre repetit. 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.
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.
[edita] Competicions
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, hi ha una llista completa aquí (
PDF) (anglès).
La The United States Sudoku Association Inc és una corporació que organitza tornejos arreu dels Estats Units.
