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.
------------------------------------------------------------
Check raw, collomn and then squares. See codes for details. For debugging reason, I change the input format to vector<string>, so that I can easily write some test input.
NOTE: for square check, I originally wrote:
for (int m = i; m<m + 3; m++){
for (int n = j; n<n + 3; n++){
which will be wrong as it will continue until the end. The correct one should be:
for (int m = i; m<i + 3; m++){
for (int n = j; n<j + 3; n++){
where i, j from previous procedures.
where i, j from previous procedures.
///////////////////////////////////////////////////////////////
//codes
#include "stdafx.h"
# include <cstdlib>
#include <iostream>
// std::cout
#include <algorithm>
// std::sort
#include <vector>
// std::vector
# include <map> // std::map
# include <unordered_map>
# include <string>
#include <bitset>
#include <ctype.h>
using namespace std;
class Solution {
public:
bool isValidSudoku(vector<string>& board) {
map<char, int>
tmp;
//check raw
for (int i = 0; i<9; i++){
tmp.clear();
for (int j = 0; j<9; j++){
if (board[i][j] != '.'){
if (tmp.find(board[i][j]) != tmp.end())
return false;
else tmp[board[i][j]] = i;
}
}
}
//check collom
for (int i = 0; i<9; i++){
tmp.clear();
for (int j = 0; j<9; j++){
if (board[j][i] != '.'){
if (tmp.find(board[j][i]) != tmp.end())
return false;
else tmp[board[j][i]] = i;
}
}
}
//check square
for (int i = 0; i<9; i = i + 3){
for (int j = 0; j<9; j = j + 3){
tmp.clear();
for (int m = i; m<i + 3; m++){
for (int n = j; n<j + 3; n++){
if (board[m][n] != '.'){
if (tmp.find(board[m][n]) != tmp.end())
return false;
else tmp[board[m][n]] = i;
}
}
}
}
}
return true;
}
};
int main(int argc, char *argv[])
{
vector<string> input = { ".87654321", "2........", "3........", "4........", "5........", "6........", "7........", "8........", "9........" };
Solution s;
bool i = s.isValidSudoku(input);
}
///////////////////////////////////////////////////////////////////
// codes for Leetcode
class Solution {
public:
bool isValidSudoku(vector<vector<char>>&
board) {
map<char, int>
tmp;
//check raw
for (int i = 0; i<9; i++){
tmp.clear();
for (int j = 0; j<9; j++){
if (board[i][j] != '.'){
if (tmp.find(board[i][j]) != tmp.end())return false;
else tmp[board[i][j]] = i;
}
}
}
//check collom
for (int i = 0; i<9; i++){
tmp.clear();
for (int j = 0; j<9; j++){
if (board[j][i] != '.'){
if (tmp.find(board[j][i]) != tmp.end())return false;
else tmp[board[j][i]] = i;
}
}
}
//check square
for (int i = 0; i<9; i = i + 3){
for (int j = 0; j<9; j = j + 3){
tmp.clear();
for (int m = i; m<i + 3; m++){
for (int n = j; n<j + 3; n++){
if (board[m][n] != '.'){
if (tmp.find(board[m][n]) != tmp.end())return false;
else tmp[board[m][n]] = i;
}
}
}
}
}
return true;
}
};
No comments:
Post a Comment