Antonio Mario Caruso

Ho scritto un codice che risolva uno dato schema di sudoku ma il programma  gira sempre senza dare soluzione e senza andare in crash perchè ha disponibilità di memoria .
Non so in che modo controllare la solve che è la funzione principale. La solve è basata  su inserimenti consecutivi di valori  in ogni cella libera che soddisfano le regole del sudoku e quindi è uno schema risolutivo “poco intelligente”e sicuramente molto oneroso per il sistema.
il codice  è incompleto perchè manca la funzione per poter inserire  uno schema di sudoku da file ma è un aspetto secondario  perchè  ho fissatoo a priori una configurazione iniziale della matrice.
 

#include <stdio.h>
#include <stdbool.h>
int m[9][9]= { {4,0,0,0,0,0,0,0,0}, 
               {0,8,3,5,0,0,4,1,0},
               {0,7,0,6,0,0,0,2,0} ,
               {0,0,0,0,8,0,1,6,0},
               {0,0,0,2,0,6,0,0,0} ,
               {0,1,7,0,4,0,0,0,0},
               {0,5,0,0,0,9,0,4,0} ,
               {0,4,2,0,0,1,7,3,0} ,
               {0,0,0,0,0,0,0,0,0}};
 // visualizza griglia sudoku
void visualizza( void)
{
	for (int i=0; i<9; i++) {
		for (int j=0; j<9; j++)
			printf("%3d",m[i][j]);
		printf("n");
	}
	printf("n");
	return;
}
//restituisce true se la configuarazione della griglia è valida
bool presente_riga( int x, int riga)
{
	for (int i=0; i<9; i++){
		if( m[riga][i]== x)
			return true;
	}
	return false;
}
bool presente_colonna ( int x, int colonna )
{
	for (int i=0; i<9; i++){
		if ( m[i][colonna]==x )
			return true;
	}
	return false;
}
bool presente_quadrante (int x, int riga, int colonna )
{
	for (int i=0; i<3; i++)
		for (int j=0; j<3; j++) {
			int s = (riga/3)*3 + i;
			int t = (colonna/3)*3 + j;
			if ( m[s][t] == x)
				return true;
	}
	return false;
}
bool config_valida (int x, int riga, int colonna)
{
	if ( !presente_riga (x,riga) && !presente_colonna (x, colonna) && !presente_quadrante(x, riga, colonna))
		return true;
	return false;
}
//restituisce vero se ha risolto il sudoku
bool solve( void )
{
	int inserimenti = 0;
	bool libero = false; 	// variabile per sapere se esiste una cella libera
	int r =-1; int c=-1; 	// indici riga e colonna  libere
	//cerca r e c primi indici tali che  m[r,c]=0
	do {
		r++;
		c=-1;
		do {
			c++;
			if (m[r][c]==0) libero=true;
		} while (libero==false && c<8);
	} while (libero==false && r<9);
	//printf("ncella libera %d , %dn", r+1, c+1);
	//se è stata trovata una cella vuota inserisci un valore e richiama funzione se la config è valida
	if ( libero ) {
		for ( int x=1; x<=9; x++ ) { 	//prova a inserire nella cella ogni valore possibile poi controlla
			if ( config_valida ( x , r, c ) ) {
				m[r][c] = x ;				// se la config è valida inserisci l'elemento
				inserimenti++;   //printf("n inserito %d in %d, %dnn", x, r+1, c+1); visualizza();
				if (solve()) return true;  //se la chiamata ricorsiva torna true, torna true alla main
				else {
					m[r][c] = 0; //se l'inserimento fatto non porta alla soluzione riporta la cella a 0
					inserimenti--;   //printf("n cancellato %d in %d, %dnn", x, r+1, c+1);   visualizza ();
				}
			}	//se la config non è valida prova con il prox x
		}
		if ( inserimenti == 0) return false;	//se non è stato possibile inserire alcun valore in una cella libera c'è un errore
	}
	else return true;   //non ci sono più celle vuote -> finito! questa è l'ultima chiamata di solve
}
int main()
{
	//configurazione();
	printf("nschema inizialen");
	visualizza();
	if ( solve() ) {
		printf("nsudoku risolto!n");
		visualizza();
	}	else printf("nil sudoku non ammette soluzione");
	return 0;
}