Sudoku: Esempio di backtracking. Il codice sorgente in linguaggio C.
Scaricare il codice sorgente

 • Codice
 • Obiettivo
 • Esecuzione
 • Principio
 • Commenti
 • Compilazione
 • Generalità


/************
SUDOKU
BACKTRACKING
Febbraio 2013
*************/


#include <stdio.h>
#include <string.h>
/* Dimensione del lato dei piccoli quadrati. */
#define MIN 3
/* Dimensione del lato del grande quadrato. */
#define MAS 9
/* Codice d'uscita delle funzioni. */
#define FALSO 0
#define VERO 1

char griglia[MAS][MAS]; /* la griglia */
long int g_conta_test; /* contatore dei test */
int g_flag_affissione; /* bandiera d'opzione di affissione dell'opzione -a */
/********/
int main(int argc, char *argv[]);
int parametro_affissione(char t[]);
/**** INSERIMENTI E CONTROLLI ****/
int inserimento_griglia(void);
int inserimento_una_linea(int linea);
int verif_inserimento_griglia(void);
int verif_inserimento_linee(void);
int verif_inserimento_una_linea(int linea);
int verif_inserimento_colonne(void);
int verif_inserimento_una_colonna(int col);
int verif_inserimento_quadrati(void);
int verif_inserimento_un_quadrato(int quadrato);
void trasferimento_quadrato(char tamp[], int quadrato);
/**** RISOLUZIONE ****/
void risolvere(void);
int casella_dispo_numero(int numero, int linea, int col);
void trasferimento_quadato_3_di_3(char tamp[], int linea, int col);
/**** DIVERSI ****/
void affissione_griglia_attesa(void);
void affissione_griglia(void);
void affissione_stringa(int lunghezza);
int griglia_finita(void);
void attesa(void);

/******/
int main(int argc, char *argv[])
/******/
{
.   /* Opzione di affissione nella funzione risolvere. */
.   g_flag_affissione = ((argc >= 2) && (parametro_affissione(argv[1])));
.   /**********/
.   printf("\n******* SUDOKU *******\n\n");
.   printf("l'opzione sudoku -a mostra la risoluzione casella per casella.\n\n");
.   printf("Inserite %d linee di %d cifre.\n", MAS, MAS);
.   printf("Le cifre possono essere separate da qualsiasi caratteri.\n");
.   printf("Inserite uno 0 per ogni casella vuota.\n");
.   printf("Per uscire dal programma, inserite la lettera U.\n\n");
.   while (inserimento_griglia()) {
.   .   g_conta_test = 0;
.   .   risolvere();
.   .   affissione_griglia();
.   .   if (! griglia_finita()) printf("Problema sudoku erroneo...\n");
.   .   printf("Test: %ld\n\n", g_conta_test);
.   }/* end while */
.   printf("\n");
.   return 0;
}

/**********************/
int parametro_affissione(char t[])
/**********************/
{
.   /* Rinvio VERO se l'utente ha inserito un opzione di affissione:
.   a, A, /a , /A , -a , -A ecc... Altrimenti rinvio FALSO */

.   char param;
.   if (strlen(t) == 1) param = t[0];
.   else if (strlen(t) == 2) param = t[1];
.   else param = 0;
.   return ((param == 'A') || (param == 'a'));
}/* end parametro_affissione */

/*********************************/
/**** INSERIMENTI E CONTROLLI ****/
/*********************************/

/*********************/
int inserimento_griglia(void)
/*********************/
{/* L'utente inserisce 9 linee di 9 cifre. */
.   int linea;
.   printf("Inserite vostra griglia sudoku:\n");
.   while (VERO){
.   .   for (linea = 0; linea < MAS; linea++){
.   .   .   if (! inserimento_una_linea(linea)) return (FALSO);
.   .   }/* end for */
.   .   printf("\nIl vostro problema sudoku:\n");
.   .   affissione_griglia();
.   .   if (verif_inserimento_griglia()) return(VERO);
.   .   else printf("\n");
.   }/* end while */
}/* inserimento_griglia */

