Jocul Sudoku constă în completarea unei rețele pătrate împărțite în N regiuni de N casete, parțial umplute cu numere, astfel încât în fiecare rând, fiecare coloană și fiecare regiune numerele de la 1 la N să apară o singură dată.
O analiză matematică a Sudoku vă permite să descoperiți diferitele proprietăți și probleme din spatele acestui joc și variantele sale.
Analiza matematică a sudoku-ului este împărțită în două părți principale: analiza proprietăților grilelor complete și analiza rezoluției unei grile.
O mare parte din accentul analizei grilelor s-a concentrat pe enumerarea soluțiilor posibile pentru diferite variații ale jocului. Studiul rezolvării se concentrează pe valorile inițiale ale grilei și pe etapele care duc la grila completă. Aceste tehnici fac apel la mai multe discipline: analiza combinatorie, algoritmică, teoria grupurilor, precum și programarea, deoarece computerul permite rezolvarea rapidă a grilelor.
Există un număr mare de variații Sudoku, caracterizate de obicei prin dimensiunea grilei (parametrul N ) și forma regiunilor. Sudokusurile clasice au un N egal cu 9 cu regiuni de celule 3 × 3. Un sudoku dreptunghiular are regiuni dreptunghiulare de dimensiunea L × C unde L este numărul de rânduri și C numărul de coloane. Un astfel de sudoku, cu dimensiunea L × 1 (sau 1 × C ), devine un pătrat latin, deoarece regiunea este un singur rând sau coloană.
Există variante mai complexe, cum ar fi cele cu regiuni tăiate neregulat ( Nanpure ), cu constrângeri suplimentare ( Samunamupure sau Killer Sudoku , respectarea unicității pe diagonalele cu Kokonotsu , constrângeri în ordinea elementelor cu Greater -Than ) sau ansambluri de mai multe grile ( Samurai , Sudoku în 3D). În unele variante, numerele sunt înlocuite cu litere. Cu toate acestea, această înlocuire a personajelor utilizate nu schimbă proprietățile intrinseci ale puzzle-ului dacă regulile rămân aceleași.
Analiza matematică a sudoku-ului a urmărit popularitatea jocului. Analizele privind complexitatea algoritmică și completitudinea NP a jocului au fost documentate spre sfârșitul anului 2002, rezultatele enumerării au apărut pe la jumătatea anului 2005. Contribuțiile multor cercetători și amatorii au făcut posibilă actualizarea proprietăților jocului. Apariția variantelor Sudoku extinde și mai mult elementele matematice care trebuie luate în considerare și explorate.
În contrast cu cele două abordări matematice principale citate la început, o abordare bazată pe logica matematică și abordarea problemei rezolvării puzzle-urilor a fost recent propusă în cartea lui Denis Berthier, „Logica ascunsă a Sudoku” sudoku ascuns). Acest lucru a făcut posibilă descoperirea și formalizarea tuturor simetriilor generalizate ale jocului și descoperirea de noi reguli de rezolvare bazate pe acestea, precum lanțurile xy ascunse.
Problema plasării cifrelor pe o grilă n 2 × n 2 cu n × n regiuni este NP-completă .
Rezolvarea unui sudoku poate fi formalizată prin problema colorării graficelor . Scopul, în versiunea clasică a jocului, este de a aplica 9 culori pe un grafic dat, dintr-o colorare parțială (configurația inițială a grilei). Acest grafic are 81 de vârfuri, câte unul pe celulă. Fiecare dintre casetele Sudoku pot fi etichetate cu o pereche ordonată (x, y) , unde x și y sunt numere între 1 și 9. Două vârfuri distincte etichetate cu (x, y) și (x ', y') sunt conectate prin o margine dacă și numai dacă:
Grila este completată prin atribuirea unui număr întreg între 1 și 9 pentru fiecare vârf, astfel încât toate vârfurile legate de o margine să nu împartă același număr întreg.
O grilă de soluții este, de asemenea, un pătrat latin . Relația dintre cele două teorii este acum complet cunoscută, deoarece D. Berthier a demonstrat, în „Logica ascunsă a Sudoku”, că o formulă logică de ordinul întâi care nu menționează blocurile (sau regiunile) este valabilă pentru sudoku dacă și numai dacă este valabil pentru pătratele latine.
Există mai puține grile de soluții decât pătratele latine, deoarece Sudoku impune constrângeri suplimentare (a se vedea punctul 4 de mai jos: numărul de grile complete posibile).
Spre deosebire de numărul de grile de soluții, nu se cunoaște numărul exact de puzzle-uri minime. (Un puzzle este minim dacă niciunul dezvăluit nu poate fi eliminat fără a compromite unicitatea soluției.) Cu toate acestea, tehnicile statistice combinate cu definirea unui nou tip de generator (generator de polarizare controlată (in) ) sunt utilizate pentru a arăta că există aproximativ (cu o eroare relativă de 0,065%):
(a se vedea cartea Satisfacție de constrângere bazată pe tipare și puzzle-uri logice sau articolul Statistici nepărtinitoare ale unui CSP - Un generator de tendințe controlate ).
Numărul maxim de dezvăluite fără să apară imediat o singură soluție, indiferent de variantă, este dimensiunea grilei minus 4: dacă două perechi de candidați nu sunt înregistrate și celulele goale ocupă colțurile unui dreptunghi și că exact două celule sunt într-o regiune, apoi există două modalități de a înregistra candidații. Opusul acestei probleme, numărul minim de dezvăluiri pentru a garanta o singură soluție, este o problemă nerezolvată, deși entuziaștii japonezi au descoperit o grilă nesimetrică 9 × 9 care conține doar 17 dezvăluiri (citiți mai multe, a se vedea (en) ). Un rezultat publicat în 2007 arată că, pentru ca un sudoku să aibă o soluție unică, 8 din cele 9 cifre trebuie să fie dezvăluite, în timp ce 18 este numărul minim de revelate pentru grilele simetrice 9 × 9.
Un puzzle este o grilă incompletă cu valori inițiale. Regiunile mai sunt numite blocuri sau zone. Termenul pătrat este evitat pentru a elimina orice confuzie.
O bandă este o serie de blocuri adiacente pe axa orizontală. O stivă este o serie de blocuri adiacente pe axa verticală. Într-un sudoku pătrat de 9 × 9, există astfel 3 benzi și 3 stive.
Un sudoku proiectat corect are o singură soluție: grila finală este unică, dar rezolvarea din grila parțială poate lua totuși căi diferite.
Numărul de rețele complete posibile este de 9! × 72 2 × 2 7 × 27 704 267 971 (adică 6 670 903 752 021 072 936 960 grile ≈ 6,67 × 10 21 ).
Ultimul factor este un număr prim . Acest rezultat a fost dovedit în 2005 de Bertram Felgenhauer și Frazer Jarvis prin cercetări exhaustive . Frazer Jarvis a simplificat foarte mult proba prin analize detaliate. Demonstrația a fost validată independent de Ed Russell.
Cu toate acestea, mai multe grile sunt echivalente dacă luăm în considerare un anumit număr de simetrii, și anume
(Observați analogia cu operațiile matricei în algebră liniară ). Luând în considerare aceste simetrii, Jarvis și Russell au arătat că există 5.472.730.538 grile neechivalente.
În schimb, la această dată, nu există niciun rezultat cu privire la numărul de puzzle-uri complete dintr-un super sudoku (grilă 16 × 16).
Dacă acum suntem interesați de numărul de probleme posibile, acest număr este în mod clar mai important, deoarece există mai multe moduri de a dezvălui cifrele aceleiași grile.
Numărul minim de celule preumplute pentru a face rezoluția unică este de 17; s-a dovedit prin calcul înianuarie 2012de către o echipă irlandeză. O listă cu toate sudokusurile cu o singură soluție cu 17 cutii umplute a fost compilată de japonezi.
Răspunsul la întrebarea „Câți puzzle-uri sudoku sunt?” »Depinde de definirea unei soluții și de echivalența dintre mai multe soluții. Pentru enumerarea tuturor soluțiilor posibile ( adică grile complete), păstrăm următoarea definiție:
O grilă A este diferită de grila B, dacă valoarea casetei din A (i, j) este diferită de B (i, j), pentru cel puțin o pereche i, j (valori limitate de dimensiunea cremaliera).
Dacă o rețea A este obținută prin simetria rețelei B, atunci acestea sunt considerate diferite. Rotațiile sunt, de asemenea, considerate ca soluții noi.
|
|
|
|||||||||||||||||||||||||||
|
|
|
|||||||||||||||||||||||||||
|
|
|
Este :
Numărul de soluții depinde de dimensiunea grilei, de regulile aplicate și de definiția precisă a unei soluții separate. Pentru un sudoku cu regiuni 3 × 3, convențiile pentru afișarea conținutului grilei sunt următoarele: benzile sunt numerotate de sus în jos, stive de la stânga la dreapta. Prin urmare, regiunile sunt numerotate de la stânga la dreapta și de sus în jos. Această convenție se aplică și grilelor dreptunghiulare.
Alți termeni sunt utili în cazul sudoku-ului cu regiuni 3 × 3:
De exemplu, notația h56 corespunde tripletului din regiunea 5, rândul 6. În limba engleză, folosim notația r pentru rând și c pentru coloană .
De asemenea, vorbim despre mini-rând sau mini-coloană pentru a desemna porțiunea prezentă într-o regiune a unui rând sau a unei coloane a grilei.
Se spune că două grile sunt simetric distincte dacă una nu poate fi derivată din cealaltă (printr-una sau mai multe operații de conservare a simetriei).
Conservarea simetrieiUrmătoarele operații transformă întotdeauna o grilă validă într-o altă grilă validă:
Aceste operații definesc o relație de simetrie între două grile echivalente. Prin excluderea schimbării etichetelor și prin luarea în considerare a celor 81 de valori prezente în grilă, aceste operații formează un subgrup al grupului simetric S 81 cu ordinea 3! 8 × 2 = 3.359.232.
Identificați soluțiile folosind lema lui BurnsidePentru o soluție, setul de soluții echivalente care pot fi obținute folosind aceste operații (cu excepția redenumirii valorilor), formează o orbită a grupului simetric. Numărul de soluții simetric distincte este astfel numărul de orbite, valoare care poate fi calculată folosind lema lui Burnside . Punctele fixe ale metodei Burnside sunt soluții care diferă doar prin redenumire. Folosind această tehnică, Jarvis Russell a calculat numărul de soluții simetric distincte: 5.472.730.538.
Pentru valori mari ale L și C , metoda lui Kevin Kilfoil (generalizată mai târziu) este utilizată pentru a estima numărul de moduri de a completa o grilă. Această metodă presupune că constrângerile de pe rânduri și coloane sunt, pentru o primă aproximare, variabile aleatorii independente condițional în ceea ce privește constrângerea din regiune. Calculele algebrice conduc la formula Kilfoil-Silver-Pettersen:
unde b L, C este numărul de moduri de a finaliza un sudoku cu L regiuni (de dimensiunea L × C ) orizontal adiacente. Pettersen Algoritmul, implementat de argint, este în prezent cel mai rapid cunoscut tehnica de a evalua cu exactitate b L, C valori .
Numărul de benzi pentru problemele în care „numărul total de puzzle-uri sudoku este necunoscut” este prezentat mai jos. Ca și în restul acestui articol, dimensiunile corespund celor din regiuni.
Dimensiuni | Număr de benzi | Autor (i) | Verificare formală |
---|---|---|---|
2 × C | (2 C )! ( C !) 2 | (evident) | da |
3 × C | Pettersen | da | |
4 × C | (Vedeți mai jos rezultatul matematic.) | Pettersen | da |
4 × 4 | 16! × 4! 12 × 1.273.431.960 = c. 9.7304 × 10 38 | Argint | da |
4 × 5 | 20! × 5! 12 × 879.491.145.024 = c. 1.9078 × 10 55 | Russell | da |
4 × 6 | 24! × 6! 12 × 677 542 845 061 056 = c. 8.1589 × 10 72 | Russell | da |
4 × 7 | 28! × 7! 12 × 563 690 747 238 465 024 = c. 4.6169 × 10 91 | Russell | da |
(Calculele de până la 4 × 100 au fost efectuate de Silver , dar nu sunt afișate aici.) | |||
5 × 3 | 15! × 3! 20 × 324 408 987 992 064 = c. 1,5510 × 10 42 | Argint | Da # |
5 × 4 | 20! × 4! 20 × 518 910 423 730 214 314 176 = c. 5,0751 × 10 66 | Argint | Da # |
5 × 5 | 25! × 5! 20 × 1 165 037 550 432 885 119 709 241 344 = c. 6,9280 × 10 93 | Pettersen / Silver | Nu |
5 × 6 | 30! × 6! 20 × 3 261 734 691 836 217 181 002 772 823 310 336 = c. 1.2127 × 10 123 | Pettersen / Silver | Nu |
5 × 7 | 35! × 7! 20 × 10 664 509 989 209 199 533 282 539 525 535 793 414 144 = c. 1,2325 × 10 154 | Pettersen / Silver | Nu |
5 × 8 | 40! × 8! 20 × 39 119 289 737 902 332 276 642 894 251 428 026 550 280 700 096 = c. 4.1157 × 10 186 | Pettersen / Silver | Nu |
Expresia pentru cazul 4 × C este:
cu:
suma externă se aplică tuturor a , b , c astfel încât 0 ⩽ a , b , c și a + b + c = 2 C suma interioară se aplică tuturor k 12 , k 13 , k 14 , k 23 , k 24 , k 34 = 0 astfel încât k 12 , k 34 = a și k 13 , k 24 = b și k 14 , k 23 = c și k 12 + k 13 + k 14 = a - k 12 + k 23 + k 24 = b - k 13 + c - k 23 + k 34 = c - k 14 + b - k 24 + a - k 34 = CExistă mai multe tipuri de constrângeri pe sudoku cu regiuni 3 × 3. Numele nu au fost standardizate, legăturile externe indică definițiile:
Tip | Numărul de grile | Autor (i) | Verificare formală |
---|---|---|---|
3doku | 104 015 259 648 | Stertenbrink | da |
Grupuri disjuncte | 201 105 135 151 764 480 | Russell | da |
Hipercub | 37 739 520 | Stertenbrink | da |
Sudoku magic | 5.971.968 | Stertenbrink | da |
Sudoku X | 55 613 393 399 531 520 | Russell | da |
NRC Sudoku | 6 337 174 388 428 800 | Brouwer | da |
Toate sudokusurile sunt valabile (unicitatea numerelor din rânduri, coloane și regiuni) după aplicarea operațiilor care păstrează proprietățile grupului sudoku. Unele sudokus sunt speciale în sensul că unele operații au același efect ca redenumirea numerelor:
Transformare | Numărul de grile | Autor (i) | Verificare formală |
---|---|---|---|
Transpunere | 10 980 179 804 160 | Russell | Indirect |
Sfert de tură | 4 737 761 280 | Indirect | |
Jumătate de rând | 56 425 064 693 760 | Indirect | |
Trupe de schimb | 5 384 326 348 800 | Indirect | |
Permutări de linii în benzi | 39 007 939 461 120 | Indirect |
Rețelele realizate corect trebuie să aibă o singură soluție. Se spune că o grilă este ireductibilă sau minimă dacă este validă și dacă eliminarea unei cifre suplimentare duce la invaliditatea acesteia ( adică nu mai admite o singură soluție). Este posibil să creați grile minime cu un număr diferit de valori inițiale. Această secțiune descrie proprietățile legate de această problemă.
Sudoku-ul clasic cu o grilă de 9 × 9, adică 81 de pătrate, este limitat în prezent de o limită inferioară de 17 valori inițiale sau de 18 când pozițiile cifrelor inițiale pot fi rotite cu 90 °. Există o presupunere care afirmă că această legătură de 17 este cea mai bună posibilă, dar nu există nicio dovadă formală, ci doar o căutare exhaustivă cu grile aleatorii:
Constrângeri suplimentare (cu sudokus ale căror regiuni sunt 3 × 3) modifică numărul de valori minime necesare pentru a veni cu o singură soluție:
O regiune poate fi descrisă prin dimensiunile sale: L × C unde L este numărul de rânduri și C numărul de coloane din regiune. În versiunea clasică de sudoku, L = C = 3. Aceasta implică faptul că există L regiuni pe bandă și C regiuni pe stivă. Este mai convenabil să menționăm dimensiunea regiunii, mai degrabă decât numărul de elemente, deoarece o regiune 2 × 6 are același număr de cutii ca una 3 × 4.
Următoarea decupare poate fi adoptată pentru a clasifica aproximativ variantele:
Constrângeri suplimentare fac posibilă orientarea mai bună a tipului de joc.
Un pătrat de sudoku N × N regiuni are mai multe proprietăți respectate pentru toate sub-elementele sale, în plus față de regula clasică de duplicate. Într-adevăr, fiecare rând și fiecare coloană are o intersecție cu N regiuni și împarte N casete cu fiecare dintre ele. Numărul de benzi și stive de asemenea , este egală cu N . Sudoku dreptunghiular nu are aceste proprietăți.
Sudoku cu regiuni 3 × 3 ascunde o altă proprietate proprie: N este numărul de subunități luate în considerare în joc, și anume trei: rând, coloană și regiune.
Du-suma-oh înlocuiți domeniile de 3 × 3 (sau mai general L × C) pe regiuni neregulate , cu o dimensiune fixă. Bob Harris a dovedit că este întotdeauna posibil să se creeze du-sum-OHS cu N -1 valori inițiale pe N de N grilă . A dat mai multe exemple.
În Samunamupure sau Killer Sudoku , regiunile au nu doar forme neregulate, ci și dimensiuni diferite. Se aplică în continuare regulile pentru unicitatea numerelor din rânduri, regiuni și coloane. Indicațiile inițiale sunt date sub formă de sume de valori în regiuni (de exemplu, o regiune de 4 celule cu o sumă de 10 va conține cifrele 1, 2, 3, 4 într-o anumită ordine). Numărul minim de valori necesare pentru a porni grila nu este nici cunoscut, nici conjecturat.
O variantă propusă de Miyuki Misawa înlocuiește sumele cu relații: indicațiile sunt simboluri = , < , > , care arată valorile relative pentru anumite regiuni adiacente. Este dat un exemplu cu doar 8 relații, dar nu se știe dacă acest număr este limita inferioară.
Abordarea descrisă aici este, în mod istoric, prima strategie utilizată pentru a enumera soluțiile unei grile sudoku clasice (3 × 3 regiuni într-o grilă 9 × 9). A fost propus de Felgenhauer și Jarvis.
Analiza începe prin studierea permutațiilor primei benzi utilizate în soluții valide. Odată identificate clasa de echivalență și simetriile acestei benzi, pentru soluții parțiale, suntem interesați de celelalte două benzi care sunt construite și numărate pentru fiecare clasă de echivalență. Luând suma tuturor combinațiilor, obținem numărul total de soluții, adică 6 670 903 752 021 072 936 960 (aproximativ 6,67 × 10 21 ).
Pentru a reduce spațiul de căutare, presupunem că redenumirea (de exemplu schimbarea „1” în „2” și invers) a celulelor produce o soluție echivalentă. O grilă permite 9! = 362 880 redenumiri de acest tip: un număr ales dintre cele 9 cifre posibile este atribuit primului tip de casetă, un număr din restul 8 este atribuit celui de-al doilea tip de casetă, un număr din restul 7 este atribuit al treilea tip de caz etc.