36. Проверка доски судоку (Valid Sudoku)

Задание.

Определить, является ли верной полученная доска для судоку размером 9 х 9 дюймов.

Только заполненные ячейки должны быть проверены в соответствии со следующими правилами:

• Каждая строка должна содержать цифры 1-9 без повторения.

• Каждый столбец должен содержать цифры 1-9 без повторения.

• В каждом из 9-ти под-квадратов, размером 3x3, должны быть цифры 1-9 без повторения

Примечание:

• Частично заполненная доска для судоку может быть допустимой, но не обязательно разрешимой.

• В соответствии с упомянутыми правилами нужно проверять только заполненные ячейки.

Пример 1.

Входные данные:

board = 
[["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"]]

Результат: true

Пример 2.

Входные данные:

board = 
[["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"]]

Результат: false

Пояснение:

То же, что и в примере 1, за исключением того, что цифра 5 в верхнем левом углу изменена на 8. Поскольку в верхнем левом вложенном поле 3x3 есть две восьмерки, это недопустимо.

Решение.

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_set<char> row[9];
        unordered_set<char> col[9];
        unordered_set<char>  sq[9];
        int r, c, shift;
        char val;

        for(r = 0; r < 9; r++) {
            for(c = 0; c < 9; c++) {
                if((val = board[r][c]) == '.')
                    continue;

                shift = (r/3)*3 + (c/3);

                if(row[r].count(val) || col[c].count(val) || sq[shift].count(val))
                    return false;

                row[r].insert(val);
                col[c].insert(val);
                sq[shift].insert(val);
            }
        }
        return true;
    }
};