/***********************/
int inserimento_una_linea(int linea)
/***********************/
{
/* L'utente deve inserire una linea
di 9 cifre separati o no da caratteri.
Solo le prime 9 cifre saranno prese in considerazione.
Il più pratico: Utilizzate il tastierino numerico e
inserire un punto ogni 3 cifre. Esempio: 103.006.709
Evitare di utilizzare gets () a causa degli tamponi troppo pieno.
Altrimenti ricordarsi di svuotare interamente lo buffer. */

.   int c, i;
.   int col = 0;
.   int result = VERO;
.   /* Riduzione a zero delle caselle della linea. */
.   for (i = 0; i < MAS; i++) {
.   .   griglia[linea][i] = 0;
.   }/* for */
.   /*******/
.   printf("Linea %d: ", linea+1);
.   while(VERO){
.   .   c = fgetc(stdin);
.   .   if (c == feof(stdin) || c == 0x0A) return result;
.   .   else if ((c == 'U') || (c == 'u')) result = FALSO;
.   .   /* Trasferimento dell'inserimento nelle caselle della linea. */
.   .   else if ( (result) && (col < MAS) && (c >= '0') && (c <= '9')) {
.   .   .   griglia[linea][col++] = c-48;
.   .   }/*end if */
.   }/* end while */
}/*end inserimento_una_linea */

/***************************/
int verif_inserimento_griglia(void)
/***************************/
{/* Verifica se no di doppione nella griglia sudoku. */
.   int result = VERO;
.   if (! verif_inserimento_linee()) result = FALSO;
.   if (! verif_inserimento_colonne()) result = FALSO;
.   if (! verif_inserimento_quadrati()) result = FALSO;
.   return result;
}/* end verif_inserimento_griglia */

/*************************/
int verif_inserimento_linee(void)
/*************************/
{/* Verifica se no di doppione nelle linee. */
.   int linea;
.   int result = VERO;
.   for (linea = 0; linea < MAS; linea++) {
.   .   if (! verif_inserimento_una_linea(linea)) result = FALSO;
.   }/* end for */
.   return result;
}/* end verif_inserimento_linee */

/*****************************/
int verif_inserimento_una_linea(int linea)
/*****************************/
{/* Verifica se no di doppione nella linea. */
.   int i,j;
.   for (i = 0; i < MAS-1; i++) {
.   .   if ( griglia[linea][i] == 0 ) continue;
.   .   for (j = i+1; j < MAS; j++) {
.   .   .   if (griglia[linea][i] == griglia[linea][j]) {
.   .   .   .   printf("Errore linea %d: Cifre uguali.\n", linea+1);
.   .   .   .   return FALSO;
.   .   .   }/* end if */
.   .   }/* end for j */
.   }/* end for i */
.   return VERO;
}/* end verif_inserimento_una_linea */

/***************************/
int verif_inserimento_colonne(void)
/***************************/
{/* Verifica se no di doppione nelle colonne. */
.   int col;
.   int result = VERO;
.   for (col = 0; col < MAS; col++) {
.   .   if (! verif_inserimento_una_colonna(col)) result = FALSO;
.   }/* end for */
.   return result;
}/* end verif_inserimento_colonne */

/*******************************/
int verif_inserimento_una_colonna(int col)
/*******************************/
{/* Verifica se no di doppione nella colonna. */
.   int i, j;
.   for (i = 0; i < MAS-1; i++) {
.   .   if ( griglia[i][col] == 0 ) continue;
.   .   for (j = i+1; j < MAS; j++) {
.   .   .   if (griglia[i][col] == griglia[j][col]) {
.   .   .   .   printf("Errore colonna %d: Cifre uguali.\n", col+1);
.   .   .   .   return FALSO;
.   .   .   }/* end if */
.   .   }/* end for j */
.   }/* end for i */
.   return VERO;
}/* end verif_inserimento_una_colonna */

