Sudoku

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

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, iar editorul are posibilitatea să indice și 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.

Istoric

Problema ofițerilor

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

În 1782 matematicianul 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 grafurilor.

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

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.

Î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ă și, în 1996, publică versiunea pentru Palm.

În 2005 Dell Magazines publică două reviste 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 cu grile cotidianului francofon Le Matin care a vândut în 2005 150000 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.

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ă la 12 noiembrie 2004.

Trei zile mai târziu , The Daily Mail publică o grilă sub numele Codenumber. The Daily Telegraph introduce prima sa grilă la 19 ianuarie 2005, urmat de alte publicații al Telegraph Group. La 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 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 din 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.

Televiziunea britanică s-a grăbit să profite de această popularitate, Sky One difuzând prima emisiune despre Sudoku, Sudoku Live, la 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 patru 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. Aceasta însă avea 1905 rezolvări posibile diferite.

Această bruscă creș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.

La 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 jucător al anului.

Variante

Un Sudoku nonomino

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 pentomino ș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 hexomino și o regiune despărțită (propusă la Campionatului Mondial de Puzzle);
• grile de 9×9 cu regiuni în formă de nonomino;
• 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 metagrilă 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ă este numită Samurai Su Doku.;
• Grile cu regiuni rectangulare: dacă o regiune este de dimensiunile linii x coloane căsuțe, grila globală se descompune în regiuni linii x coloane, valorile urmând a fi completate sunt cuprinse în intervalul de la 1 la linii x coloane;
• 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. 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.

Code Doku conceput de Steve Schaefer conține o frază completă, pe când 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 afirmă 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.

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

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 demonstrat că acest număr de grile este

$6670903752021072936960\approx 6,67\times 10^{21}.$

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.

Pe de altă parte, 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ă nicio constrângere de simetrie. 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:

1. permutări de 9 numere;
2. schimbarea rândurilor cu coloanele (transpoziție);
3. permutarea liniilor într-un singur bloc;
4. permutarea coloanelor într-un singur bloc;
5. permutarea blocurilor pe un rând de blocuri;
6. permutarea blocurilor pe o coloană de blocuri.

Se remarcă analogia cu operațiile matriciale în algebra liniară.

Matematică

Problema cu plasarea cifrelor pe o grilă de n²×n² cuprinzând n×n regiuni este demonstrată ca fiind NP-completă. 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, aceasta în măsura în care 18 este numărul minim de căsuțe precompletate pentru grilele 9×9 simetrice.

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

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 procedee: căutarea, folosirea cifrelor candidate, respectiv analiza.

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: aceasta î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 începe 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.) 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.

Cifrele candidate

Un exemplu a notației cu puncte

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.

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 căsuță 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:

1. „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.
2. „Fiecare candidată trebuie să aparțină unui model autoconsistent ș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țe 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 celelalte 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), celelalte 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 propunerilor 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ă minimizeze numărarea, numărul cifrelor candidat și numărul de ipoteze.

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 rezolvarea unui Sudoku, durând doar câteva milisecunde. Datorită vitezei sale, este acum preferat de majoritatea programatorilor.

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

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.

Vezi și

• Pătrat latin
• Wayne Gould
• Dell Magazines
• Nikoli
• Kakuro
• Matematică recreativă

Bibliografie

• en Delahaye, Jean-Paul, "The Science Behind Sudoku", Scientific American magazine, June 2006.
• en Kim, Scott, "The Science of Sudoku" Arhivat în 19 octombrie 2013, la Wayback Machine., 2006
• en Provan, J. Scott, "Sudoku: Strategy Versus Structure", American Mathematical Monthly, October 2009. Published also as a University of North Carolina technical report UNC/STOR/08/04, 2008.

Legături externe

• Materiale media legate de Sudoku la Wikimedia Commons
• en Sudoku pe Curlie – An active listing of Sudoku links
• en 'Father of Sudoku' puzzles next move (BBC)
• fr Metode de rezolvare ale Sudoku
• fr Explicație animată a regulilor
• en Program care generează Sudoku; a folosit la generarea ilustrațiilor acestui articol
• Grila zilnică de sudoku din Evenimentul Zilei Online
• en Legături spre diferite situri propunând grile
• en Reguli și istorie a site-ului Nikoli Arhivat în 13 iunie 2006, la Wayback Machine.
• en O platformă internațională pentru competiția sudoku
• 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