Determine if a Sudoku is valid. The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’. A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
sudoku
A valid Sudoku contains three conditions: (1) all rows should contain exactly 1 to 9. (2) all columns should contain exactly 1 to 9. (3) all sub grids (9 of them) should contain exactly 1 to 9.
The best data structure we can use is the STL:set, we need to clean the set before next validation (row, column or grid). To solve a Sudoku, we can use DFS algorithm: Depth First Search (Backtracking) Algorithm to Solve a Sudoku Game
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 | // https://helloacm.com/how-to-check-valid-sudoku-in-cc/ class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { unordered_set<int> has; for (int i = 0; i < 9; i ++) { has.clear(); // rows for (int j = 0; j < 9; j ++) { if (board[i][j] != '.') { if (has.count(board[i][j])) { return false; } has.insert(board[i][j]); } } has.clear(); // columns for (int j = 0; j < 9; j ++) { if (board[j][i] != '.') { if (has.count(board[j][i])) { return false; } has.insert(board[j][i]); } } } for (int i = 0; i < 3; i ++) { for (int j = 0; j < 3; j ++) { // sub grids has.clear(); for (int x = i * 3; x < i * 3 + 3; x ++) { for (int y = j * 3; y < j * 3 + 3; y ++) { if (board[x][y] != '.') { if (has.count(board[x][y])) { return false; } has.insert(board[x][y]); } } } } } return true; } }; |
// https://helloacm.com/how-to-check-valid-sudoku-in-cc/
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
unordered_set<int> has;
for (int i = 0; i < 9; i ++) {
has.clear();
// rows
for (int j = 0; j < 9; j ++) {
if (board[i][j] != '.') {
if (has.count(board[i][j])) {
return false;
}
has.insert(board[i][j]);
}
}
has.clear();
// columns
for (int j = 0; j < 9; j ++) {
if (board[j][i] != '.') {
if (has.count(board[j][i])) {
return false;
}
has.insert(board[j][i]);
}
}
}
for (int i = 0; i < 3; i ++) {
for (int j = 0; j < 3; j ++) {
// sub grids
has.clear();
for (int x = i * 3; x < i * 3 + 3; x ++) {
for (int y = j * 3; y < j * 3 + 3; y ++) {
if (board[x][y] != '.') {
if (has.count(board[x][y])) {
return false;
}
has.insert(board[x][y]);
}
}
}
}
}
return true;
}
};See also: Just Another Sudoku Solver in Depth First Search (and BackTracking) Algorithm
Checking a Sudoku to see if it is valid or not in Python with 27 Hash Sets: Teaching Kids Programming – Sudoku Validator/Algorithm using 27 Hash Sets
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Delphi 10.1 Berlin Version Number
Next Post: Google Interview Question - Print Message
