Sudoku

De Viquip??dia

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

[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

Sudoku resolt. Cada fila columna i regi?? de 3??3, cont?? tots els n??meros del 1 al 9 una sola vegada

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.

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 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

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 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).