[Geeks for Geeks] Solve the Sudoku

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:
//Function to find a solved Sudoku.
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);
}

//Function to print grids of the Sudoku.
void printGrid (int grid[N][N])
{
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++)
cout<<grid[i][j]<<' ';
}
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/15/PS/GeeksforGeeks/solve-the-sudoku/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.