Sudoku Solver in C++: risolutore sudoku con backtracking

Uno degli esercizi più utilizzati in ambito di programmazione e di algoritmi e strutture dati, è certamente il Sudoku Solver in C++ utilizzando la tecnica algoritmica di backtracking.

Supponiamo quindi di dover dare in input una griglia Sudoku 9×9 che al suo interno è divisa in ulteriori griglie 3×3.

Le semplici regole del gioco prevedono che dobbiamo usare all’interno di una stessa riga numeri compresi tra 1 e 9 senza ripetizioni e sappiamo anche che all’interno di una matrice 3×3 non ci debbano anche qui essere ripetizioni.

#include <iostream>
#define N 9
using namespace std;
int matrice[N][N] = {
   {3, 0, 6, 5, 0, 8, 4, 0, 0},
   {5, 2, 0, 0, 0, 0, 0, 0, 0},
   {0, 8, 7, 0, 0, 0, 0, 3, 1},
   {0, 0, 3, 0, 1, 0, 0, 8, 0},
   {9, 0, 0, 8, 6, 3, 0, 0, 5},
   {0, 5, 0, 0, 9, 0, 6, 0, 0},
   {1, 3, 0, 0, 0, 0, 2, 5, 0},
   {0, 0, 0, 0, 0, 0, 0, 7, 4},
   {0, 0, 5, 2, 0, 6, 3, 0, 0}
};
bool isPresentEiNcolonnaonna(int colonna, int num){ //controlla se un numero è già presente nella colonna
   for (int riga = 0; riga < N; riga++)
      if (matrice[riga][colonna] == num)
         return true;
   return false;
}
bool isPresentEiNriga(int riga, int num){ //controlla se un numero è già presente nella riga
   for (int colonna = 0; colonna < N; colonna++)
      if (matrice[riga][colonna] == num)
         return true;
   return false;
}
bool isPresentEiNquadratro(int boxStartRiga, int boxStartColonna, int num){
////controlla se un numero è già presente nel box 3x3
   for (int riga = 0; riga < 3; riga++)
      for (int colonna = 0; colonna < 3; colonna++)
         if (matrice[riga+boxStartRiga][colonna+boxStartColonna] == num)
            return true;
   return false;
}
void sudokuMatrice(){ //stampa a video la matrice risolta
   for (int riga = 0; riga < N; riga++){
      for (int colonna = 0; colonna < N; colonna++){
         if(colonna == 3 || colonna == 6)
            cout << " | ";
         cout << matrice[riga][colonna] <<" ";
      }
      if(riga == 2 || riga == 5){
         cout << endl;
         for(int i = 0; i<N; i++)
            cout << "---";
      }
      cout << endl;
   }
}
bool trovAspazIovuoto(int &riga, int &colonna){ //trova spazio vuoto
   for (riga = 0; riga < N; riga++)
      for (colonna = 0; colonna < N; colonna++)
         if (matrice[riga][colonna] == 0) //marked with 0 is empty
            return true;
   return false;
}
bool veRificApostoValido(int riga, int colonna, int num){
   //when item not found in colonna, riga and current 3x3 box
   return !isPresentEiNriga(riga, num) && !isPresentEiNcolonnaonna(colonna, num) && !isPresentEiNquadratro(riga - riga%3 ,
colonna - colonna%3, num);
}
bool solveSudoku(){
   int riga, colonna;
   if (!trovAspazIovuoto(riga, colonna))
      return true; //when all places are filled
   for (int num = 1; num <= 9; num++){ //valid numbers are 1 - 9
      if (veRificApostoValido(riga, colonna, num)){ //check validation, if yes, put the number in the matrice
         matrice[riga][colonna] = num;
         if (solveSudoku()) //recursively go for other rooms in the matrice
            return true;
         matrice[riga][colonna] = 0; //turn to unassigned space when conditions are not satisfied
      }
   }
   return false;
}
int main(){
   if (solveSudoku() == true)
      sudokuMatrice();
   else
      cout << "Non esistono soluzioni";
}