[Article Spotlight] Permutazioni nella risoluzione di uno Shikaku tramite bruteforcing in C#

Benvenuti a questo nuovo appuntamento con l'Article Spotlight del martedì.

Oggi vi propongo un articolo nel quale lavoreremo un po' di logica, e prenderemo come base un gioco giapponese piuttosto recente, lo Shikaku. In esso si gioca su una griglia di varie dimensioni, e si deve riuscire a dividere il campo di gioco in rettangoli non sovrapposti, sulla base di alcune indicazioni numeriche presenti sulla griglia stessa.

Cito dall'articolo

Shikaku (shikaku ni kire, dividere per quadrati) è un gioco di logica giapponese pubblicato da Nikoli Co. Ltd  , editore specializzato in giochi, specialmente puzzle logici. Dello stesso editore, è – per fare un esempio – anche il più celebre Sudoku. Lo Shikaku (letteralmente, in lingua giapponese, quadrato) si gioca su una griglia di uguali righe e colonne, che può estendersi dalle dimensioni di 5 x 5 fino a 25 x 25 e oltre. 
Alcune delle celle che costituiscono la griglia di gioco sono numerate. L’obiettivo del gioco è quello di dividere la griglia in rettangoli e quadrati tali per cui ciascuna di queste divisioni contenga uno solo dei numeri presenti, e che l’area di tale porzione sia pari al numero stesso. Ciò significa che due divisioni della griglia non possono sovrapporsi, ovvero condividere celle.

Riportiamo qui a seguire un esempio di Shikaku 11 x 11, con relativa soluzione:

 
Griglie più piccole sono ovviamente più semplici da risolvere, e tuttavia si può essere tratti in inganno nel selezionare aree errate e dover ritornare sui propri passi, quando ci si rende conto – proseguendo nel gioco – che si è scelta una divisione che lascia scoperte celle, oppure che mette in condizione di non avere spazio necessario per soluzioni adiacenti. Nonostante questo, l’uomo è avvantaggiato dal poter vedere il problema, e quindi avere quantomeno un’idea delle proporzioni che ciascun rettangolo o quadrato dovranno avere. Non potendo replicare questa sensazione a livello macchina, dovremo necessariamente trovare un’altra strada per procedere.

Trattandosi di un gioco con un numero finito di soluzioni, esso si presta piuttosto bene all'automazione. Tuttavia, essendo un problema in parte grafico (o meglio, più agevolmente apprezzabile potendo osservare), la parte interessante dell'approccio al problema risiede in come poter rappresentare digitalmente la griglia di gioco e le combinazioni possibili, in modo che sia fruibile anche lato macchina. Inoltre, a partire da ciò, sarà utile valutare come generare e analizzare la validità delle soluzioni potenziali, scartando quelle inefficaci come in una sorta di lucchetto a combinazione, verso l'ottenimento dell'unica soluzione valida.

Nella speranza che possiate trovare interessante e stimolante il tema proposto, eccovi il link all'articolo:

[C#] Permutazioni nella risoluzione di uno Shikaku tramite bruteforcing (it-IT)

Buona lettura, e arrivederci a presto su queste pagine!
Emiliano Musso