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 elements inside the square
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
for (int dr=0; dr<=8; dr++) {
if (dr == r) // skip the current row
continue;
else {
if (board[dr][c] == board[r][c])
return false;
}
}
// Check in all the columns for a matching number
for (int dc=0; dc<=8; dc++) {
if (dc == c) // skip the current row
continue;
else {
if (board[r][dc] == board[r][c])
return false;
}
}
// Check in the square for any matching number
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