Sudoku for geeks

Quest'oggi parliamo di algoritmi per risolvere il sudoku. Personalmente questo gioco di logica inventato nel '700 nientepopodimenoché da Eulero ma divenuto noto a livello internazionale soltanto a partire dal 2005 non mi ha mai entusiasmata... mentre le sue implicazioni informatiche e algoritmiche sono un altro discorso! ;-) Ti propongo quindi la traduzione delle procedure descritte nell'articolo Sudoku | Backtracking-7 pubblicato su GeeksforGeeks.

Dato un array bidimensionale 9×9 parzialmente riempito grid[9][9], l'obiettivo è quello di assegnare delle cifre (da 1 a 9) alle celle vuote in modo tale che ogni riga, colonna e sottogriglia di dimensioni 3×3 contenga esattamente un'istanza delle cifre da 1 a 9.

Si consiglia di risolverlo prima su "PRACTICE", prima di passare alla soluzione [ma io ovviamente vado dritta al sodo ;-) NdC].

Algoritmo ingenuo

L'algoritmo ingenuo consiste nel generare tutte le possibili configurazioni di numeri da 1 a 9 per riempire le celle vuote. Prova ogni configurazione una per una fino a trovare la configurazione corretta.

Algoritmo di backtracking

Come tutti gli altri problemi di backtracking, possiamo risolvere il sudoku assegnando uno ad uno i numeri alle celle vuote. Prima di assegnare un numero, controlliamo se è sicuro assegnarlo. In pratica controlliamo che lo stesso numero non sia presente nella riga corrente, nella colonna corrente e nella sottogriglia 3×3 corrente. Dopo aver controllato che sia sicuro, assegniamo il numero e controlliamo in modo ricorsivo se questa assegnazione porta a una soluzione o meno. Se l'assegnazione non porta a una soluzione, proviamo il numero successivo per la cella vuota corrente. E se nessuno dei numeri (da 1 a 9) porta a una soluzione, restituiamo FALSO.

Trovare riga, colonna di una cella non assegnata
Se non ce n'è nessuna, restituire VERO
Per le cifre da 1 a 9
   a) Se non vi è alcun conflitto per la cifra in riga, colonna
      assegnare la cifra a riga, colonna e provare ricorsivamente a riempire il resto della griglia
   b) Se la ricorsione ha esito positivo, restituire VERO
   c) Altrimenti, rimuovere la cifra e provarne un'altra
Se tutte le cifre sono state provate e nessuna ha funzionato, restituire FALSO

[Mi spiace per le righe che "sconfinano", ho usato il tag <nobr> per evitare di andare a capo, e volendo mantenere una formattazione decente dovrei rivoluzionare il layout del blog ma adesso non ci penso nemmeno]
In calce all'articolo è riportata l'implementazione dell'algoritmo nei linguaggi C++, C, Java, Python e C# per stampare in output la griglia riempita completamente.