/****************************/
int verif_inserimento_quadrati(void)
/****************************/
{/* Verifica se no di doppione nei quadrati di 3 x 3. */
.   int quadrato;
.   int result = VERO;
.   for (quadrato = 0; quadrato < MAS; quadrato++) {
.   .   if (! verif_inserimento_un_quadrato(quadrato)) result = FALSO;
.   }/* end for */
.   return result;
}/* end verif_inserimento_quadrati */

/*******************************/
int verif_inserimento_un_quadrato(int quadrato)
/*******************************/
{/* Verifica se no di doppione nel quadrato di 3 x 3. */
.   char tamp[MAS+10];
.   int i, j;
.   trasferimento_quadrato(tamp, quadrato);
.   for (i = 0; i < MAS-1; i++) {
.   .   if (tamp[i] == 0 ) continue;
.   .   for (j = i+1; j < MAS; j++) {
.   .   .   if (tamp[i] == tamp[j]) {
.   .   .   .   printf("Errore quadrato %d: Cifre uguali.\n", quadrato+1);
.   .   .   .   return FALSO;
.   .   .   }/* end if */
.   .   }/* end for j */
.   }/* end for i */
.   return VERO;
}/* end verif_inserimento_un_quadrato */

/*************************/
void trasferimento_quadrato(char tamp[], int quadrato)
/*************************/
{/* Trasferimento il quadrato 3 x 3 in una matrice unidimensionale. */
.   int i,j, x,y,z;
.   x = (((quadrato) % MIN)*MIN);
.   y = (((quadrato+MIN) / MIN)*MIN)-MIN;
.   z = 0;
.   for (j = y; j < y+MIN; j++) {
.   .   for (i = x; i < x+MIN; i++) {
.   .   .   tamp[z++] = griglia[j][i];
.   .   }/* end for i */
.   }/* end for j */
}/* end trasferimento_quadrato */

/*********************/
/**** RISOLUZIONE ****/
/*********************/

/************/
void risolvere(void)
/************/
{/* Attenzione, funzione ricorsiva... */
.   int linea, col, numero, num_tamp;
.   for (linea = 0; linea < MAS; linea++) {
.   .   for (col = 0; col < MAS; col++) {
.   .   .   if (griglia[linea][col]) continue;
.   .   .   for (numero = 1; numero <= MAS; numero++) {
.   .   .   .   if (! casella_dispo_numero(numero, linea, col)) continue;
.   .   .   .   num_tamp = griglia[linea][col];
.   .   .   .   griglia[linea][col] = numero;
.   .   .   .   g_conta_test++;
.   .   .   .   if (g_flag_affissione) affissione_griglia_attesa();
.   .   .   .   risolvere();
.   .   .   .   if (griglia_finita()) return;
.   .   .   .   /* Per vedere tutte le soluzioni
.   .   .   .   delle griglie sudoku a soluzioni multiple
.   .   .   .   mettere in rem la linea della cima e
.   .   .   .   ritirare il rem della linea del sotto. */

.   .   .   .   /* if (griglia_finita()) affissione_griglia_attesa(); */
.   .   .   .   griglia[linea][col] = num_tamp;
.   .   .   }/* end for numero */
.   .   .   return;
.   .   }/* end for col */
.   }/* end for linea */
.   return;
}/* end risolvere */

/**********************/
int casella_dispo_numero(int numero, int linea, int col)
/**********************/
{
/* Prova se il numero è già messo
in la linea, o in la colonna, o in il quadrato di 3 X 3
afferente alla casella indicata da linea, col. */

.   char tamp[MAS+10];
.   int i;
.   /* Se il numero è utilizza nella linea, rinvio FALSO. */
.   for (i = 0; i < MAS; i++) if (griglia[linea][i] == numero) return(FALSO);
.   /* Se il numero è utilizza nella colonna, rinvio FALSO. */
.   for (i = 0; i < MAS; i++) if (griglia[i][col] == numero) return(FALSO);
.   /* Se il numero è utilizza nel quadrato, rinvio FALSO */
.   trasferimento_quadato_3_di_3(tamp, linea, col);
.   for (i = 0; i < MAS; i++) if (tamp[i] == numero) return (FALSO);
.   /* Dunque il numero è disponibile per la casella. */
.   return(VERO);
}/* end casella_dispo_numero */

