3-SAT è un compito logico in cui è necessario valutare se una serie di espressioni logiche è corretta o se porta ad una contraddizione. Un esempio di questa sequenza è: S ∧ ¬S. A prima vista, questo sembra complicato. Tuttavia, la frase può essere tradotta rapidamente se sai che “∧” significa “allo stesso tempo” e che “¬” è la negazione. Questo traduce l’affermazione in: S E allo stesso tempo no S. Il compito ora è impostare la variabile S Imposta il valore su vero o falso in modo che l’affermazione complessiva sia vera (ovvero non crei una contraddizione). In questo caso è impossibile, perché si ottiene l’uno e l’altro: vero e falso allo stesso tempo (l S = vero) oppure falso e non falso allo stesso tempo (l S = falso). Entrambe le affermazioni sono prive di significato: una cosa non può essere giusta e sbagliata allo stesso tempo. Quindi, questa sequenza di espressioni non è soddisfacente.
3- I problemi SAT includono istruzioni sequenziali, ciascuna delle quali è direttamente correlata a tre variabili, sotto forma di: (UN1 ∨ B1 ∨ C1( ∧ )UN2 ∨ B2 ∨ C2( ∧ … ∧ )UNN ∨ BN ∨ CN). Il computer deve cercare di assegnare valori reali alle variabili affinché l’affermazione aggregata sia vera. A quanto pare, questo problema è NP-difficile. All’aumentare della durata dell’attività, il tempo di elaborazione richiesto aumenta in modo esponenziale.
Walsh ora doveva dimostrare che qualsiasi problema 3-SAT può essere rappresentato in Candy Crush e che la risoluzione di un problema Candy Crush risolve automaticamente il problema 3-SAT associato. Per fare ciò, ha identificato le combinazioni di caramelle nel gioco Candy Crush con variabili e operazioni logiche in un problema 3-SAT. In questo modo l’informatico è riuscito a dimostrare che qualsiasi affermazione booleana sotto forma di 3-SAT può essere rappresentata da un’adeguata distribuzione di caramelle in Candy Crush.
Questo potrebbe essere uno dei motivi per cui il gioco crea così dipendenza. Se fosse facile da risolvere come un gioco di tris, non sarebbe così avvincente.”Toby Walsh, informatico
Ecco come funziona: quando un giocatore effettua un determinato scambio, Walsh lo interpreta come l’assegnazione di un valore booleano a una variabile, ad esempio “La variabile 1 è falsa”. Ogni scambio cambia il campo di gioco. Inoltre, può creare una catena di tre caramelle, che scompaiono istantaneamente e permettono ad altre caramelle di salire sul campo di gioco. Se fai tante permutazioni quante sono le varianti del corrispondente problema 3-SAT, puoi vedere dalle caramelle rimanenti sul campo di gioco se l’affermazione 3-SAT associata è vera o falsa. Ad esempio: se dopo tutte le permutazioni il campo nella terza riga e nella seconda colonna contiene una goccia gialla di limone, ciò equivale all’affermazione “corretto”. Walsh distribuisce in anticipo le caramelle sul campo in modo che una goccia di limone gialla non cada su quel campo a meno che non si formi un numero minimo di tre catene di caramelle: in questo modo il compito Candy Crush viene risolto con successo.
Walsh è stato in grado di dimostrarlo nel marzo 2014, che Candy Crush è NP difficile – e quindi anche complesso da un punto di vista matematico. Può essere rassicurante quando fallisci un altro livello di Candy Crush. Ma questa complessità ha anche il suo fascino. Walsh scrive: »Questo potrebbe essere il motivo della dipendenza del gioco. Se fosse facile da risolvere come un gioco di tris, non sarebbe così attraente.”
“Specialista del web. Appassionato di cultura pop. Pensatore. Foodaholic. Esperto di viaggi. Appassionato di caffè. Sostenitore televisivo amatoriale.”
