STANAANDREY

sudoku solver

Oct 18th, 2020 (edited)
473
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. ///****************
  4. const int n = 9, bn = 3;
  5. int sudokuGrid[n + 2][n + 2];
  6.  
  7. bool usedInRow(int row, int num) {
  8.     for (int i = 0; i < n; i++)
  9.         if (sudokuGrid[row][i] == num)
  10.             return true;
  11.     return false;
  12. }
  13.  
  14. bool usedInCol(int col, int num) {
  15.     for (int i = 0; i < n; i++)
  16.         if (sudokuGrid[i][col] == num)
  17.             return true;
  18.     return false;
  19. }
  20.  
  21. bool usedInBox(int bsRow, int bsCol, int num) {
  22.     for (int i = bsRow; i < bsRow + bn; i++)
  23.         for (int j = bsCol; j < bsCol + bn; j++) {
  24.             if (sudokuGrid[i][j] == num) {
  25.                 return true;
  26.             }
  27.         }
  28.     return false;
  29. }
  30.  
  31. bool isSafe(int row, int col, int num) {
  32.     bool e = !usedInRow(row, num);
  33.     e = e && !usedInCol(col, num);
  34.     e = e && !usedInBox(row - row % bn,
  35.                         col - col % bn,
  36.                         num);
  37.     return e;
  38. }
  39.  
  40. bool findEmptyPlace(int &row, int &col) {
  41.     for (row = 0; row < n; row++)
  42.         for (col = 0; col < n; col++)
  43.             if (!sudokuGrid[row][col])
  44.                 return true;
  45.     return false;
  46. }
  47.  
  48. bool solveSudoku() {
  49.     int row, col;
  50.     if (!findEmptyPlace(row, col))
  51.         return true;
  52.     for (int num = 1; num <= n; num++) {
  53.         if (isSafe(row, col, num)) {
  54.             sudokuGrid[row][col] = num;
  55.             if (solveSudoku())
  56.                 return true;
  57.             sudokuGrid[row][col] = 0;
  58.         }
  59.     }
  60.     return false;
  61. }
  62.  
  63. void read() {
  64.     for (int i = 0; i < n; i++)
  65.         for (int j = 0; j < n; j++)
  66.             cin >> sudokuGrid[i][j];
  67. }
  68.  
  69. void display(bool ok) {
  70.     if (!ok) {
  71.         puts("IMPOSSIBLE!");
  72.         return;
  73.     }
  74.     cout << string(17, '-') << endl;
  75.     for (int i = 0; i < n; i++) {
  76.         for (int j = 0; j < n; j++)
  77.             cout << sudokuGrid[i][j] << ' ';
  78.         puts("");
  79.     }
  80. }
  81.  
  82. int main()
  83. {
  84.     read();
  85.     display(solveSudoku());
  86.     return 0;
  87. }
  88.  
RAW Paste Data