Sudoku

De la Wikipedia, enciclopedia liberă

Sudoku, pronunţat [sudoku], din japoneză 数, sû, cifră, şi 独, doku, unică, este un joc în formă de grilă inventat în 1979 şi inspirat de pătratul latin şi de problema celor 36 ofiţeri a lui Leonhard Euler. Scopul jocului este de a umple această grilă cu cifrele de la 1 la 9 respectând anumite condiţii, cu unele cifre fiind de la început dispuse în grilă.

[modifică] Prezentare

O grilă 9×9 de Sudoku (apăsaţi pe imagine pentru a vedea soluţia, care apare mai jos)

Grila jocului este un pătrat de nouă pe nouă căsuţe, subdivizat în tot atâtea pătrate identice, numite regiuni (vedeţi figura). Regula jocului este simplă: fiecare rând, coloană sau regiune nu trebuie să conţină decât o dată cifrele de la unu la nouă. Formulat altfel, fiecare ansamblu trebuie să conţină cifrele de la unu la nouă o singură dată.

Cifrele nu reprezintă decât o convenţie, relaţiile aritmetice între ele nefiind de nici un folos. Orice ansamblu de simboluri distincte: litere, forme, culori, pot fi folosite fără a se modifica regulile jocului. Dell Magazine, primul care a publicat grile, a folosit cifre în publicaţiile sale. Dimpotrivă, Scramblets, de la Penny Press, şi Sudoku Word, de Knight Features Syndicate, folosesc amândouă litere.

Interesul jocului consistă în simplitatea regulilor sale şi în complexitatea soluţiilor sale. Grilele publicate au de obicei un nivel de dificultate indicat, ba chiar editorul poate să şi indice un timp de rezolvare probabil. Cu toate că, în general, grilele ce conţin mai multe cifre completate sunt mai uşoare, inversul nu este în totdeauna adevărat. Dificultatea veritabilă a jocului rămâne totuşi în a găsi suita exactă a cifrelor rămase.

Acest joc a inspirat deja mai multe versiuni electronice care aduc un interes diferit rezolvării grilelor Sudoku. Forma sa de tip grilă şi folosirea lui într-un scop ludic îl aduc mai aproape de alte jocuri publicate în ziare, cum ar fi careurile şi problemele de şah.

Profesorii recomandă practicarea jocului Sudoku ca antrenament pentru gândirea logică. Nivelul de dificultate poate în acest caz să fie adaptat publicului.

Grilele sunt publicate în ziare, dar pot fi şi generate cu ajutorul unui computer.

[modifică] Istoric

[modifică] Problema ofiţerilor

Problema celor 36 de ofiţeri: un pătrat greco-latin de ordin 6 este imposibil de rezolvat

În 1782, mathematicianul elveţian Leonhard Euler îşi imaginează următoarea problemă într-o grilă. Unii atribuie paternitatea Sudokului elveţianului, cu atât mai mult cu cât munca lui Euler consista în studiul pătratelor latine şi teoria graficelor.

Problema ofiţerilor se poate enunţa astfel: fie şase regimente diferite, fiecare regiment posedând şase ofiţeri de grade diferite. Se cere să se plaseze cei 36 ofiţeri într-o grilă de 6 x 6, fiecare ofiţer ocupând câte căsuţă, în aşa fel că fiecare rând şi fiecare coloană să conţină toate gradele şi toate regimentele.

"Deşi, după tot efortul pe care l-am dat pentru rezolvarea acestei probleme, am fost obligaţi să recunoaştem că un astfel de aranjament este absolut imposibil, deşi nu putem să dăm o demonstraţie riguroasă"

În 1901, francezul Gaston Tarry demonstrează imposibilitatea rezultatului datorită unei căutări extensive a tuturor cazurilor şi prin încrucişarea rezultatelor.

Legătura între Sudoku şi problema celor 36 de ofiţeri este condiţia care împiedică repetiţia unui acelaşi element în grilă, ajungându-se în final tot la un joc care se foloseşte de principiul pătratului latin (combinarea a două pătrate latine în cazul pătratului greco-latin, pătrat latin subdivizat în mai multe regiuni în cazul Sudoku).

[modifică] Versiunea modernă a Sudokului

În 1979, un jurnalist liber specializat în jocurile de tip enigmă, Howard Garns, creează primul joc. Dell Magazines îl introduce în acelaşi an într-o publicaţie destinată pieţei new-yorkeze, Dell Pencil Puzzles and Word Games, sub numele de Number Place. Nikoli îl introduce în Japonia în aprilie 1984 în magazinul Monthly Nikolist şi îl numeşte Sūji wa dokushin ni kagiru (数字は独身に限る, care se poate traduce prin "cifra trebuie să fie unică" sau "apare o singură dată"; 独身 semnifică în traducere "singur" sau "celibatar"). Mai târziu, numele se schimbă şi devine Sudoku (数独), respectând aşa tradiţia de a forma un cuvânt mai scurt luând scrierea kanji a parafrazei.