/*******************************/
void trasferimento_quadato_3_di_3(char tamp[], int linea, int col)
/*******************************/
/* Trasferimento il quadrato di 3 X 3 afferente
ad una casella in una matrice unidimensionale. */

{
.   int i, j, k;
.   while ((linea % MIN) != 0) linea--;
.   while ((col % MIN) != 0) col--;
.   k = 0;
.   for (j = linea; j < linea+MIN; j++) {
.   .   for (i = col; i < col+MIN; i++) {
.   .   .   tamp[++k] = griglia[j][i];
.   .   }/* end for i */
.   }/* end for j */
}/* end trasferimento_quadato_3_di_3 */

/*****************/
/**** DIVERSO ****/
/*****************/

/****************************/
void affissione_griglia_attesa(void)
/****************************/
{/* Mostra la griglia di sudoku con messa in attesa del tasto entra. */
.   affissione_griglia();
.   printf("%ld, Tasto entra per il seguito...", g_conta_test);
.   attesa();
}/* end affissione_griglia_attesa */

/*********************/
void affissione_griglia(void)
/*********************/
{/* Mostra la griglia di sudoku */
.   int linea, col;
.   for (linea = 0; linea < MAS; linea++) {
.   .   for (col = 0; col < MAS; col++) {
.   .   .   printf(" %1d ", griglia[linea][col]);
.   .   .   if ( ((col % MIN) == MIN-1) && (col < MAS-1) ) {
.   .   .   .   printf(" | ");
.   .   .   }
.   .   }/* end for col */
.   .   printf("\n");
.   .   if ( ((linea % MIN) == MIN-1) && (linea < MAS-1) ) {
.   .   .   affissione_stringa(33);
.   .   }
.   }/* end for linea */
.   printf("\n");
}/* end affissione_griglia */

/*********************/
void affissione_stringa(int lunghezza)
/*********************/
{/* Affissione una stringa di carattere asterisco. */
.   int i;
.   for (i = 1; i <= lunghezza; i++) {
.   .   printf("*");
.   }
.   printf("\n");
}/* end affissione_stringa */

/****************/
int griglia_finita(void)
/****************/
/* Prova se la griglia sudoku è finita.
Rinvio VERO se la griglia è finita, altrimenti rinvio FALSO.
Comincia con la fine della griglia. */

{
.   int linea, col;
.   for (linea = MAS-1; linea >= 0; linea--) {
.   .   for (col = MAS-1; col >= 0; col--) {
.   .   .   if (griglia[linea][col] == 0 ) {
.   .   .   .   return FALSO;
.   .   .   }
.   .   }/* end for col */
.   }/* end for linea */
.   return VERO;
}/* end griglia_finita */

/*********/
void attesa(void)
/*********/
{/* Attesa del tasto entra alla tastiera. */
.   char c;
.   while(VERO){
.   .   c = fgetc(stdin);
.   .   if (c == feof(stdin) || c == 0x0A) return;
.   }/* end while */
}/* end attesa */



 Obiettivo 

L'obiettivo di questo programma è di risolvere un problema sudoku in backtracking.
Il cuore di questo metodo è la funzione ricorsiva risolvere() di 20 linee circa accompagnata dalle 5 linee della funzione casella_dispo_numero().
Queste 25 linee sono il cuore del sistema, il resto è soprattutto riservato alla battitura ed alla verifica di questa.


 Esecuzione 

Il programma funziona in modalità di comando.
  >sudoku.exe (sotto Windows emulazione DOS).
  $./sudoku (sotto linux).

