momente şi schiţe de informatică şi matematică
anti point—and—click

Testare, măsurare şi sumarizare (III)

R | backtracking
2021 jul

Demarăm unele investigaţii pe setul de grile Sudoku „dificile” considerat în [2]:

# explore1.R
library(tidyverse)

str2vec <- function(str)  # "şir de caractere" ==> vectorul caracterelor
    unlist(strsplit(str, split=NULL, perl=TRUE))

print.grila <- function(grila, zero=FALSE) {
    G <- str2vec(grila)
    if(zero) G[G == "."] <- "0"
    dim(G) <- c(9, 9)  # structurează ca matrice 9(coloane) × 9(linii)
    print.table(t(G))  # afişează fără '"' (nu "2", ci 2), pe linii
}

n.clues <- function(grila) {  # numărul de valori 1..9 fixate iniţial
    G <- str2vec(grila)
    length(G[G != "."])
}

HG <- readRDS("HG.rds")  # 478 de grile Sudoku "dificile"

HG$grid înregistrează grilele iniţiale, iar HG$sol – soluţiile acestora; pe coloana HG$back avem o listă de câte 50 de valori întregi, reprezentând fiecare numărul de reveniri pe parcursul soluţionării repetate a grilei respective, prin programul su_doku.R din [1].
În principiu, asimilăm „dificultatea” grilei cu media valorilor back asociate ei (durata soluţionării grilei depinde liniar de back).

Formulările mai complicate sau mai lungi le vom înscrie în fişierul "explore1.R"; pentru liniile mai simple (ca şi în scopul verificării unor aspecte), folosim consola interactivă R (liniile respective încep cu prompt-ul obişnuit, ">").

Repartiţia după numărul de indicii iniţiale

Se ştie că pentru ca o grilă Sudoku să aibă soluţie unică este necesar ca valorile fixate iniţial să fie în număr de cel puţin 17 şi măcar 8 dintre acestea să fie distincte.

