36. Valid Sudoku.txt

//Оптимальный по скорости. Создаётся 3 двумерных массива типа bool для хранения истинности строк, столбцов и полей размером 3 на 3(боксов).
//В каждом таком массиве есть ещё 9 массивов состоящих из 9 элементов.(массив 9и строк, в каждой строке 9 элементов). По умолчанию все false;
//С помощью двух циклов проходим все строки и столбцы. Если числа нет, то пропускаем эту итерацию.
//Когда мы находим число, превращаем его из char в int и отнимаем 1. Т.о. у нас появляется индекс массива в который мы положим значение true;
//Если в массиве под этим же индексом уже есть true, значит данное число уже было, и мы возвращаем false. 
//Со строками и столбцами всё просто но вот с боксами нет. Нам нужно понять в какой бокс положить данное число.
//Для получения индекса бокса мы должны воспользоваться формулой int b = (r / 3) * 3 + (c / 3); где r - индекс строки, c - индекс колонки(столбца).
//У нас есть 9 полей (боксов) и расположены они вот так 123. Бокс состоит 3 на 3 элементов. Т.е. через каждые 3 элемента должен быть след. бокс.
//					   		456
//					   		789
//Поэтому индекс строки r и столбца c делим на 3.(0 / 3 == 0, 3 / 3 == 1, 6 / 3 == 2). Складываем полученные ответы для c и r чтобы получить индекс бокса.
//Поскольку по горизонтали у нас всего 3 бокса для переноса на 4 бокс умножаем r / 3 на 3.(очень умно жаль я сам не придумал этого).

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        const int cnt = 9; //Общее кол-во
	bool row[cnt][cnt] = { false }; //Заполняем истинность рядов для проверки каждой строки
	bool col[cnt][cnt] = { false }; //Заполняем истинность колонок для проверка каждого столбца
	bool box[cnt][cnt] = { false }; //Заполняем истинность боксов для проверка каждого вложенного поля

	for (int r = 0; r < cnt; r++) { //Цикл по всем строкам
		for (int c = 0; c < cnt; c++) { //Цикл по всем колонкам
			if (board[r][c] == '.') continue; //Пропускаем итерацию если в ячейке нет числа
			int n = board[r][c] - '0' - 1; //Извлекаем число из символа. Убавляем на 1 чтобы получить индекс
			int b = (r / 3) * 3 + (c / 3); //Получаем индекс массива для боксов
			if (row[r][n] || col[c][n] || box[b][n]) return false; //Если уже гдето есть true то возвращаем false

			row[r][n] = true; // Если нет, то в каждый массив ставим true
			col[c][n] = true;
			box[b][n] = true;
		}
	}
	return true;//Если код закончился, то значит нигде нет повторений
    }
};


//Мой код. Проверяю все строки и стобцы начиная с верхнего левого. Чтобы определить истинность в боксах, сначала проверяю первые 3 строки, и уже 
//	потом первые 3 столбца.
//Мне потребовалось 3 вектора чтобы запоминать инфу о боксах и ещё один вектор чтобы запоминать текущую строку или столбец.
//Не оптимально, потому что 3 подрят for и некоторые боксы проверяются по 2 раза.
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<vector<bool>> box[9][10];
        for (int step = 0; step < 9; step += 3) {
            vector<vector<bool>> box(3, vector<bool>(10, false));
            for (int i = step; i < step + 3; i++) {
                vector<bool> numbersLine(10);
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] != '.') {
                        int k = board[i][j] - '0';
                        if (numbersLine[k] == false)
                            numbersLine[k] = true;
                        else
                            return false;
                        int boxNum = j / 3;
                        if (box[boxNum][k] == false)
                            box[boxNum][k] = true;
                        else
                            return false;	
                    }
                }
            }
            for (int k = 0; k < 3; k++)//обнуляем вектора
                fill(begin(box[k]), end(box[k]), false);
            for (int j = step; j < step + 3; j++) {
                vector<bool> numbersLine(10);
                for (int i = 0; i < 9; i++) {
                    if (board[i][j] != '.') {
                        int k = board[i][j] - '0';
                        if (numbersLine[k] == false)
                            numbersLine[k] = true;
                        else
                            return false;
                        int boxNum = i / 3;
                        if (box[boxNum][k] == false)
                            box[boxNum][k] = true;
                        else
                            return false;
                    }
                }
            }
        }
        return true;
    }
};