fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. constexpr int maksN = 9;
  5. int plansza[maksN + 10][maksN + 10];
  6. int podstawa[maksN + 10][maksN + 10][maksN + 10];
  7. int odwiedzone[maksN + 10][maksN + 10][maksN + 10];
  8.  
  9. void krzyz(pair<int, int> biezaca, int i) {
  10.     int kolumna = (biezaca.second - 1) / 3, wiersz = (biezaca.first - 1) / 3;
  11.     kolumna *= 3, wiersz = 3 * wiersz + 1;
  12.     for (int j = kolumna + 1; j <= kolumna + 3; j++) 
  13.         odwiedzone[wiersz][j][i] = true; 
  14.  
  15.     wiersz++;
  16.  
  17.     for (int j = kolumna + 1; j <= kolumna + 3; j++) 
  18.         odwiedzone[wiersz][j][i] = true;
  19.  
  20.     wiersz++;
  21.  
  22.     for (int j = kolumna + 1; j <= kolumna + 3; j++) 
  23.         odwiedzone[wiersz][j][i] = true;
  24.     for (int j = 1; j <= 9; j++) 
  25.         odwiedzone[j][biezaca.second][i] = true;
  26.     for (int j = 1; j <= 9; j++) 
  27.         odwiedzone[biezaca.first][j][i] = true;
  28. }
  29.  
  30. void przywroc(pair<int, int> biezaca, int i) {
  31.     int kolumna = (biezaca.second - 1) / 3, wiersz = (biezaca.first - 1) / 3;
  32.     kolumna *= 3, wiersz = 3 * wiersz + 1;
  33.     for (int j = kolumna + 1; j <= kolumna + 3; j++) 
  34.         odwiedzone[wiersz][j][i] = false;
  35.  
  36.     wiersz++;
  37.  
  38.     for (int j = kolumna + 1; j <= kolumna + 3; j++) 
  39.         odwiedzone[wiersz][j][i] = false;
  40.     wiersz++;
  41.     for (int j = kolumna + 1; j <= kolumna + 3; j++) 
  42.         odwiedzone[wiersz][j][i] = false;
  43.     for (int j = 1; j <= 9; j++)
  44.         if (j != biezaca.first)
  45.         odwiedzone[j][biezaca.second][i] = false;
  46.     for (int j = 1; j <= 9; j++) 
  47.         odwiedzone[biezaca.first][j][i] = false;
  48. }
  49.  
  50. bool sudoku() {
  51.     pair<int, int> biezaca = {-1, -1};
  52.  
  53.     int maks_mozliwosci = 0;
  54.  
  55.     for (int i = 1; i <= 9; i++) {
  56.         for (int j = 1; j <= 9; j++) {
  57.             if (plansza[i][j] < 1) 
  58.             {
  59.                 int mozliwosci = 0;
  60.                 for (int k = 1; k <= 9; k++)
  61.                     if (podstawa[i][j][k] || odwiedzone[i][j][k]) mozliwosci++;
  62.  
  63.                 if (maks_mozliwosci < mozliwosci) 
  64.                 {
  65.                     maks_mozliwosci = mozliwosci;
  66.                     biezaca = {i, j};
  67.                 }
  68.             }
  69.         }
  70.     }
  71.     if (biezaca.first < 0)
  72.         return true;
  73.     for (int i = 1; i <= 9; i++) {
  74.         if (odwiedzone[biezaca.first][biezaca.second][i] || podstawa[biezaca.first][biezaca.second][i])
  75.             continue; 
  76.         bool warunek = true;
  77.         int kolumna = (biezaca.second - 1) / 3, wiersz = (biezaca.first - 1) / 3;
  78.         kolumna *= 3, wiersz = 3 * wiersz + 1;
  79.         for (int j = kolumna + 1; j <= kolumna + 3; j++)
  80.             if ((biezaca != make_pair(wiersz, j)) && plansza[wiersz][j] == i)
  81.                 warunek = false;
  82.  
  83.         wiersz++;
  84.  
  85.         for (int j = kolumna + 1; j <= kolumna + 3; j++)
  86.             if ((biezaca != make_pair(wiersz, j)) && plansza[wiersz][j] == i) warunek = false;
  87.  
  88.         wiersz++;
  89.  
  90.         for (int j = kolumna + 1; j <= kolumna + 3; j++)
  91.             if ((biezaca != make_pair(wiersz, j)) && plansza[wiersz][j] == i) warunek = false;
  92.  
  93.         for (int j = 1; j <= 9; j++)
  94.             if (j != biezaca.first && plansza[j][biezaca.second] == i) warunek = false;
  95.  
  96.         for (int j = 1; j <= 9; j++)
  97.             if (j != biezaca.second && plansza[biezaca.first][j] == i)
  98.                 warunek = false;
  99.  
  100.         if (!warunek) continue;
  101.  
  102.         plansza[biezaca.first][biezaca.second] = i;
  103.         krzyz(biezaca, i);
  104.  
  105.         if (sudoku()) return true;
  106.  
  107.         plansza[biezaca.first][biezaca.second] = 0; przywroc(biezaca, i);
  108.     }
  109.     return false;
  110. }
  111.  
  112. void przygotuj(pair<int, int> biezaca, int i) {
  113.     int kolumna = (biezaca.second - 1) / 3, wiersz = (biezaca.first - 1) / 3;
  114.     kolumna *= 3, wiersz = 3 * wiersz + 1;
  115.  
  116.     for (int j = kolumna + 1; j <= kolumna + 3; j++)
  117.         podstawa[wiersz][j][i] = true;
  118.  
  119.     wiersz++;
  120.  
  121.     for (int j = kolumna + 1; j <= kolumna + 3; j++)
  122.         podstawa[wiersz][j][i] = true;
  123.  
  124.     wiersz++;
  125.  
  126.     for (int j = kolumna + 1; j <= kolumna + 3; j++) podstawa[wiersz][j][i] = true;
  127.     for (int j = 1; j <= 9; j++) podstawa[j][biezaca.second][i] = true;
  128.     for (int j = 1; j <= 9; j++) podstawa[biezaca.first][j][i] = true;
  129. }
  130.  
  131. int main() {
  132.     ios_base::sync_with_stdio(0);
  133.     cin.tie(0);
  134.     cout.tie(0);
  135.     string s;
  136.     for (int i = 1; i <= 9; i++) {
  137.         for (int j = 1; j <= 9; j++) 
  138.         {
  139.             cin >> s;
  140.             if (s[0] == '*')
  141.                 plansza[i][j] = 0;
  142.             else
  143.                 plansza[i][j] = s[0] - '0';
  144.         }
  145.     }
  146.     for (int i = 1; i <= 9; i++) {
  147.         for (int j = 1; j <= 9; j++)
  148.             if (plansza[i][j] > 0)
  149.                 przygotuj(make_pair(i, j), plansza[i][j]);
  150.     }
  151.  
  152.     sudoku();
  153.  
  154.     for (int i = 1; i <= 9; i++) {
  155.         for (int j = 1; j <= 9; j++)
  156.             cout << plansza[i][j] << ' ';
  157.         cout << endl;
  158.     }
  159.     return 0;
  160. }
  161.  
Success #stdin #stdout 0.01s 5392KB
comments (?)
stdin
copy 
* 7 * * 8 1 * * *
* 2 * 5 * * * * 9
5 * * * * * * * 1
* 6 * * 3 8 2 * *
* * * 2 * 5 * * *
* * 2 9 7 * * 3 *
2 * * * * * * * 5
7 * * * * 9 * 1 *
* * * 7 2 * * 6 *
stdout
copy 
6 7 9 3 8 1 5 2 4 
4 2 1 5 6 7 3 8 9 
5 3 8 4 9 2 6 7 1 
9 6 4 1 3 8 2 5 7 
3 8 7 2 4 5 1 9 6 
1 5 2 9 7 6 4 3 8 
2 9 6 8 1 3 7 4 5 
7 4 3 6 5 9 8 1 2 
8 1 5 7 2 4 9 6 3
https://ideone.com/0Sdd0e
language:
C++ (gcc 8.3)
created:
311 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!