Metode de RezolvareAceste metode de rezolvare sunt rulate in functie de gradul de complexitate - daca oricare din ele modifica grila de solutii atunci rezolvatorul se duce inapoi la metoda de rezolvare A si porneste de la capat. De fiecare data cind o metoda anume este folosita, se contorizeaza puncte ca si 'punctaj de dificultate' pentru a oferi un grad de dificultate pentru sudoku respectiv.
Metoda de Rezolvare D ACTUALIZATA!Metoda revizuita, codata de Alan Chambers - multumim Al! Cauta pe un rand in grila de solutie sa vada daca exista vreun grup de N casute care contin N numere posibile. Daca un astfel de "lant" exista, atunci acele casute trebuie sa contina aceste numere, deci putem elimina aceste numere din alte casute in rind. Acest procedeu se repeta pentru coloane si blocuri. De exemplu, in rand 1 2 3 4 5 6 7 8 9 --------------------------------------------------------------------------------- 378 38 6789 37 458 2 34568 489 1 Coloanele 1, 2 si 4 contin numerele 3, 7 si 8. Deci putem elimina [78] din coloana 3, [8] din coloana 5 si [38] din coloana 7 si [8] din coloana 8. Dupa aceea randul va arata astfel: 1 2 3 4 5 6 7 8 9 --------------------------------------------------------------------------------- 378 38 69 37 45 2 456 49 1 Pentru un exemplu practic, incercati aceasta pagina. Punctaj de dificultate=32, 48 sau 64 pentru valorile N= 2, 3 respectiv 4. Metoda de Rezolvare E - nu este inca implementataAm avut o noua metoda de rezolvare sugerata pentru unul din Challenge Sudoku (Sudoku "Provocare") dar nu am codat-o inca. Pentru a vedea noua regula, sau daca va tenteaza o codare, apasati aici. Metoda de Rezolvare F ACTUALIZATA!Aceasta metoda de rezolvare devine in mod progresiv mai complicata, precum vom vedea in continuare. Cautati la un rand sa gasiti instante unde un numar apare doar in doua casute. Daca exista orice alt rand care satisface aceeasi regula pentru acelasi numar, si coloanele casutelor sunt aceleasi in ambele cazuri, atunci acel numar trebuie sa apara in doua din cele 4 casute. Puteti apoi elimina orice alta aparitie a acelui numar in coloanele care se potrivesc. Se repeta pentru coloane. Aceasta metoda este cunoscuta de experti sub denumirea X-wing. Exista si un procedeu similar si pentru blocuri: Daca, pentru fiecare rand, cele doua casute sunt in acelasi bloc puteti elimina alte aparitii in blocurile care se potrivesc. Repetati pentru coloane rlativ la randuri si coloane relativ la blocuri. Apoi, repetati pentru blocuri - daca doua blocuri impartasesc randuri sau coloane si un singur numar apare in doar doua casute in fiecare bloc, in randurile sau coloanele care corespund, apoi alte aparitii ale numarului pot fi eliminate din acele randuri si coloane. (destul de complicat, eh? nu cred ca inteleg). Aceasta devine din ce in ce mai complicata cu 3-si-3 casute numita Swordfish. In final, exista ordine superioare ale acestei probleme pentru 4 casute etc. Al Chambers a venit inca o data in fata si a codat o versiune generica a Metodei de Rezolvare F care se duce la un grad de complexitate pina la N casute. Sta mintea-n loc! A numit versiunea cu N=4 Jellyfish, care banuiesc se numeste astfel pentru ca "iti inmoaie genunchii". Sunt in total de acord, Al. Punctaj de dificultate=48 (pentru X-wing) sau 64 (Swordfish si deasupra) Alte metode de rezolvareAlte metode de rezolvare pot fi vazute la Website-ul lui John Perry. Acestea sunt destul de complicate dar poate veti fi nevoiti sa mergeti la scriind cod Javascript! Ce este 'permite Ghiceste-si-Verifica'?Aceasta implementeaza ceea ce este cunoscut sub numele de 'Firul Ariadnei'. Daca toate metodele de rezolvare sunt epuizate, este nevoie de a ghici raspunsul pentru o casuta, si apoi incearca sa gaseasca un raspuns prin reaplicarea metodelor de rezolvare. Daca acest rezultat este un Sudoku invalid, incearca sa ghiceasca o alta valoare. Daca sunt inca variante disponibile, va continua sa ruleze pina cind gaseste un raspuns valid (sau invalid). Exista un argument daca acest procedeu este 'logic', deci l-am facut ca si optiune folosind acea casuta de bifare (tickbox). Intoarce Prima Solutie PosibilaDaca folositi metoda Ghiceste-si-Verifica, este intotdeauna posibil ca pentru un Sudoku dat sa exista mai mult decit o solutie. Nebifand 'Intoarce prima solutie' va verifica toate caile posibile sa confirme ca solutia dumneavoastra este unica. RecunoastereMulte multumiri lui 'rubylips' la http://www.act365.com/sudoku/ pentru sfat si ajutor despre 'Firul Ariadnei' si alte observatii folositoare. Multumim de asemenea lui r.e.s pentru furnizarea unui link la dovada ca Sudoku este NP-hard, si pentru testarea rezolvatorului. Multumim lui Pete Forman pentru actualizarea la metoda B, pentru cautarea in blocuri. Multumim lui Colin Hughes pentru descoperirea bug-urilor in modul set. Multumim lui Keven Cook pentru descoperirea bug-ului in reporting pane. Multumim lui Tim Lindsay pentru exemplul nerezolvabil prin logica - care a fost sursa de inspiratie pentru pagina challenge (provocare). Multumim lui Bill Giles pentru ideea pas-cu-pas a rezolvatorului. Multumim lui Mark Summerville pentru furnizarea regulilor logice pentru metodele de rezolvare E si F. Multumim lui Kevin Lawson pentru sugestia de puzzle provocativ alternativ. Multumim lui John MacLeod pentru revizuirea metodei D. Multumim lui David Budgett and John MacLeod (din nou!) pentru versiunea 'bloc' explicativa a metodei F. Multumim lui Tim Nobel and Michael Lawrence pentru sugestiile despre regula lor. Multumim lui Al Chambers pentru codarea metodei revizuite D - bine muncit! Multumim lui Craig Oakley pentru Swordfish. Multumim lui Al din nou pentru Metoda F, generic.. este mult deasupra mea! Multumim lui Nicolas Leoutre pentru traducerea site-ului in Franceza. Multumim lui Sernin Van de Krol pentru traducerea site-ului in Olandeza. Multumim lui Riccardo Riva pentru traducerea site-ului in Italiana. Multumim lui Gordon Royle pentru ca ne-a legat la lista sa de 17-digits sudoku. Multumim lui Pat Breniser pentru pontul despre cum sa imbunatatim rezolvatorul pas-cu-pas. |