În 1986, Nikoli introduce două noutăţi care vor face jocul popular: numărul căsuţelor descoperite este mai mare de 30 şi grilele sunt simetrice, adică sunt simetric distribuite în jurul centrului grilei. Astăzi, majoritatea ziarelor importante din Japonia, ca de exemplu Asahi Shimbun, publică acest joc. În Japonia, Nikoli este în continuare proprietarul numelui Sudoku; concurenţii săi folosesc un alt nume.

În 1989, Loadstar şi Softdisk publică DigitHunt pentru Commodore 64, probabil prima aplicaţie pentru computer capabilă de a genera grile Sudoku. Mai există una, Enterprise, care continuă să folosească acest nume (en www.coregames.com).

În 1995, Yoshimitsu Kanai publică un generator software sub numele de Single Number (traducerea în engleză a Sudoku), pentru Macintosh, în japoneză şi în engleză (pentru mai multe detalii, vedeţi en [1]) şi, în 1996, publică versiunea pentru Palm (pentru mai multe detalii, vedeţi en [2]).

În 2005, Dell Magazines publică două magazine dedicate Sudokurilor: Original Sudoku şi Extreme Sudoku. Mai mult, Kappa Publishing Group reia grilele Nikoli în GAMES Magazine sub numele Squared Away. Ziarele New York Post, USA Today şi San Francisco Chronicle publică şi ele acest joc. Grile apar în anumite antologii de jocuri, ca şi The Giant 1001 Puzzle Book (sub numele Nine Numbers).

În iulie 2005 Sudoku ajunge în Franţa, publicat de Sport cérébral, editor specializat în jocurile de gândire. Primul număr se va vinde într-un total de 20.000 de exemplare, adică de două ori mai mult decât tirajul vândut de obicei cu ocazia publicării unui nou joc, un adevărat record conform declaraţiei lui Xavier de Bure, directorul general al editurii. Le Figaro publică primele grile cotidiene de la începutul lui iulie, urmat în cursul verii 2005 de Libération, La Provence, Nice Matin, 20 Minutes, Métro şi Le Monde. Magazinul 1, 2, 3... Sudoku scoate primul său număr în noiembrie 2005.

Fenomenul Sudoku a prins şi în Elveţia, Wayne Gould aprovizionând grile cotidianului francofon Le Matin care a vândut în 2005 150 000 cărţi de sudoku şi se gândeşte să producă o emisiune televizată pe această temă. Le Temps, alt cotidian elveţian publică grile de Sudoku din septembrie.

Se pare că japonezii au făcut jocul Sudoku pentru că alfabetul lor avea prea multe simboluri pentru a putea produce careuri la scară mare (vedeţi fr [3]).

[modifică] Popularitatea în mass-media

Din 1997, Wayne Gould, un judecător Neo-Zeelandez din Hong Kong, ieşit la pensie, este intrigat de o grilă parţial completată într-o librărie japoneză. Timp de şase ani, compune o aplicaţie care generează automat aceste grile. Ştiind că ziarele britanice publică careuri şi alte jocuri similare de mult timp, propune Sudoku ziarului The Times, care publică pentru prima oară o grilă pe 12 noiembrie 2004.

Trei zile mai târziu , The Daily Mail publică o grilă sub numele Codenumber. The Daily Telegraph introduce prima sa grilă pe 19 ianuarie 2005, urmat de alte publicaţii al Telegraph Group. Pe 20 mai 2005, Daily Telegraph în Sydney publică prima oară o grilă.

Începând cu data de 23 februarie 2005, Daily Telegraph începe publicarea zilnică a grilelor Sudoku, promovându-l chiar pe prima pagină, celelalte ziare britanice încep şi ele să-i acorde atenţie. Daily Telegraph a decis să continue campania sa de promovare doar în momentul în care a realizat că vânzările se măreau pur şi simplu datorită prezenţa grilei Sudoku. The Times era mai degrabă discret faţă de imensa popularitate care înconjura concursul său de Sudoku. Prevăzuse deja să profite de avansul obţinut prin publicarea unei prime cărţi despre Sudoku.

În aprilie şi în mai 2005, jocul a devenit atât de popular încât mai multe ziare naţionale îl publică în mod regulat. Printre acestea, se numără The Independent, The Guardian, The Sun (intitulat Sun Doku) şi The Daily Mirror. Atunci când cuvântul Sudoku devine popular în Anglia, Daily Mail îl adoptă în locul numelui Codenumber. De atunci, ziarele s-au întrecut unele pe altele în a-şi promova grilele proprii. The Times şi Daily Mail afirmă că au fost primele care au publicat o grilă de Sudoku, pe când The Guardian afirmă, ironic, că grilele construite manual, furnizate de Nikoli, produc o mai bună experienţă pentru jucători decât grilele generate de un software.

