leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0037.cpp (1039B)

      1 class Solution {
      2     bool check(vector<vector<char>> &board, int i, int j, char val) {
      3         for (int x = 0; x < 9; x++)
      4             if (board[x][j] == val) return false;
      5         for (int y = 0; y < 9; y++)
      6             if (board[i][y] == val) return false;
      7 
      8         i = (i / 3) * 3, j = (j / 3) * 3;
      9         for (int x = i; x < i + 3; x++)
     10             for (int y = j; y < j + 3; y++)
     11                 if (board[x][y] == val) return false;
     12         return true;
     13     }
     14     bool solveSudoku(vector<vector<char>> &board, int i, int j) {
     15         if (i == 9) return true;
     16         if (j == 9) return solveSudoku(board, i + 1, 0);
     17         if (board[i][j] != '.') return solveSudoku(board, i, j + 1);
     18 
     19         for (char c = '1'; c <= '9'; c++) {
     20             if (!check(board, i, j, c)) continue;
     21             board[i][j] = c;
     22             if (solveSudoku(board, i, j + 1)) return true;
     23             board[i][j] = '.';
     24         }
     25 
     26         return false;
     27     }
     28 
     29   public:
     30     void solveSudoku(vector<vector<char>> &board) { solveSudoku(board, 0, 0); }
     31 };