Solve the Sudoku
Given an incomplete Sudoku configuration in terms of a 9 x 9 2-D square matrix (grid[][]), the task to find a solved Sudoku. For simplicity, you may assume that there will be only one unique solution.
Time : O(9^(n*n))
Space : O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 vector<int > cells (9 ) , rows (9 ) , cols (9 ) ;class Solution { bool helper (int grid[N][N], int pos) { if (pos == 81 ) return true ; int y = pos / 9 , x = pos % 9 ; if (grid[y][x]) return helper (grid, pos + 1 ); int row = y, col = x, cell = (y / 3 ) * 3 + (x / 3 ); int mask = rows[row] | cols[col] | cells[cell]; for (int i = 1 ; i <= 9 ; i++) { if (mask & (1 <<i)) continue ; rows[row] ^= (1 <<i); cols[col] ^= (1 <<i); cells[cell] ^= (1 <<i); grid[y][x] = i; if (helper (grid, pos + 1 )) return true ; grid[y][x] = 0 ; rows[row] ^= (1 <<i); cols[col] ^= (1 <<i); cells[cell] ^= (1 <<i); } return false ; } public : bool SolveSudoku (int grid[N][N]) { for (int i = 0 ; i < 9 ; i++) rows[i] = cols[i] = cells[i] = 0 ; for (int i = 0 ; i < N; i++) { for (int j = 0 ; j < N; j++) { if (grid[i][j]) { int row = i; int col = j; int cell = (i / 3 ) * 3 + (j / 3 ); rows[row] |= (1 <<grid[i][j]); cols[col] |= (1 <<grid[i][j]); cells[cell] |= (1 <<grid[i][j]); } } } return helper (grid, 0 ); } void printGrid (int grid[N][N]) { for (int i = 0 ; i < N; i++) { for (int j = 0 ; j < N; j++) cout<<grid[i][j]<<' ' ; } } };