Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character
'.'
.
A partially filled sudoku which is valid.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
Solution:
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
map<char, bool> map, map2, map3;
int size = board.size();
// Check Rows and cols.
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if ((board[i][j] != '.' && map.find(board[i][j]) != map.end()) ||
(board[j][i] != '.' && map2.find(board[j][i]) != map2.end())) {
return false;
} else {
map[board[i][j]] = true;
map2[board[j][i]] = true;
}
}
map.clear();
map2.clear();
}
// Box check.
for (int i = 0; i < 9; i=i+3) {
for (int j = 0; j < 9; j=j+3) {
for (int ii = i; ii < i + 3; ii++) {
for (int jj = j; jj < j + 3; jj++) {
if (board[ii][jj] != '.' && map3.find(board[ii][jj]) != map3.end()) {
return false;
} else {
map3[board[ii][jj]] = true;
}
}
}
map3.clear();
}
}
return true;
}
};
====================== Again ===============
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
if (board.size() != 9 || board[0].size() != 9) {
return false;
}
if (!rowValid(board) || !colValid(board) || !boxValid(board)) {
return false;
}
return true;
}
bool rowValid(vector<vector<char>>& board) {
for (auto row : board) {
set<int> st;
for (char ch : row) {
if (ch != '.') {
if (st.count(ch)) {
return false;
}
st.insert(ch);
}
}
}
return true;
}
bool colValid(vector<vector<char>>& board) {
for (int i = 0; i < 9; i++) {
set<int> st;
for (int j = 0; j < 9; j++) {
if (board[j][i] != '.') {
if (st.count(board[j][i])) {
return false;
}
st.insert(board[j][i]);
}
}
}
return true;
}
bool boxValid(vector<vector<char>>& board) {
for (int ii = 0; ii < 9; ii = ii + 3) {
for (int jj = 0; jj < 9; jj = jj + 3) {
set<int> st;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[ii + i][ jj + j] != '.') {
if (st.count(board[ii + i][ jj + j])) {
return false;
}
st.insert(board[ii + i][ jj + j]);
}
}
}
}
}
return true;
}
};
============= Single iteration solution ===========
class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { unordered_set<string> st; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if (board[i][j] == '.') continue; string t = "(" + to_string(board[i][j]) + ")"; string row = to_string(i) + t, col = t + to_string(j), cell = to_string(i / 3) + t + to_string(j / 3); if (st.count(row) || st.count(col) || st.count(cell)) return false; st.insert(row); st.insert(col); st.insert(cell); } } return true; } };
No comments:
Post a Comment