Subita popularitate a jocului în Anglia a atras multe comentarii în mass-media (vedeţi Sources dedesubt) şi parodii care au urmat (de exemplu, secţia G2 a ziarului The Guardian' se anunţă ca primul supliment cu o grilă pe pagină.). Sudoku s-a aflat în atenţia opiniei publice imediat după alegerile în 2005 în Anglia, incitând câţiva comentatori să declare că acesta împlinea o nevoie în electoratul politic. O altă explicaţie sugerează că atrage şi reţine atenţia cititorilor, mai mulţi simţindu-se din ce în ce mai satisfăcuţi pe măsură ce descoperă soluţia. The Times estimează că cititorii apreciază atât grilele uşoare cât şi grilele dificile. În consecinţă, publică amândouă tipurile unele lângă altele începând cu 20 iunie 2005.

Imagine:SudokuLive.jpg

Prima emisiune la televizor care pune în joc Sudoku, pe întâi iulie 2005, pe Sky One

Televiziunea britanică s-a grăbit să profite de această popularitate, Sky One difuzând prima emisiune despre Sudoku, Sudoku Live, pe 1 iulie 2005, prezentată de către matematicianul Carol Vorderman. Nouă echipe de nouă jucători, printre care se află şi o vedetă, fiecare echipă reprezentând câte o regiune geografică, încearcă să completeze câte o grilă Sudoku. Fiecare jucător are în mână un aparat care îi permite să preia o cifră din una din cele patre celule de care este responsabil. Există posibilitatea schimbului de cifre cu ceilalţi membri din echipă, dar lipsind o anumită familiaritate, concurenţii nu o fac. La fel, publicul din faţa televizoarelor participă în paralel la o competiţie interactivă. Sky One a încercat să creeze un Sudoku gigant pentru emisiunea sa, prin intermediul unei enorme grile cu latura de 84 (en www.skyone.co.uk). Aceasta însă avea 1.905 rezolvări posibile diferite.

Această bruscă crştere de popularitate în ziarele britanice şi internaţionale face ca Sudoku să fie considerat ca "Cubul Rubik al celui de-al XXI-lea secol" (traducerea liberă a "the Rubik's cube of the 21st century"). Spre exemplu, Wayne Gould furniza la sfârşitul lui 2005 grile pentru aproximativ 70 cotidiane în 27 de ţări.

Pe 28 noiembrie 2005 , Televiziunea elveţiană din zona francofonă lansa o emisiune televizată cotidiană, Su/do/ku, unde doi candidaţi se întrec timp de 5 zile, în fiecare zi 3 reprize a 8 minute.

Se organizează campionate naţionale, ca de exemplu primul Campionat al Franţei de Sudoku (Paris, 18 decembrie 2005) câştigat de Juliette Thery, 19 ani. Această competiţie organizată de Sport Cérébral recompensează cel mai bun jucator al anului.

[modifică] Variante

Un Sudoku nonomino

Un Sudoku pe jumătatea suprafeţei unui cub; fiecare "rând/coloană" are două feţe (Sursă: Prisana)

Chiar dacă grilele clasice sunt cele mai obişnuite, există mai multe variante:

grile de 4×4 care conţin regiuni de 2×2 (în general pentru copii)
grile de 5×5 care conţin regiuni în formă de pentamino şi care au fost publicate sub numele de Logi-5
grile de 6×6 care conţin regiuni de 2×3 (propusă la Campionatului Mondial de Puzzle)
grile de 7×7 cu şase regiuni în formă de hexamino şi o regiune despărţită (propusă la Campionatului Mondial de Puzzle)
grile de 9×9 cu regiuni în formă de polyomino
grile de 16×16 cu regiuni de 4×4 (numite Number Place Challenger şi publicate de Dell, sau numite uneori Super Sudoku)
grile de 25×25 cu regiuni de 5×5 (numite Sudoku the Giant şi publicate de Nikoli)
Există o variantă care în plus impune ca cifrele din diagonalele principale să fie unice. Number Place Challenger, menţionat anterior, şi Sudoku X din Daily Mail, o grilă de 6×6, aparţin acestei categorii
grile de 8×8 conţinând regiuni de 2×4 şi 4×2, şi unde rândurile, coloanele şi diagonalele principale conţin o cifră unică
O meta-grilă compusă din cinci grile de 9×9 în quincunx care se încalecă la colţuri este publicată în Japonia sub numele de Gattai 5 (care înseamnă "cinci fuzionaţi") sau Samuraï. În ziarul The Times, această formă est numită Samurai Su Doku (pentru mai multe detalii , vedeţi en [4]).
Grile cu regiuni rectangulare: dacă o regiune este de dimensiunile LiniixColoane căsuţe, grila globală se descompune în ColoanexLinii regiuni ; valorile urmând a fi completate sunt cuprinse în intervalul de la 1 la ColoanexLinii
Dion Church a creat o grilă 3D, pe care Daily Telegraph a publicat-o în mai 2005

Au fost publicate de asemenea, variante alfabetice, care folosesc litere în loc de cifre. The Guardian le numeşte Godoku şi le descrie ca fiind diabolice. Knight Features preferă numele de Sudoku Word (pentru mai multe detalii, vedeţi en [5]). en Wordoku al lui Top Notch arată literele, în dezordine, ale unui cuvânt care pleacă de la colţul stânga sus şi ajunge în colţul dreapta jos. Un jucător având o bună cultură poate să îl găsească şi să îşi folosească descoperirea pentru rezolvarea Sudokului.

en Code Doku conceput de Steve Schaefer conţine o frază completă, pe când en Super Wordoku al lui Top Notch conţine două cuvinte de nouă litere, fiecare găsindu-se pe una din diagonalele principale. Aceste jocuri nu sunt considerate de către pasionaţi ca fiind adevărate, pentru că logica nu este suficientă pentru a le rezolva, chiar dacă au o soluţie unică. Top Notch affirmă că aceste jocuri sunt concepute de o aşa manieră încât să împiedice soluţiile generate de către programe de rezolvare automată.

În Japonia, sunt publicate alte variante. Iată o listă incompletă:

Grile conectate secvenţial: mai multe grile de 9×9 sunt rezolvate consecutiv, dar doar prima are destule căsuţe precompletate care să permită să fie rezolvată logic. O dată această primă grilă rezolvată, anumite cifre sunt copiate în următoarea. Această formulă impune jucătorului să facă treacă des de la o grilă parţial rezolvată la alta.
Grile foarte mari care consistă în mai multe grile (de obicei de 9×9) care sunt parţial suprapuse. Sunt des întâlnite grilele compuse din 20 până la 50. Mărimea regiunilor care se suprapun parţial variază (două grile de 9×9 pot să aibă în comun 9, 18 sau 36 celule). Adesea, nici o căsuţă nu este precompletată în aceste regiuni.
Grile obişnuite unde o cifră este membră a patru grupuri, în loc de trei obişnuite (rânduri, coloane şi regiuni): cifrele situate pe aceleaşi poziţii relative într-o regiune nu trebuie să corespundă. Aceste grile sunt de obicei imprimate în culoare, fiecare grup despărţit împărţind o culoare pentru a facilita lectura.

Trusa de jocuri pentru a participa la Campionatul Mondial de Puzzle în 2005 conţine o variantă intitulată Digital Number Place: în loc să conţină căsuţe precompletate, majoritatea celulelor conţin o cifră parţial desenată care împrumută grafia afişajului cu şapte segmente.

Pe 31 august 2005, The Times a început publicarea a lui Killer Su Doku, numit şi Samunamupure (care înseamnă "loc de sumare"), care indică suma celulelor regrupate, ceea ce adaugă un supliment de dificultate în căutarea soluţiei, cu tot că poate să şi ajute la rezolvare. Toate celelalte reguli de până acum se aplică, de asemenea.

Majoritatea ziarelor propun astăzi o grilă Sudoku în pagina lor de jocuri.

[modifică] Numărul de grile complete posibile

Este evident că numărul de grile este mai mic decât numărul de moduri de a plasa nouă cifre 1, nouă cifre 2, ... nouă cifre 9 într-o grilă de 81 de căsuţe. Numărul grilelor este deci mai mic decât

$\frac{81!}{9!^9} \approx 5,31306887 \times 10^{70}$

Într-adevăr, în această numărătoare, nu se ţine cont de nici o constrângere de unicitate.

Numărul grilelor complete posibile este inferior numerelor pătratelor latine de latură 9.

În sfârşit, numărul grilelor complete posibile este inferior lui $9! 9$ care ar corespunde numărului de feluri de a construi regiunile fără a ţine cont de constrângerile liniilor şi ale coloanelor.

În 2005, Bertram Felgenhauer şi Frazer Jarvis au en demonstrat că acest număr de grile este:

$6 670 903 752 021 072 936 960 \approx 6,67 \times 10^{21}$ (pentru mai multe detalii, vedeţi în engleză [6]).

Acest număr este egal cu:

$9! \times 72^{2} \times 2^{7} \times 27704267971$

Ultimul factor este un număr prim. Acest rezultată a fost demonstrat cu ajutorul unei căutări exhaustive. Frazer Jarvis a simplificat apoi considerabil demonstraţia cu ajutorul unei analize detaliate. Demonstraţia a fost validată de manieră independentă de către Ed Russell. Jarvis şi Russell au arătat că în ţinând cont de simetrii, există 5.472.730.538 soluţii en [7].

Pe de altă parte, la această dată, nu există nici un rezultat care să indice numărul grilelor complete într-un super sudoku (grilă de 16 × 16).

Dacă este să ne interesăm acum asupra numărului problemelor propuse, acesta este net mai important pentru că există mai multe modalităţi de a descoperi cifrele unei aceleiaşi grile.

Problema numărului de căsuţe precompletate în prealabil necesare pentru a da o rezolvare unică este actualmente nerezolvată. Cel mai bun rezultat, obţinut de japonezi, este de 17 căsuţe fără nici constrângere de simetrie. en [8] en [9]. Nimic nu indică faptul că nu ar fi posibilă găsirea unei soluţii unice cu mai puţine numere. Gordon Royle indică faptul că două rezolvări sunt considerate ca fiind diferite dacă nu pot fi transformate una în alta (sau invers) cu ajutorul unei combinaţii a operaţiilor următoare:

permutări de 9 numere
schimbarea rândurilor cu coloanele (transpoziţie)
permutarea liniilor într-un singur bloc
permutarea coloanelor într-un singur bloc
permutarea blocurilor pe un rând de blocuri
permutarea blocurilor pe o coloană de blocuri

Se remarcă analogia cu operaţiile matriciale în algebra lineară.

[modifică] Matematică

Problema cu plasearea cifrelor pe o grilă de n²×n² cuprinzând n×n regiuni este demonstrată ca fiind NP-completă (pentru mai multe detalii, vedeţi en [10]). Aceasta înseamnă că este absolut imposibil (s-a demonstrat de asemenea că nu depinde de nivelul nostru actual de cunoştinţe) de a găsi un algoritm eficace (polinomial în mărimea grilei şi determinist) pentru a rezolva toate grilele de sudoku de fără limite de mărime (vedeţi teoria complexităţii pentru mai multe detalii în ceea ce priveşte NP-completitudinea). În limbaj obişnuit, aceasta înseamnă că există grile de sudoku pentru care căutarea soluţiei cere la anumite momente folosirea metodei backtracking (*). Pe grilele de mărime finită dată, rezolvarea poate să se facă cu ajutorul unui automat finit care cunoaşte ansamblul arborelui de joc.

(*) Backtracking-ul (refăcând calea) consistă în a face o presupunere fără ca aceasta să fie justificată şi în a continua căutarea soluţiei, existând posibilitatea revenirii la pasul anterior şi schimbarea presupunerii făcute dacă aceasta a dus la imposibilitatea continuării.

Rezolvarea unui Sudoku poate fi formalizată asemenea problemei colorării grafurilor. Scopul, în versiunea clasică a jocului, este aceea de a aplica 9 culori pe un graf dat, plecând de la o colorare parţială (configuraţia iniţială a grilei). Acest graf posedă 81 vârfuri, unul pentru fiecare celulă. Fiecare poate fi etichetat cu un cuplu ordonat (x, y), unde x şi y sunt întregi cuprinşi între 1 şi 9. Două vârfuri distincte etichetate cu (x, y) şi (x’, y’) sunt legate printr-o margine dacă şi doar dacă:

x = x’ sau,
y = y’ sau,
⌈x/3⌉ = ⌈x’/3⌉ şi ⌈y/3⌉ = ⌈y’/3⌉

Grila se completează atribuind un întreg între 1 şi 9 pentru fiecare vârf, astfel încât toate vârfurilor legate printr-o margine să nu aibă comun acelaşi întreg.

O grilă soluţie este de asemenea şi un pătrat latin. Există substanţial mai puţine grile soluţii decăt pătrate latine, pentru că Sudoku impune constrângeri suplimentare (Vedeţi mai sus punctul 4: numărul de grile complete posibile).

Numărul maxim de căsuţe precompletate astfel încât nici o soluţie unică să nu apară imediat, prin oricare metodă de rezolvare, este mărimea grilei minus 4: dacă două perechi de candidaţi nu sunt înscrişi şi dacă celulele goale ocupă colţurile unui dreptunghi, şi dacă exact două celule sunt într-o regiune, atunci există două feluri de a înscrie candidaţii. Problema opusă, adică numărul minim de căsuţe precompletate necesare pentru a garanta o soluţie unică, este nerezolvată, chiar dacă entuziaştii japonezi au descoperit o grilă 9×9 fără simetrie care conţine doar 17 căsuţe precompletate (pentru mai multe detalii, vedeţi en [11] şi en [12]), aceasta în măsura în care 18 este numărul minim de căsuţe precompletate pentru grilele 9×9 simetrice.

[modifică] Reguli şi terminologie

De obicei, jocul este propus sub forma unei grile de 9×9, împărţită în sub-grile de 3×3, numite "regiuni". Câteva celule conţin cifre, aşa-numitele "căsuţe precompletate". Scopul este acela de a umple celulele goale, cu câte o cifră în fiecare celulă, în aşa fel încât fiecare rând, fiecare coloană şi fiecare regiune să conţină cifrele de la 1 la 9 o singură dată. În consecinţă, fiecare cifră a soluţiei apare o singură dată în trei "direcţii", de unde numele "cifră unică". Când o cifră poate fi înscrisă într-o celulă, aceasta se numeşte candidată.

[modifică] Metode de rezolvare

Regiunea din colţul dreapta sus trebuie să conţină un 5. Eliminând rândurile şi coloanele care conţin un 5, jucătorul elimină toate celulele goale care nu pot conţine această cifră. Nu mai rămâne deci decât o singură celulă posibilă, cea colorată în verde.

Metoda de rezolvare este compusă din trei procedeuri: căutarea, folosirea cifrelor candidate, respectiv analiza.

[modifică] Căutarea

Căutarea este prima metodă aplicată la începutul jocului, precum şi periodic în timpul umplerii grilei. Mai multe căutări sunt adesea necesare între două momente de analiză. Această căutare face apel la două tehnici simple:

Reducerea prin cruce: aceast înseamnă, pentru fiecare cifră, eliminarea celulelor unde aceasta nu poate fi plasată. Pentru a determina aceste celule, jucătorul trasează o linie imaginară pe fiecare linie şi pe fiecare coloană unde cifra apare deja. Căsuţele care nu sunt traversate de nici o astfel de linie imaginară sunt acelea unde cifra poate fi inserată. Această metodă poate fi folosită pentru completarea mai întâi a căsuţelor "celor mai uşoare". Pentru a câştiga timp, jucătorul poate înceape prin cifrele cele mai numeroase printre căsuţele precompletate, dar este important ca metoda să fie aplicată fiecărei cifre. Pentru a minimiza timpul de căutare în celelalte etape, această căutare trebuie făcută sistematic, verificând toate cifrele.

Numărătoarea de la 1 la 9 pentru fiecare regiune, fiecare rând şi fiecare coloană. Această etapă permite găsirea cifrelor lipsă. (Făcând-o în funcţie de ultima cifră găsită poate accelera căutarea.) În grilele dificile, cifra care trebuie înscrisă poate să fie determinată făcând o numărătoare inversă, adică încercând găsirea cifrelor care nu pot apărea în celulă, ceea ce permite determinarea cifrelor candidate.

Jucătorii experţi caută "contingenţele" în timpul căutării, adică încearcă să determine celulele candidat (două sau trei) pentru o cifră anume. Când cifrele sunt toate în acelaşi rând (sau coloană), şi o regiune, ele sunt folosite în timpul reducerii prin cruce şi a numărătorii (vedeţi en exemplu). Grilele cele mai dificile cer recunoaşterea contingenţelor multiple, de multe ori în direcţii diferite sau la intersecţii. Aceasta obligă jucătorii la înscrierea cifrelor candidate (metodă descrisă în continuare).

Grilele care se pot rezolva prin reducerea prin cruce sunt considerate ca fiind uşoare, cele mai dificile necesitând alte tehnici de rezolvare.

[modifică] Cifrele candidate

Cifrele candidate pentru fiecare celulă au fost înscrise. Anumite celule au numai câte o cifră candidat, după ce candidatele invalide au fost eliminate. (Apăsaţi pe imagine pentru a vedea versiunea mărită.)

Căutarea se opreşte atunci când nici o cifră nouă nu mai este înscrisă. Din acest moment se foloseşte o altă tehnică. Unora dintre jucători li se pare mai uşor să înscrie cifrele candidate în celulele goale. Există două notaţii folosite: indicele şi punctele.

Pentru notaţia cu indici, cifrele candidate sunt înscrise într-o celulă, fiecare cifră putând ocupa sau nu un loc precis. Inconvenientul acestei metode este că ziarele publică grile în general de o mai mică mărime, ceea ce face relativ dificilă înscrierea mai multor cifre într-o aceeaşi celulă. Mai mulţi jucători reproduc la scară mai mare grilele sau recurg la un creion fin.
Pentru notaţia cu puncte, jucătorii înscriu puncte în celulele goale. Poziţia relativă a unui punct indică cifra care lipseşte. De exemplu, pentru a indica 1 într-o celulă, se pune un punct în stânga sus. Această notaţie permite rezolvarea directă a unei grile imprimată dintr-un ziar. Cu toate acestea, ea necesită o anumită dexteritate, existând posibilitatea relativ uşoară de a plasa greşit un punct într-un moment de neatenţie, iar acest mic marcaj făcut din greşeală poate duce ulterior la confuzie. Unii jucători preferă de aceea folosirea unui pix pentru a limita posibilitatea apariţiei greşelilor.

[modifică] Analiza

Cele două teme ale acestui procedeu sunt eliminarea şi ipoteza.

Eliminarea: căutarea soluţiei se poate face eliminând succesiv cifrele candidate pentru o casuţă astfel încât să nu se păstreze decât o singură cifră candidat. O dată ce această candidată a fost găsită, o altă căutare trebuie efectuată pentru a determina consecinţele pe care această alegere o are asupra celorlalte căsuţe. Există mai multe tehnici de eliminare care se bazează pe regulile de mai jos, reguli ce au nişte corolaruri utile:

Un ansamblu dat de n căsuţe într-un rînd, o coloană sau o regiune, nu poate să primească decât n cifre diferite. Această regulă este la baza tehnicii de "eliminare a cifrei candidat orfane", discutată mai jos.
Fiecare candidată trebuie să aparţină unui model auto-consistent şi independent. Această regulă stă la baza tehnicilor de analiză avansate, care cer inspecţia ansamblului tuturor posibilităţilor pentru o cifră candidat. Există un număr finit de "circuite închise" sau posibilităţi de grile "n×n". Această regulă a dat naştere metodelor X-Wing, respectiv Swordfish, printre altele. Dacă un astfel de model este identificat, atunci eliminarea cifrelor candidate este deseori posibilă.

Una din tehnicile cele mai folosite este "eliminarea cifrei candidat orfane". Căsuţele cu un acelaşi ansamblu de cifre candidat se zic cuplate dacă numărul candidatelor din fiecare din ele este egal cu numărul de căsuţte care le pot conţine. De exemplu, două căsuţe sunt cuplate dacă conţin o pereche unică de candidaţi (p,q) într-un rând, o coloană sau o regiune; trei căsuţe se zic cuplate dacă conţin un triplet unic de cifre candidate (p,q,r). Aceste cifre nu pot apărea în alte părţi, pentru că ar exista un conflict într-o linie, o coloană sau o regiune. Pentru acest motiv, cifrele candidate (p,q,r) care se găsesc în celelalte celule trebuie eliminate. Acest principiu merge cu sub-ansambluri de cifre candidate: dacă trei celule au doar { (p,q,r), (p,q), (q,r) }, sau { (p,r), (q,r), (p,q) }, toate cifrele candidate ale aceste mulţimi care se găsesc în celelalte căsuţe trebuie eliminate.

- Un al doilea principiu decurge din principiu precedent. Dacă numărul celulelor într-un rând, o coloană sau o regiune este egal cu mărimea unei mulţimi de cifre candidate, celulele şi cifrele sunt cuplate şi doar aceste cifre vor apărea în căsuţe. Toate ceilalte cifre candidate trebuie eliminate. De exemplu, dacă (p,q) poate apărea doar în două căsuţe (dintr-un rând, coloană sau regiune), ceilalte cifre candidate trebuie eliminate.

Primul principiu se bazează pe conceptul de "cifre cuplate unic", pe când al doilea se bazează pe conceptul de "căsuţe cuplate unic". Tehnicile avansate se bazează pe aceste concepte şi cuprind rânduri multiple, coloane multiple şi regiuni multiple.

Folosind metoda ipotezei, o căsuţă cu doar două cifre candidat este aleasă şi una din cele două cifre este înscrisă în celulă. Etapele precedente sunt repetate şi fie duc la o contradicţie (cifră duplicată sau căsuţă fără candidat), fie la o propunere validă. Evident, în cazul unei contradicţii, a doua cifră face parte din soluţie. Algoritmul lui Nishio este o formă simplificată a acestei metode: pentru fiecare cifră candidat dintr-o căsuţă, inserarea unei cifre anume previne înscrierea acestei cifre candidat în altă parte în grilă? Dacă răspunsul este da, atunci cifra candidată este eliminată.

Metoda prin ipoteză necesită folosirea unui creion şi a unei gume de şters. Puriştii o resping, pentru că este o metodă de încercări şi eşecuri, prin tatonări, pe când majoritatea grilelor publicate fac apel doar la logică pentru a fi rezolvate. Cu toate acestea, această metodă are meritul de a duce mai rapid la soluţie.

Rămâne la latitudinea fiecărui jucător găsirea unei metode care să îi ofere cele mai bune rezultate. Unii vor dezvolta o metodă care să reducă inconvenientele propunelor precedente. De exemplu, unii vor găsi plictisitor înscrierea tuturor cifrelor candidat în toate căsuţele. Metoda ipotezei cere organizare. Ideal este găsirea unei modalităţi de rezolvare care să minimizeaze numărarea, numărul cifrelor candidat şi numărul de ipoteze.

[modifică] Soluţii informatice

Pentru un informatician, a programa căutarea unei soluţii prin intermediul contingenţelor sau multiplelor contingenţe (aşa cum se cere pentru problemele cele mai dificile) este o sarcină relativ simplă. Un astfel program imită un jucător uman care caută o soluţie fără să caute la întâmplare.

Este de asemenea relativ simplu conceperea unui algoritm de căutare prin backtracking. De obicei, este suficient ca algoritmul să aleagă 1 pentru prima celulă, apoi 2 pentru următoarea, atâta timp cât nu apare nici o contradicţie. Când apare o astfel de contradicţie, algoritmul încearcă o altă valoare pentru căsuţa care duce la contradicţie. O dată epuizate toate posibilităţile pentru această căsuţă, algoritmul "revine" şi reîncepe cu penultima celulă.

Chiar dacă acest algoritm nu este foarte eficace, el va găsi o soluţie dacă dispune de suficient timp. O grilă de 9×9 este de obicei rezolvată în mai puţin de trei secunde de un computer modern care are acces la un interpretor, şi în mai puţin timp cu un limbaj compilat.

Un program mai eficace se va baza pe cifre candidate potenţiale pentru fiecare căsuţă, eliminând cifrele candidat imposibile până când rămâne o singură cifră. Cunoscând această cifră, algoritmul poate găsi o altă cifră pentru o altă căsuţă, şi tot aşa.

O alternativă la backtracking este aceea de a recurge la metodele preconizate de programarea logică, aşa cum este implementată de Prolog şi de Scheme. În acest caz, se furnizează programului constrângerile grilei (o cifră pe rând, pe coloană şi pe regiune; cifrele descoperite); acest program va lua singur deciziile pentru rezolvarea problema. Ştiind că majoritatea grilelor au o soluţie unică, căutarea va avea cu siguranţă succes.

Donald Knuth a pus la punct un algoritm care face apel la listele dublu înlănţuite, şi care se pare că este foarte eficace pentru rezolvarea acestui tip de problemă. S-a demonstrat că acest algoritm este indicat pentru la rezolvarea unui Sudoku, durând doar câteva milisecunde. Datorită vitezei sale, este acum preferat de majoritatea programatorilor.

[modifică] Grade de dificultate

Grilele publicate menţionează deseori gradul de dificultate. Acesta este calculat în funcţie de uşurinţa de rezolvare printr-o metodă logică. Surprinzător, numărul căsuţelor precompletate nu are aproape nici o legătură cu dificultatea unei grile. Grilele cu un mic număr de cifre pot fi uşor de rezolvat, pe când altele care conţin un număr mai mare de căsuţe precompletate decât de obicei pot fi foarte greu de rezolvat.

Cunoscând complexitatea regulilor, programele de rezolvare automată pot estima dificultatea găsirii unei soluţii pentru un om. Această estimare este în general suficient de precisă pentru a permite editorilor de a o folosi. Unii editori de grile online folosesc şi ei această estimare.

Mai mulţi factori influenţează dificultatea problemelor. Ecuaţia de bază ţine cont de:

numărul căsuţelor care sunt necompletate
numărul căsuţelor umplute prin eliminare
numărul de ipoteze necesare pentru a completa grila
numărul căutărilor care trebuie făcute pentru a completa grila

[modifică] Construcţia grilelor

Se pare că Dell Magazines, pionier în domeniul publicaţiilor Sudoku, îşi generează grilele cu ajutorul computerului. Acestea sunt de obicei compuse din 30 de cifre descoperite distribuite la întâmplare. Autorul grilelor este necunoscut. În timpul iernii din 2000, Wei-Hwa Huang a afirmat că era autorul programului care generează aceste grile; după spusele lui, grilele anterioare erau construite de mână. Generatorul ar fi scris în C++ şi, deşi oferă anumite opţiuni pentru a satisface piaţa japoneză (cum ar fi simetria, respectiv mai puţine cifre), Dell preferă să nu le folosească. Unii speculează că Dell continuă să folosească acest program, dar nici o dovadă nu poate susţine aceste afirmaţiile.

Grilele de Sudoku de la Nikoli, important creator de Sudoku în Japonia, sunt construite de mână, numele autorului apărând împreună cu fiecare grilă publicată; căsuţele precompletate sunt tot timpul prezentate de o manieră simetrică. Number Place Challenger de la Dell afişează şi el numele autorului. Se pare că şi grilele publicate în majoritatea ziarelor britanice sunt generate automat, dar fac apel la simetrie, ceea ce dă de înţeles că ar fi creaţia unui om. The Guardian afirmă că grilele sale sunt create manual de japonezi, dar nu este făcută nici o menţiune a acestuia. Ele ar putea fi construite de persoane de la Nikoli. The Guardian a afirmat că fiind construite de mână, grilele conţin "aluzii subtile" foarte puţin probabil să existe în grilele construite de computer.

Este posibil să se construiască grile cu mai multe soluţii şi chiar fără nici o soluţie, dar acestea nu sunt considerate ca fiind Sudoku autentice. Ca şi pentru alte jocuri de logică, se cere o soluţie unică. Este deci necesară mare atenţie în timpul construcţiei unei grile, ştiind că o singură cifră prost plasată poate face imposibilă rezolvarea grilei.

[modifică] Vezi şi

Caută Sudoku în Wikţionar, dicţionarul liber.

Pătrat latin
Wayne Gould
Dell Magazines
Nikoli
Kakuro

[modifică] Legături externe

Beneficiind de un succes fără precedent pentru acest tip de joc, paginile Internet care au ca subiect Sudoku sunt foarte numeroase:

[modifică] Generale

[modifică] Programe

[modifică] Grile de joc

[modifică] Referinţe

În legătură cu popularitatea rapidă a Sudokului în Marea Britanie:
- en The puzzling popularity of Su Doku BBC News, 22 aprilie 2005)
- en So You Thought Sudoku Came From the Land of the Rising Sun... The Observer, 15 mai 2005
- en Do You Sudoku? The Economist, 19 mai 2005

Adus de la "http://ro.wikipedia.org../../../s/u/d/Sudoku.html"

Categorii: Matematică recreativă | Cultura japoneză | Fenomen de modă | Jocuri