1  #include <iostream>
  2  
  3  using namespace std;
  4  
  5  // N*N-es mátrix
  6  #define N 9
  7  
  8  // Sudoku "tábla" kiírása
  9  void kiir(int matrix[N][N])
 10  {
 11      for (int i = 0; i < N; i++)
 12      {
 13          for (int j = 0; j < N; j++)
 14              cout << matrix[i][j] << " ";
 15          cout << endl;
 16      }
 17  }
 18  
 19  // Annak vizsgálata, hogy az adott szám beilleszthető-e az adott sor-oszlop helyre
 20  bool Rendben(int sudoku[N][N], int sor, int oszlop, int szam)
 21  {
 22  
 23      // Ellenőrizzük, hogy az adott sorban szerepel-e már a beírni kívánt szám
 24      // Ez esetben hamis értéket adunk vissza - return false
 25      for (int x = 0; x < N; x++)
 26          if (sudoku[sor][x] == szam)
 27              return false;
 28  
 29      // Ellenőrizzük, hogy az adott oszlopban szerepel-e már a beírni kívánt szám
 30      // Ez esetben is hamis értéket adunk vissza - return false
 31      for (int x = 0; x < N; x++)
 32          if (sudoku[x][oszlop] == szam)
 33              return false;
 34  
 35      // Megnézzük, hogy az érintett 3x3-as résztáblában szerepel-e már a beírni kívánt szám
 36      // Ez esetben is hamis értéket adunk vissza - return false
 37      int rt_sor = sor - sor % 3,               // Résztábla kezdősorának meghatározása
 38          rt_oszlop = oszlop - oszlop % 3;      // Résztábla kezdőoszlopának meghatározása
 39  
 40      for (int i = rt_sor; i < rt_sor + 3; i++)
 41          for (int j = rt_oszlop; j < rt_oszlop + 3; j++)
 42              if (sudoku[i][j] == szam)
 43                  return false;
 44  
 45      return true;   // Ha minden rendben volt, igaz értéket adunk vissza
 46  }
 47  
 48  /* A részlegesen már kitöltött sudoku-tábla teljes kitöltése */
 49  bool Sudoku_feltoltes(int sudoku[N][N], int sor, int oszlop)
 50  {
 51      // Ha a sornak és oszlopoknak is a végére értünk leállítjuk a rekurziót - return true
 52      if (sor == N - 1 && oszlop == N)
 53          return true;
 54  
 55      /* Ha egy sor elemeivel (oszlopok) végeztünk, menjünk a következő sorra,
 56         oszlopot pedig megint az elejére állítjuk */
 57      if (oszlop == N) {
 58          sor++;
 59          oszlop = 0;
 60      }
 61  
 62      /* Ellenőrizzük, hogy már kitöltött pozíción vagyunk-e,
 63         ha igen, menjünk egy oszloppal jobbra és rekurzió... */
 64      if (sudoku[sor][oszlop] > 0)
 65          return Sudoku_feltoltes(sudoku, sor, oszlop + 1);
 66  
 67      for (int szam = 1; szam <= N; szam++)
 68      {
 69  
 70          // Elhelyezhető-e az adott szám az adott sor-oszlop pozíción
 71          if (Rendben(sudoku, sor, oszlop, szam))
 72          {
 73              sudoku[sor][oszlop] = szam;
 74  
 75              // Térjünk rá a következő oszlop vizsgálatára - rekurzió
 76              if (Sudoku_feltoltes(sudoku, sor, oszlop + 1))
 77                  return true;
 78          }
 79  
 80          // Ha nem találtunk megoldást, állítsuk ismét üresre az adott helyet a táblában
 81          sudoku[sor][oszlop] = 0;
 82      }
 83      return false;
 84  }
 85  
 86  int main()
 87  {
 88      // Kezdeti állapot megadása
 89      int sudoku[N][N] = {
 90                      { 5, 0, 0, 0, 4, 0, 7, 0, 3 },
 91                      { 0, 4, 0, 6, 2, 8, 0, 0, 0 },
 92                      { 0, 0, 2, 0, 0, 0, 0, 0, 0 },
 93                      { 0, 0, 0, 5, 0, 0, 4, 9, 7 },
 94                      { 0, 0, 0, 0, 7, 0, 0, 0, 0 },
 95                      { 7, 1, 4, 0, 0, 3, 0, 0, 0 },
 96                      { 0, 0, 0, 0, 0, 0, 6, 0, 0 },
 97                      { 0, 0, 0, 9, 6, 2, 0, 5, 0 },
 98                      { 8, 0, 1, 0, 3, 0, 0, 0, 9 }
 99      };
100  
101      if (Sudoku_feltoltes(sudoku, 0, 0))
102          kiir(sudoku);
103      else
104          cout << "nem találtam megoldást... " << endl;
105  
106      return 0;
107  }