Rules of Sudoku Grid
Thus we have the below 3 algorithmic checks
Program to validate a given Sudoku
#include<iostream>
#include<vector>
#include<map>
using namespace std;
class Sudoku {
public:
bool IsValid (vector<vector<char>>& board) {
// Create a map for validating the number inside the 9 smaller grids of dimension (3 X 3).
// This additional check would be used after the row and columns check pass
// These smaller grids start from
// 1'st row : [0,0], [0,3], [0,6]
// 2'nd row : [3,0], [3,3], [3,6]
// 3'rd row : [6,0], [6,3], [6,6]
map<int,int> row_start, col_start;
for(int i=0; i<=2; i++) {
row_start[i] = 0;
col_start[i] = 0;
}
for(int i=3; i<=5; i++) {
row_start[i] = 3;
col_start[i] = 3;
}
for(int i=6; i<=8; i++) {
row_start[i] = 6;
col_start[i] = 6;
}
// Look at each element of the sudoku
for (int r=0; r<=8; r++) {
for (int c=0; c<=8; c++) {
if (board[r][c] == '.') {
continue;
} else {
// Check in all the rows for a matching number, column would remain the same only row would increment.
for (int dr=0; dr<=8; dr++) {
if (dr == r) // skip the current row, as we don't want to compare the number with itself
continue;
else {
if (board[dr][c] == board[r][c])
return false;
}
}
// Check in all the columns for a matching number, row will remain the same only column would increment.
for (int dc=0; dc<=8; dc++) {
if (dc == c) // skip the current column, as we don't want to compare the number with itself
continue;
else {
if (board[r][dc] == board[r][c])
return false;
}
}
// Check in the square of dimension (3 X 3) for any matching number.
// Ex: To check if a number at position [4,4] is valild, check all the numbers in the grid starting from [3,3] till [6,6] for any match
for (int dr=row_start[r]; dr<=row_start[r]+2; dr++) {
for (int dc=col_start[c]; dc<=col_start[c]+2; dc++) {
if (dr == r and dc == c) // Skip the same element
continue;
else if (board[dr][dc] == board[r][c])
return false;
}
}
}
}
}
return true;
}
};
int main() {
Sudoku S;
vector<vector<char>> grid_1 = {{ '5', '3', '.', '.', '7', '.', '.', '.', '.'},
{ '6', '.', '.', '1', '9', '5', '.', '.', '.'},
{ '.', '9', '8', '.', '.', '.', '.', '6', '.'},
{ '8', '.', '.', '.', '6', '.', '.', '.', '3'},
{ '4', '.', '.', '8', '.', '3', '.', '.', '1'},
{ '7', '.', '.', '.', '2', '.', '.', '.', '6'},
{ '.', '6', '.', '.', '.', '.', '2', '8', '.'},
{ '.', '.', '.', '4', '1', '9', '.', '.', '5'},
{ '.', '.', '.', '.', '8', '.', '.', '7', '9'}};
if (S.IsValid(grid_1)) {
cout << "Sudoku grid_1 is valid" << endl;
} else {
cout << "Sudoku grid_1 is invalid" << endl;
}
vector<vector<char>> grid_2 = {{ '8', '3', '.', '.', '7', '.', '.', '.', '.'},
{ '6', '.', '.', '1', '9', '5', '.', '.', '.'},
{ '.', '9', '8', '.', '.', '.', '.', '6', '.'},
{ '8', '.', '.', '.', '6', '.', '.', '.', '3'},
{ '4', '.', '.', '8', '.', '3', '.', '.', '1'},
{ '7', '.', '.', '.', '2', '.', '.', '.', '6'},
{ '.', '6', '.', '.', '.', '.', '2', '8', '.'},
{ '.', '.', '.', '4', '1', '9', '.', '.', '5'},
{ '.', '.', '.', '.', '8', '.', '.', '7', '9'}};
if (S.IsValid(grid_2)) {
cout << "Sudoku grid_2 is valid" << endl;
} else {
cout << "Sudoku grid_2 is invalid" << endl;
}
return 0;
}
Output
Sudoku grid_1 is valid
Sudoku grid_2 is invalid