L'utente inserisce la griglia sudoku da risolvere.
La battitura è stata ridotta alla sua semplice espressione. Si convalidano 9 linee di 9 cifre. Ogni cifra può essere separata da uno o più caratteri. Esempio più semplice in tastierino numerico:
  060.104.050 [ Entra ]
  008.305.600 [ Entra ] ecc...
L'utente inserisce uno zero per le caselle vuote. [Ctrl C] o una linea che contiene la lettera "u" fa lasciare il programma.

Il software visualizza il problema sudoku, verifica la coerenza di quest'ultimo, fa il trattamento e mostra la soluzione. Il tempo di trattamento è quasi istantaneo per le griglie che accettano una o più soluzioni. Il tempo d'esecuzione può durare molti minuti su griglie non aventi alcuna soluzione.

L'opzione [ -a ] visualizza tutta la griglia ad ogni incarico di un numero ad una casella. Basta entrare il nome del programma seguito da uno spazio e dall'espressione "-a".
  >sudoku.exe -a (sotto Windows)
  $./sudoku -a (sotto linux)
In seguito l'utente colpisce il tasto entra o mantiene questa sostenuta per continuare il trattamento e la visualizzazione della risoluzione passo per passo.


 Principio di risoluzione 

Metodo ricorsivo:
La funzione risolvere() cerca la prima casella libera. Quindi la casella libera cerca il prossimo numero disponibile come soluzione.
Se c'è un numero di disponibile:
 • Il numero è destinato alla casella.
 • La funzione si chiama essa anche, impilamento. Dunque il programma passerà alla casella libera seguente.
Altrimenti:
 • La funzione ritorna su essa anche, disimpilamento. Dunque il programma passerà alla casella libera precedente, che ricercherà il prossimo numero disponibile seguente.


 Commenti 

Il programma risolve:
 • Qualsiasi problema sudoku corretto e completo, cioè accettando soltanto una soluzione unica.
 • Qualsiasi problema sudoku corretto ed incompleto, anche una griglia vuota, cioè che accetta molte soluzioni possibili.
Modificando due linee nella funzione risolvere(), vedere i rem, il programma può ricercare il seguito delle soluzioni possibili afferenti al problema sudoku.


 Compilazione 

Compilare in modo C. è inutile compilare in c++.

Questo programma è stato compilato e provato con gcc sotto Linux e sotto Windows.
Esempio di comando di compilazione sotto Windows:
gcc -Wall sudoku.c -o sudoku.exe

Esempio di comando di compilazione sotto Linux:
gcc -Wall sudoku.c -o sudoku

Vi consigliamo il comando seguente:
gcc -Wall -O3 -s -ansi -pedantic sudoku.c -o sudoku
  -Wall : Messaggio di allarme, esempio una variabile non utilizzata.
  -O3 : Ottimizzazione del codice per la velocità d'esecuzione. La dimensione del codice generato è più grande. La durata d'esecuzione è più rapida e può essere divisa per cinque, secondo i casi.
  -s : Elimina il codice di debug dunque quest'ultimo sarà più breve.
  -ansi et -pedantic : Verifica l'uniformazione del codice ed aumenta così la portabilità.

Per un massimo di standardizzazione solo le funzioni standard: printf(), fgetc() e strlen() sono utilizzati.


 Generalità 

Il sudoku si basa sui principi della « programmazione con vincoli », ciò implica che la sua risoluzione interessa molto gli informatici.

La programmazione a vincoli è diventata indispensabile per gestire molti problemi complessi nella ricerca e nell'industria. Ad esempio:
 • Sviluppare classi orari in una scuola.
 • Migliorare gli itinerari di un insieme di aerei di linea.
 • Ottimizzare il percorso di molti veicoli di consegna.
 • Progettare la produzione di un seguito di prodotti in una fabbrica.
 • Dividere le bande occupate tra i server del web.

La risoluzione di un sudoku rappresenta un esempio-tipo della programmazione a vincoli. È per questo che è studiata molto presto come esempi di esercizi pedagogici in analisi ed in programmazione.