Să adăugăm în tabelul HG (obiect al clasei tibble") o coloană conţinând pentru fiecare grilă, numărul de indicii iniţiale:

HG <- HG %>% mutate(clues = unlist(lapply(grid, n.clues))) %>%
      relocate(clues, .after = 1)
> head(HG, 2)  # verificare
# A tibble: 2 x 4
  grid                             clues sol                              back  
  <chr>                            <int> <chr>                            <list>
1 85...24..72......9..4.........1…    22 8596124377238541691643795289861… <int2 ..53.....8......2..7..1.5..4...…    23 1453276988396541276729185434961… <int

Numărul valorilor indicate iniţial spune ceva şi despre „dificultate” (dacă se dau mai mult de 40 de valori, atunci grila respectivă devine „uşoară”). Putem vedea în mai multe moduri, cam cum stau lucrurile pentru grilele din HG:

> (table(HG[c("clues")]) -> vcl)
 17  19  20  21  22  23  24  25  26  28 
 38   2   2  96 195 118  16   7   2   2 
> round(vcl/sum(vcl), 3)
   17    19    20    21    22    23    24    25    26    28 
0.079 0.004 0.004 0.201 0.408 0.247 0.033 0.015 0.004 0.004
> hist(HG$clues)

Cam 8% dintre grile au câte 17 indicii, 3% au câte 24, iar 85% sunt grile cu 22, 23 sau 21 de indicii (dintre care aproape jumătate sunt cu câte 22 indicii).

Evidenţierea grilelor cu o aceeaşi soluţie

Există grile iniţiale care au o aceeaşi soluţie finală:

> unique(HG$sol) %>% length
[1] 428  # deci 478 - 428 = 50 alte grile au soluţia între soluţiile acestor 428

Cu alte cuvinte, există 428 de grupuri de grile, fiecare conţinând fie una singură, fie două sau mai multe grile – caz în care grilele din grupul respectiv au o aceeaşi soluţie. Ca să clarificăm lucrurile, putem folosi funcţiile implicate de group_by():

> grs <- HG %>% group_by(sol)
> grs %>% count(sol) %>% filter(n > 1) %>% arrange(desc(n))
# A tibble: 30 x 2  # 30 grupuri au câte măcar două grile
# Groups:   sol [30]
   sol                                                                         n
   <chr>                                                                   <int>
 1 123456789457189236968327154249561873576938412831742695314275968695814312
 2 12345678945718923686932715427184596338469251769573184251296437873621845
 3 12349678545728193696835714224916587357693842183174265931457926869582435
 4 12345678945678912378913254626487395131792586489564123757239461863821743
 5 12345678945678912379821356423754869151936284786419735234287591667592143
 6 12345678945718923668927341529436857176152439883591764234269185751873293
 7 12345678945718926368923741524157839679561382483692457131289564756874193
 8 12345678945678912378913256426789435131827549659436187264591823787264392
 9 12345678945678912378913256427536149834189527696824731559761384261452892
10 12345678945678912378913256427894563131562749896431827559286134763759482
# … with 20 more rows

Deci există 12 grile care au o aceeaşi soluţie, două grupuri pentru care cele câte 5 grile conţinute au aceeaşi soluţie, ş.a.m.d. Să determinăm liniile din tabelul HG pe care se află cele 12 grile cu aceeaşi soluţie:

> lgr <- group_rows(grs)
> ( i12 <- lgr[order(sapply(lgr, length), decreasing=TRUE)][[1]] )
 [1] 344 345 346 359 360 361 363 402 429 461 465 467

group_rows() a produs lista lgr de vectori întregi care dau indecşii rândurilor din tabelul HG corespunzătoare fiecăruia dintre grupurile care au fost ataşate prin group_by() acestui tabel; ordonând lgr descrescător după lungimile vectorilor conţinuţi, am găsit pe primul loc vectorul indecşilor liniilor corespunzătoare celor 12 grile cu aceeaşi valoare în câmpul $sol.

Să afişăm cele 12 linii; excludem câmpul $sol (care are aceeaşi valoare pe toate liniile) şi simplificăm (într-o nouă coloană) câmpul $grid, eliminând caracterul '.' (rămân numai valorile 1..9 care au fost fixate iniţial, ceea ce este suficient în general, pentru a putea sesiza mici deosebiri între cele 12 grile iniţiale); adăugăm coloana $back1 pe care înscriem media celor câte 50 de valori asociate în lista $back fiecărei grile:

> HG12 <- HG[i12, ] %>%
+         select(grid, clues, back) %>%
+         mutate(grid1 = str_replace_all(grid, "\\.", ""),
+                back1 = round(unlist(lapply(.$back, mean)))) %>%
+         arrange(desc(back1))
> print(HG12 %>% select(grid1, clues, back1))
# A tibble: 12 x 3
   grid1                  clues back1
   <chr>                  <int> <dbl>
 1 3483681467392547686765    22   845
 2 3483683146739254768675    22   710
 3 3483681467394254768675    22   678
 4 3483681467392547686475    22   529
 5 3448368146739254768675    22   514
 6 3483681467397254768675    22   506
 7 3483681467392576864754    22   435
 8 3483681446739254768675    22   327
 9 3483681467391247686475    22   322
10 3483681467391247686765    22   245
11 3483683146739124768675    22   245
12 3483681467391247686735    22   159

Cele 12 grile (cu o aceeaşi soluţie) au un acelaşi număr (22) de indicii. Pe coloana $grid1 putem sesiza uşor mici diferenţe între grilele respective, iar acestea au implicat o variaţie importantă (de la 159 la 845) a valorilor parametrului back1. Să afişăm de exemplu, primele două grile – dar în ordine inversă:

> for(i in 2:1) print.grila(HG12$grid[i])
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
 [1,] .    .    3    .    .    .    .    .    .   
 [2,] 4    .    .    .    8    .    .    3    6   
 [3,] .    .    8    3    .    .    1    .    .   
 [4,] .    4    .    .    6    .    .    7    3   
 [5,] .    .    .    9    .    .    .    .    .   
 [6,] .    .    .    .    .    2    .    .    5   
 [7,] .    .    4    .    7    .    .    6    8   
 [8,] 6    .    .    .    .    .    .    .    .   
 [9,] 7    .    .    .    .    .    5    .    .
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
 [1,] .    .    3    .    .    .    .    .    .   
 [2,] 4    .    .    .    8    .    .    3    6
 [3,] .    .    8    .    .    .    1    .    .
 [4,] .    4    .    .    6    .    .    7    3   
 [5,] .    .    .    9    .    .    .    .    .   
 [6,] .    .    .    .    .    2    .    .    5   
 [7,] .    .    4    .    7    .    .    6    8   
 [8,] 6    .    .    .    .    .    .    .    .   
 [9,] 7    .    .    6    .    .    5    .    .    

Singura diferenţă între acestea apare în coloana a 4-a: în loc de "3" pe al treilea loc, pe cealaltă grilă avem "6", în ultima poziţie; „dificultatea” obţinerii soluţiei (aceeaşi soluţie, pentru ambele grile) a crescut astfel, de la 710 la 845.

Sumarizarea dificultăţii grilelor

Mai sus am înfiinţat (de la consolă) coloana $back1 numai pentru HG12; să o adăugăm întregului set, în "explore1.R" (de data aceasta, cu valori int, în loc de dbl):

HG$back1 <- as.integer(round(unlist(lapply(HG$back, mean))))

Prin summary avem o caracterizare imediată a repartizării după valorile $back1 a celor 478 de grile din HG:

> summary(HG$back1)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
   0.00   51.25  111.50  145.53  183.00  845.00 

Cam câte 25% dintre grilele respective au "back1" cel mult 51.25 (am zice că sunt relativ „uşoare”), respectiv cel puţin 183 (iar pentru celelalte 50%, "back1" este între 51.25 şi 183). Cam 50% dintre grile au valoarea "back1" la stânga (iar celelalte 50%, la dreapta) valorii mediane 111.50; media 145.53 fiind sensibil mai mare ca mediana, avem la dreapta medianei şi valori cam „exagerat” de mari ("outliers", corespunzător aici unor grile foarte „dificile”).

Pentru grilele cu dificultatea "back1" mai mare ca 200, avem:

> hard <- HG %>% filter(back1 > 200) %>% select(-back) %>% arrange(desc(back1))
> hist(hard$back1, cex.lab=0.9, cex.main=0.9, cex.axis=0.8); grid()

nrow(hard) ne arată că avem exact 100 astfel de grile, iar de pe histograma obţinută vedem că dintre acestea cam 50 au "back1" între 200 şi 300, vreo 20 au "back1" între 300 şi 400, etc.; numai vreo 4 grile au „dificultatea” cea mai mare, între 700 şi 900.

Pentru a sintetiza grafic repartiţia grilelor, după variabilele $clues şi $back1, putem considera de exemplu această funcţie (dar sunt multe alte posibilităţi):

back_clues <- function(dataSet = HG) {
    boxplot(back1 ~ clues, data = dataSet, cex = 0,
            cex.lab=0.9, cex.main=0.9, cex.axis=0.8, lwd=1.5)
    stripchart(back1 ~ clues, data = dataSet, method = "jitter", 
               pch=20, cex=0.7, col = 2:12, 
               vertical=TRUE, add=TRUE)
    grid()
}

Precizăm doar că method="jitter" deplasează puţin punctele, pentru a evita cumva suprapunerile (altfel, presupunem că se ştie: help(nume_funcţie), de exemplu help(stripchart), afişează informaţiile necesare despre funcţia respectivă, inclusiv exemple de folosire).

Pentru întregul set HG, apelând deci back_clues(), avem:

În baza acestei imagini, putem considera că relevante ca „dificultate” sunt numai grilele (şi de fapt, numai câte o parte a acestora) cu 17, 21, 22, 23 sau 24 indicii iniţiale; pentru celelalte, avem numai valori foarte mici pentru $back1 şi le putem considera ca fiind „uşoare” (cel mai uşoare fiind cele cu 28 indicii, apoi cele cu câte 26 sau 19 indicii, apoi cele cu 25 sau cu 20 indicii).

Selectând numai grilele între care sunt şi cele dificile, avem:

> back_clues(HG %>% filter(clues %in% c(17, 21, 22, 23, 24)))

Se vede că avem puţine grile care sunt într-adevăr, „dificile”: deasupra ordonatei 450 avem numai vreo 25 de puncte.

Următoarea funcţie afişează grila cea mai dificilă, dintre cele cu acelaşi număr de indicii:

theHarder <- function(nclues) {
    hg <- HG %>% filter(clues == nclues) %>% 
          filter(back1 == max(back1))
    print.grila(hg$grid[1])
    hg  # returnează obiectul "tibble" corespunzător grilei afişate
}

Am afişat deja mai sus, cel mai dificile două grile (cu câte 22 indicii, având back1 845 şi respectiv 710); să afişăm grila cea mai dificilă dintre cele cu câte 21 de indicii (ordonata punctului corespunzător ei pe imaginea redată mai sus este ceva mai mare ca 600):

> theHarder(21)
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
 [1,] .    .    .    .    9    .    .    5    .   
 [2,] .    1    .    .    .    .    .    3    .
 [3,] .    .    2    3    .    .    7    .    .   
 [4,] .    .    4    5    .    .    .    7    .
 [5,] 8    .    .    .    .    .    2    .    .   
 [6,] .    .    .    .    .    6    4    .    .   
 [7,] .    9    .    .    1    .    .    .    .   
 [8,] .    8    .    .    6    .    .    .    .   
 [9,] .    .    5    4    .    .    .    .    7

# A tibble: 1 x 5
  grid                          clues sol                           back   back1
1 ....9..5..1.....3...23..7...…    21 7438921565186479329623517486… <int …   644

Desigur, prin:

> lapply(c(17, 21, 22, 23, 24), theHarder) -> lstH

vom obţine pe ecran cele 5 cel mai dificile grile dintre cele cu numărul respectiv de indicii, obţinând şi o listă lstH a obiectelor "tibble" asociate acestora.

vezi Cărţile mele (de programare)

docerpro | Prev | Next