Programul su_doku.R din [1] îmbină două sau trei idei: aplică grilei iniţiale (pe toate liniile, coloanele şi blocurile) cele mai simple două reguli, "Hidden Single" şi "Naked Pair" – repetând însă până când nu mai rezultă astfel, vreo nouă fixare pe grilă a unei valori; dacă după aceasta, rămân celule pe care încă există cel puţin câte doi candidaţi, atunci se lansează un mecanism "backtracking" (în cursul căruia am implicat desemenea, cele două reguli menţionate) pentru a decide care dintre candidaţi trebuie fixat pe celulele respective; ca de obicei, se pleacă de la celula cu număr minim de candidaţi – dar candidaţii respectivi sunt abordaţi în ordine aleatorie.
Testând programul pe un set de "30 very difficult Sudoku puzzles" (v. [1]) – am rămas oarecum dezamăgit: contrar înţelegerii mele pentru "very difficult", soluţiile s-au obţinut şi instantaneu şi în mod direct (fără a mai ajunge la "backtracking").
Între timp însă, am înţeles: etichete ca "Harder", "Hardest", "difficult", sau "Easy" etc. reflectă punctul de vedere al celui fără de care jocul ca atare nici nu ar exista: pentru acesta, interesant şi plăcut este să ajungă la soluţie judecând grila concretă respectivă (şi nicidecum, utilizând "backtracking", sau vreun program special de rezolvare), pe baza constrângerilor specifice jocului şi cu cât logica necesară pare mai subtilă şi devine sofisticată – cu atât creşte şi gradul de „dificultate”, iar jucătorul este tentat să atingă un nivel superior de măiestrie.
/kaidoku furnizează un modul Python care permite şi generarea de grile Sudoku pe diverse grade de dificultate; putem testa programul nostru din [1] pentru fişierul text sudoku.txt, care conţine 25000 de grile etichetate după dificultate cu 1..9.
Am fost bucuros desigur, să găsesc un asemenea fişier text pe care să experimentez (pentru practicanţii jocului se oferă şi "book PDF", ca şi în cazul din [1]); mai întâi, am copiat fişierul respectiv, adaptându-l formatului CSV, în fişierul "Seki_sudoku.csv":
grad,grila 1,001400273372085964496720001600247005847601329100938007700092158918570432253004700 1,274000950058921470010070283145760398907835104823049567482090010096418730031000849 ### ... 9,107000003200750000009200008900002030080030060020100007800004200000028006300000409 9,000001096070050008003020100430000700000264000008000014005030400700040060320800000
Programul de testare pe care îl constituim mai departe este asemănător celui folosit în [1] pentru grilele din "HgridSet.csv" – dar acum diferă formatul grilei iniţiale şi avem în plus, câmpul de clasificare "grad".
Mai întâi, prin read_csv() obţinem un obiect "tibble" în care coloana $grad este de tip "factor" (grupând în final după nivelele acestuia, vom putea formula uşor statistici pe grupurile de dificultate):
# test_mysu.R library(tidyverse) source("su_doku.R") tbl9 <- read_csv("Seki_sudoku.csv", col_types="fc") %>% mutate(sol = "", back = 0L, mls = 0L)
> str(tbl9) # inspectăm din consola R tibble [25,000 × 5] (S3: spec_tbl_df/tbl_df/tbl/data.frame) $ grad : Factor w/ 9 levels "1","2","3","4",..: 1 1 1 1 1 1 1 1 1 1 ... $ grila: chr [1:25000] "001400273372085964496720001600247005847601329100938007700092158918570432253004700" "274000950058921470010070283145760398907835104823049567482090010096418730031000849" ... $ sol : chr [1:25000] "" "" "" "" ... # va înregistra soluţiile grilelor $ back : int [1:25000] 0 0 0 0 0 0 0 0 0 0 ... # numărul de reveniri "backtracking" $ mls : int [1:25000] 0 0 0 0 0 0 0 0 0 0 ... # milisecunde
Putem constata imediat, câte grile avem pe fiecare grad de dificultate:
> tbl9 %>% count(grad) # inspectăm din consola R # A tibble: 9 x 2 grad n <fct> <int> 1 3000 # grile cu dificultatea 1 2 3000 3 3000 4 3000 5 3000 6 3000 7 3000 8 3000 9 1000 # grile cu dificultatea 9
Să observăm că dacă accesăm (prin operatorul "[") o valoare din coloana $grila (de exemplu, cea de pe linia 5), obţinem tot un obiect "tibble" (şi nu un vector):
> str(tbl9[5, 2]) # inspectăm din consola R tibble [1 × 1] (S3: tbl_df/tbl/data.frame) $ grila: chr "467090050009516740351407206140273080070941060030865074704608539093154600020030418"
Următoarea funcţie va transforma aceste obiecte "tibble" în vectori întregi (cum avem nevoie în su_doku.R):
tbl2int <- function(tbl_chr) { # tibble [1 × 1], $grid: chr "..." ==> <int> Z grd <- as.character(tbl_chr) as.integer(unlist(strsplit(grd, split="", perl=TRUE))) }
Folosind această funcţie putem formula uşor şi o funcţie prin care să afişăm o grilă iniţială, sau soluţia acesteia (după ce vom fi obţinut-o, pe linia i din tbl9):
print.Kand <- function(i, j=2) { # col.2: $grila, col.3: $sol Z <- tbl2int(tbl9[i, j]) dim(Z) <- c(9, 9) print.table(t(Z)) }
Partea principală a programului de testare decurge la fel ca în [1], dar de data aceasta măsurăm nu numai timpul de rezolvare pentru fiecare grilă, dar (vom vedea îndată din ce motiv) şi timpul total de lucru:
Start <- Sys.time() for(i in 1:nrow(tbl9)) { grd <- tbl2int(tbl9[i, 2]) back <- 0 u <- system.time({ Z <- fixgrid(aspire(grd)) reshat(Z) }) tbl9[i, 3] <- printSol(Result) # înregistrează soluţia grilei curente tbl9[i, 4] <- back tbl9[i, 5] <- round(1000*u["elapsed"]) } End <- Sys.time() print(End - Start)
În final, tabelăm după gradul de dificultate, media şi suma pentru variabilele $back şi $mls (care pentru fiecare grilă, reprezintă numărul de reveniri din "backtracking" şi respectiv, durata soluţionării ei):
stat <- tbl9 %>% group_by(grad) %>% # sumarizează statistic rezultatele summarise(across(c("back", "mls"), list(mean = mean, sum = sum))) print(stat)
Redăm rezultatele execuţiei programului constituit mai sus (cu precizarea că rezultatele diferă de la o execuţie la alta – dat fiind că în reshat() am folosit sample() pentru a „ordona” candidaţii celulei curente – dar diferă nesemnificativ):
Time difference of 38.97481 mins # End - Start `summarise()` ungrouping output (override with `.groups` argument) # A tibble: 9 x 5 grad back_mean back_sum mls_mean mls_sum <fct> <dbl> <int> <dbl> <int> 1 1 0 0 2.50 7495 2 2 0 0 2.89 8671 3 3 0 0 7.31 21916 4 4 0.000667 2 9.24 27725 5 5 0.0487 146 13.2 39632 6 6 0.0927 278 14.3 42995 7 7 0.128 384 15.5 46441 8 8 0.370 1111 18.5 55560 9 9 1.23 1227 27.1 27137 > sum(stat$mls_sum) # sau: sum(tbl9$mls) [1] 277572 # /1000 /60 = 4.6262 minute
Constatăm că şi pentru back şi pentru mls, valoarea medie creşte odată cu gradul de dificultate. Pentru toate cele 3×3000 grile cu gradul de dificultate 1, 2 sau 3, avem back=0, deci soluţia a fost găsită (practic) fără "backtracking"; pentru celelalte grile, valorile back sunt relativ mici (şi este de precizat că ar fi fost sensibil mai mari, dacă pentru a ordona candidaţii celulei curente am fi folosit un criteriu determinist obişnuit, în loc de sample() – v. [1]).
Să observăm că durata mls creşte odată cu gradul de dificultate, dar creşte neuniform – diferenţele (în medie) de la un grad la cel următor fiind de (aproximativ) 0,4,2,4,1,1,3,9 milisecunde (desigur, pentru aceste comparaţii am folosit valorile din coloana $mls_mean; dacă speculam pe coloana _sum, atunci trebuia să ţinem seama de faptul că la gradul 8 avem 3000 de grile, iar la gradul 9 avem numai 1000 de grile).
La prima vedere, apare oarecum consternant acest fapt: execuţia programului "test_mysu.R" durează mult, End-Start fiind cam de 40 minute – în timp ce durata totală a rezolvării propriu-zise a celor 25000 de grile (dată de suma valorilor din coloana stat$mls_sum) este doar de (aproape) 5 minute!
su_doku.R rezolvă o singură grilă, iar în cazul vizat mai sus – într-un timp mediu de 2.5 până la 27.1 milisecunde, în funcţie de gradul de dificultate 1..9. Având de rezolvat 25000 de grile, furnizate într-un fişier sau într-o anumită structură de date – trebuie să prevedem şi o modalitate de înregistrare a soluţiilor acestora; în test_mysu.R constituit mai sus, obiectul tbl9 de tip "tibble" serveşte pentru a înregistra soluţiile pe măsură ce se obţin, alături de grilele iniţiale.
Am constatat mai sus că execuţia părţii principale a programului a luat cam 40 de minute, din care numai cel mult 5 minute constituie durata totală a rezolvării propriu-zise a celor 25000 de grile; la prima vedere, diferenţa de 35 de minute a fost consumată pe de o parte, de cele 25000 de apeluri tbl2int() (necesare pentru a obţine grilele iniţiale ca vectori integer) şi pe de altă parte, de cele trei „instrucţiuni” de atribuire necesare pentru a înscrie pe linia curentă din tbl9 soluţia grilei curente (pentru fiecare dintre cele 25000 de grile) şi valorile back şi mls aferente soluţiei.
Se ştie că asemenea atribuiri individuale necesită copieri suplimentare de obiecte (v. Advanced R, §2.5 "Modify-in-place"), mărind artificial durata execuţiei; totuşi, 35 de minute numai pentru apelurile tbl2int() şi atribuirile menţionate (în număr de numai câteva zeci de mii) – este chiar prea mult… Ce ne-a scăpat mai sus, „la prima vedere”?
Păi am zice că am confundat sau am amestecat cumva, lucrurile; am vrut să testăm "su_doku.R" pe un set mare de grile cu diverse grade de dificultate (lămurind cumva şi ce înseamnă „dificultate” pentru Sudoku), dar am vrut (fireşte) şi să măsurăm duratele. Însă testarea e una, măsurarea e alta, iar măsurarea timpului… cere timp.
Ne-a scăpat din vedere mai sus, operaţia system.time({...}), care aici devine o mare consumatoare de timp, dat fiind că este apelată de 25000 de ori; de fiecare dată, se apelează proc.time() de două ori, înainte şi după evaluarea expresiei dintre acolade, iar proc.time() combină de fiecare dată anumite categorii de timp specifice sistemului de operare subiacent, pregătind şi producând anumite statistici asupra duratei evaluării expresiei respective. În fond, system.time() angajează operaţii multiple şi delicate şi este de evitat folosirea ei în interiorul unui ciclu lung (cum avem mai sus); de regulă, duratele se măsoară prin instrumente specializate, precum Rprof().
Să eliminăm câmpul $mls din tbl9 şi să renunţăm la system.time(); în plus, să aplicăm tbl2int() „vectorial” (coloanei $grila), în loc să o apelăm la fiecare iteraţie:
Start <- Sys.time() tbl9$grila <- lapply(tbl9$grila, tbl2int) for(i in 1:nrow(tbl9)) { grd <- tbl9$grila[[i]] # în loc de apelurile tbl2int(tbl9[i, 2]) back <- 0 # u <- system.time({ Z <- fixgrid(aspire(grd)) reshat(Z) # }) tbl9[i, 3] <- printSol(Result) tbl9[i, 4] <- back } End <- Sys.time() print(End - Start)
Rulând programul cu aceste modificări, obţinem (acum în 6 minute, în loc de 40):
> source("test_mysu.R") Time difference of 6.189756 mins `summarise()` ungrouping output (override with `.groups` argument) # A tibble: 9 x 3 grad back_mean back_sum 1 1 0 0 2 2 0 0 3 3 0 0 4 4 0.000333 1 5 5 0.0493 148 6 6 0.0747 224 7 7 0.135 406 8 8 0.390 1171 9 9 1.17 1174
Împărţind durata de 6 minute la numărul de grile, putem estima că soluţionarea unei grile oarecare a luat în medie cam 14 milisecunde – ceea ce se potriveşte suficient cu valorile mai precise constatate când consideram şi câmpul $mls; şi încă putem compara temporal după gradul de dificultate, având în vedere că (v. graficul statistic din [1]) în medie, mls depinde direct proporţional de back – de exemplu, am putea zice că în medie, rezolvarea unei grile de grad 8 (pentru care back_mean este 0.39) este cam de trei ori mai rapidă faţă de cazul unei grile de grad 9 (pentru care back_mean este 1.17).
Din start, cel mai „dificile” grile sunt cele pentru care $grad are valoarea 9; la prima vedere, dificultatea acestora ar fi dată de valoarea duratei de soluţionare. Numai că pentru "su_doku.R", această durată depinde de… noroc: candidatul de fixat pe celula curentă se alege în mod aleatoriu şi dacă primul încercat este chiar cel din soluţie, atunci se poate ca back să rămână 0, implicând o soluţionare aproape instantanee – altfel, se va reveni ulterior asupra acestei alegeri, iar back şi mls vor creşte.
Să revenim la programul iniţial "test_mysu.R" (păstrând şi system.time()) şi să ne ocupăm numai de cele 1000 de grile cu gradul 9 (cel mai „dificile”):
tbl9 <- read_csv("Seki_sudoku.csv", col_types="fc") %>% filter(grad == 9) %>% mutate(sol = "", back = 0L, mls = 0L)
Să rulăm test_mysu.R de 10 ori, salvând rezultatele în fişierele "run{1-10}.RDS"; să reunim în final, aceste fişiere:
# stat.R library(tidyverse) file_names <- paste0("run", 1:10, ".RDS") df9 <- map_df(file_names, function(fn) { df <- readRDS(fn) %>% mutate(grad = NULL, grila = unlist(lapply(.$grila, function(g) gsub(", ", "", toString(g))))) }) df9 <- df9 %>% arrange(desc(mls)) write_csv(df9, file="grad9x10.csv")
Am eliminat câmpul $grad (trebuia să o fi făcut direct în tbl9, dar am uitat); tbl9$grila era o listă de vectori integer şi acum – am revenit la vectori character.
În fişierul rezultat "grad9x10.csv" avem câte 10 linii pentru fiecare dintre cele 1000 de grile de gradul 9, iar cele 10000 de linii sunt redate în ordinea descrescătoare a valorilor $mls; am formulat acest fişier CSV „pentru orice eventualitate” (de exemplu, îl putem fila într-un editor de text, pentru o primă impresie asupra datelor respective) – dar bineînţeles că pentru investigaţii vom folosi obiectul tibble aferent, df9.
Primele trei linii din df9 sunt:
> df9[1:3, ] # A tibble: 3 x 4 grila sol back mls <chr> <chr> <int> <int> 1 00010048008007050000000800700800… 9671524831836745925249386177582… 21 167 2 00010048008007050000000800700800… 9671524831836745925249386177582… 20 166 3 00760005040000300802001070000820… 8976423514517936286235187949182… 20 148
Constatăm că liniile 1 şi 2 corespund unei aceleiaşi grile, iar aceasta ar fi cea mai dificilă, ca având cea mai mare durată de soluţionare. Redăm (printr-o funcţie similară cu print.Kand()) grila respectivă şi soluţia ei, precum şi valorile back şi mls corespunzătoare ei în cele 10 execuţii test_mysu.R (aici redăm numai soluţia, pe care boldăm cele 26 de valori fixate prin grila iniţială):
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [1,] 9 6 7 1 5 2 4 8 3 [2,] 1 8 3 6 7 4 5 9 2 [3,] 5 2 4 9 3 8 6 1 7 [4,] 7 5 8 2 1 3 9 4 6 [5,] 6 3 1 7 4 9 2 5 8 [6,] 2 4 9 5 8 6 3 7 1 [7,] 4 7 5 3 2 1 8 6 9 [8,] 3 1 6 8 9 5 7 2 4 [9,] 8 9 2 4 6 7 1 3 5 > df9 %>% filter(grila == .$grila[1]) %>% select(back, mls) back mls 1 21 167 # cele mai mari 2 valori dintre cele 10000 2 20 166 3 15 133 4 12 115 5 10 106 6 10 105 7 12 103 8 10 86 9 10 86 10 8 78
Durata soluţionării a variat de la o execuţie la alta a programului su_doku.R, între 78 milisecunde (cu numai 8 reveniri "backtracking") şi 167 milisecunde (făcând acum 21 de reveniri, asupra alegerii aleatoare a candidatului curent).
În orice caz, constatăm prin max(df9$back) că 21 este numărul maxim de reveniri "backtracking" şi avem numai 4 grile pentru care s-a atins acest maxim:
> df9 %>% filter(back == 21) %>% nrow(.) [1] 4
A doua grilă ca dificultate (cea corespunzătoare liniei a treia din df9), tot cu 26 de valori fixate iniţial, constituie iarăşi un caz interesant:
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [1,] 8 9 7 6 4 2 3 5 1 [2,] 4 5 1 7 9 3 6 2 8 [3,] 6 2 3 5 1 8 7 9 4 [4,] 9 1 8 2 6 5 4 7 3 [5,] 5 3 6 4 7 1 2 8 9 [6,] 7 4 2 3 8 9 5 1 6 [7,] 2 8 5 9 3 4 1 6 7 [8,] 3 7 9 1 2 6 8 4 5 [9,] 1 6 4 8 5 7 9 3 2 back mls 1 20 148 # a treia cea mai mare valoare dintre cele 10000 2 17 128 3 3 38 4 3 37 5 3 36 6 3 35 7 3 35 8 0 17 9 0 14 10 0 14
În acest caz, în trei din cele 10 execuţii candidaţii au fost fixaţi „din prima” încercare, fără a fi nevoie să se revină asupra alegerii făcute (şi numai în două execuţii, au trebuit mai mult de 3 reveniri (17 şi respectiv 20), „umflând” de peste 10 ori durata soluţionării (de la 14 la 148 milisecunde)).
Mai sus, am măsurat pentru fiecare execuţie a programului şi back şi mls; dar mls depinde totuşi de calităţile calculatorului pe care se rulează programul şi pe de altă parte, depinde liniar de back (v. graficul statistic din [1]) – deci ar suficient să considerăm numai back.
Pentru cele două grile redate mai sus, valoarea medie a valorilor back în cele 10 execuţii ale programului este 12.8, respectiv 5.2 – încât am putea spune că prima este cam de 2.5 ori mai dificilă decât a doua. Însă, fiindcă back are (pentru toate grilele) valori foarte mici, aflate pe o plajă foarte îngustă – o distincţie ca „de două ori mai dificilă” este mai degrabă exagerată.
vezi Cărţile mele (de programare)