Saturday, July 16, 2016

Valid Sudoku

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.

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