Advertisement
Szczepan86

Rozwiązywacz Sudoku

Apr 18th, 2020
597
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3.  
  4. using namespace std;
  5.  
  6. int rozmiar = 9;
  7. int dane[9][9];
  8.  
  9. void drukuj() {
  10.   for (int y=0; y<rozmiar; y++) {
  11.     for (int x=0; x<rozmiar; x++) {
  12.       if (dane[y][x] != 0) {
  13.         cout << dane[y][x] << " ";
  14.       } else {
  15.         cout << "_ ";
  16.       }
  17.     }
  18.     cout << endl;
  19.   }
  20.   cout << endl;
  21. }
  22.  
  23. bool weryfikujDane() {
  24.   for (int x=0; x<rozmiar; x++) {
  25.     for (int y=0; y<rozmiar; y++) {
  26.       if (dane[y][x] != 0) {
  27.  
  28.         // sprawdz czy w wierszu / kolumnie istnieje juz taka wartosc
  29.         int a = 0;
  30.         for (int i=0; i<rozmiar; i++) {
  31.           // sprawdz wiersz - spodziewamy sie tylko jednej identycznej wartosci
  32.           if (dane[y][x] == dane[y][i]) a++;
  33.           // sprawdz kolumne - spodziewamy sie tylko jednej identycznej wartosci
  34.           if (dane[y][x] == dane[i][x]) a++;
  35.         }
  36.         if (a > 2) return false;
  37.  
  38.         // określenie w której sekcji jesteśmy
  39.         int sX = x/3;
  40.         int sY = y/3;
  41.        
  42.         a = 0;
  43.         // sprawdz czy w danej sekcji istnieje podobna liczba
  44.         for (int i=sY*3; i<sY*3+3; i++) {
  45.           for (int j=sX*3; j<sX*3+3; j++) {
  46.             if (dane[y][x] == dane[i][j]) a++;
  47.           }
  48.         }
  49.         if (a > 1) return false;
  50.       }
  51.     }
  52.   }
  53.   return true;
  54. }
  55.  
  56. int main() {
  57.   fstream plik;
  58.   plik.open("bledne_dane.txt");
  59.   for (int i=0; i<rozmiar; i++) {
  60.     for (int j=0; j<rozmiar; j++) {
  61.       plik >> dane[i][j];
  62.     }
  63.   }
  64.   plik.close();
  65.  
  66.   drukuj();
  67.   if (weryfikujDane()) {
  68.     cout << "DANE OK" << endl;
  69.   } else {
  70.     cout << "DANE NOK" << endl;
  71.   }
  72.  
  73.   // wybierz komórkę (która ma wartość równą 0)
  74.   //int x = 0, y = 0;
  75.   string komenda;
  76.   int liczbaPustychMiejsc;
  77.   int liczbaUzupelnionychMiejsc;
  78.   do {
  79.     liczbaPustychMiejsc = 0;
  80.     liczbaUzupelnionychMiejsc = 0;
  81.     for (int x=0; x<rozmiar; x++) {
  82.       for (int y=0; y<rozmiar; y++) {
  83.         if (dane[y][x] == 0) {
  84.           // ustaw liczby od 1 .. 9 jako możliwe
  85.           bool dostepneLiczby[rozmiar+1];
  86.           for (int i=0; i<rozmiar+1; i++) {
  87.             dostepneLiczby[i] = true;
  88.           }
  89.           // wykreślamy wszystkie liczby które istnieją w tym samym wierszu
  90.           // lub kolumnie
  91.           for (int i=0; i<rozmiar; i++) {
  92.             dostepneLiczby[dane[y][i]] = false;
  93.             dostepneLiczby[dane[i][x]] = false;
  94.           }
  95.  
  96.           // określenie w której sekcji jesteśmy
  97.           int sX = x/3;
  98.           int sY = y/3;
  99.          
  100.           // wykreślamy wszystkie liczby które istnieją w tej samej sekcji
  101.           for (int i=sY*3; i<sY*3+3; i++) {
  102.             for (int j=sX*3; j<sX*3+3; j++) {
  103.               dostepneLiczby[dane[i][j]] = false;
  104.             }
  105.           }
  106.  
  107.           // sprawdz liczbe mozliwych kombinacji
  108.           int liczbaKombinacji = 0;
  109.           int mozliwaWartosc = 0;
  110.           for (int i=0; i<rozmiar+1; i++) {
  111.             if (dostepneLiczby[i]) {
  112.               liczbaKombinacji++;
  113.               mozliwaWartosc = i;
  114.             }
  115.           }
  116.  
  117.           // zaktualizuj dane jeśli liczba kombinacji = 1
  118.           if (liczbaKombinacji == 1) {
  119.             dane[y][x] = mozliwaWartosc;
  120.             liczbaUzupelnionychMiejsc++;
  121.           } else {
  122.             liczbaPustychMiejsc++;
  123.           }
  124.         }
  125.       }
  126.     }
  127.     drukuj();
  128.     //cout << "Czy powtórzyć zgadywanie? (t/n)";
  129.     //cin >> komenda;
  130.   } while (liczbaPustychMiejsc > 0 && liczbaUzupelnionychMiejsc > 0);
  131. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement