37. Sudoku Solver.txt

//Оптимальное по скорости + я чутка оптимизировал. Я сделал основные массивы bool, а не int. Смысл не поменялся, за то потребляем меньше памяти.
class Solution {
    bool row[9][9] = {}, col[9][9] = {}, box[9][9] = {};//Глобальные массивы для хранения значений(По умолчанию заполнены false) 
    bool valid(int x, int y, int i) {//Функция проверки числа на возможность вставить его в пустое место основной таблицы board
        return row[x][i] == false && col[y][i] == false && box[x / 3 * 3 + y / 3][i] == false;//Если ни в одном массиве нет данного числа, значит мы можем вставить данное число в пустое место.
    }
    bool dfs(vector<vector<char>> &board, int x, int y) {//Рекурсивная функция 
        if (y == 9) {//Если строка закончилась переходим на следующую
            ++x;
            y = 0;
        }
        if (x == 9) return true;//Если вся таблица закончилась, значит судоку решено. Возвращаем true.
        if (board[x][y] == '.') {//Теперь ищем пустые значения, чтобы заполнить их.
            for (int i = 0; i < 9; ++i) {//Пытаемся подставить любое возможное число на пустое место.
                if (!valid(x, y, i)) continue;//Проверяем, может ли подойти число i + 1 на данное место. Если нет пропускаем итерацию
                board[x][y] = '1' + i;//Если да, то добавляем i + 1 в основную таблицу board.
                row[x][i] = col[y][i] = box[x / 3 * 3 + y / 3][i] = true;//Добавляем в массивы информацию, о том что мы добавили новое значение в основную таблицу board.
                if (dfs(board, x, y + 1)) return true;//Вызываем следующую рекурсивную функцию. Если следующая функция вернула true, то тоже возвращаем true, чтобы закончить рекурсию.
                row[x][i] = col[y][i] = box[x / 3 * 3 + y / 3][i] = false;//Если следующая рекурсивная функция вернула false, значит число не подошло. Удаляем информацию о нём из всех массивов.
                board[x][y] = '.';//И очищаем основную таблицу.
            }
            return false;//Если ни одно число не подошло, значит в предыдущей итерации рекурсии тоже стоит неверное число. Возвращаем false, чтобы вернуться на шаг назад.
        }
        return dfs(board, x, y + 1);//Если значение не пустое(в этом месте уже есть число), то переходим к следующему
    }
public:
    void solveSudoku(vector<vector<char>>& board) {//Основная функция
        for (int i = 0; i < 9; ++i) {//циклы перебора всех значений board
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') continue; //Нам не нужны пустые элементы
                row[i][board[i][j] - '1'] = true;//хеш-таблица строк. в строку i в элемент board[i][j] - 1 добавляем значение true. Это означает что в строке есть число, равное board[i][j] + 1. 
                col[j][board[i][j] - '1'] = true;//хеш-таблица колонок. в колонку j в элемент board[i][j] - 1 добавляем значение true. Это означает что в колонке есть число, равное board[i][j] + 1. 
                box[i / 3 * 3 + j / 3][board[i][j] - '1'] = true;//хеш-таблица полей(боксов). в бокс i / 3 * 3 + j / 3 в элемент board[i][j] - 1 добавляем значение true. Это означает что в боксе есть число, равное board[i][j] + 1. 
            }//i / 3 * 3 + j / 3 - подробное объяснение в предыдущей задаче.
        }
        dfs(board, 0, 0);//Вызываем рекурсивную функцию. В параметрах оснавная таблица, координаты x и y для начала действия алгоритма.
    }
};




//Оптимальное по скорости(оригинальное)
class Solution {
    int row[9][9] = {}, col[9][9] = {}, box[9][9] = {};//Глобальные массивы для хранения значений(По умолчанию заполнены нулями) 
    bool valid(int x, int y, int i) {//Функция проверки числа на возможность вставить его в пустое место основной таблицы board
	    return row[x][i] == 0 && col[y][i] == 0 && box[x / 3 * 3 + y / 3][i] == 0;//Если ни в одном массиве нет данного числа, значит мы можем вставить данное число в пустое место.
    }
    bool dfs(vector<vector<char>> &board, int x, int y) {//Рекурсивная функция 
        if (y == 9) {//Если строка закончилась переходим на следующую
            ++x;
            y = 0;
        }
        if (x == 9) return true;//Если вся таблица закончилась, значит судоку решено. Возвращаем true.
        if (board[x][y] == '.') {//Теперь ищем пустые значения, чтобы заполнить их.
            for (int i = 0; i < 9; ++i) {//Пытаемся подставить любое возможное число на пустое место.
                if (!valid(x, y, i)) continue;//Проверяем, может ли подойти число i + 1 на данное место. Если нет пропускаем итерацию
                board[x][y] = '1' + i;//Если да, то добавляем i + 1 в основную таблицу board.
                row[x][i] = col[y][i] = box[x / 3 * 3 + y / 3][i] = 1;//Добавляем в массивы информацию, о том что мы добавили новое значение в основную таблицу board.
                if (dfs(board, x, y + 1)) return true;//Вызываем следующую рекурсивную функцию. Если следующая функция вернула true, то тоже возвращаем true, чтобы закончить рекурсию.
                row[x][i] = col[y][i] = box[x / 3 * 3 + y / 3][i] = 0;//Если следующая рекурсивная функция вернула false, значит число не подошло. Удаляем информацию о нём из всех массивов.
                board[x][y] = '.';//И очищаем основную таблицу.
            }
            return false;//Если ни одно число не подошло, значит в предыдущей итерации рекурсии тоже стоит неверное число. Возвращаем false, чтобы вернуться на шаг назад.
        }
        return dfs(board, x, y + 1);//Если значение не пустое(в этом месте уже есть число), то переходим к следующему
    }
public:
    void solveSudoku(vector<vector<char>>& board) {//Основная функция
        for (int i = 0; i < 9; ++i) {//циклы перебора всех значений board
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') continue; //Нам не нужны пустые элементы
                row[i][board[i][j] - '1'] = 1;//хеш-таблица строк. в строку i в элемент board[i][j] - 1 добавляем значение 1. Это означает что в строке есть число, равное board[i][j] + 1. 
                col[j][board[i][j] - '1'] = 1;//хеш-таблица колонок. в колонку j в элемент board[i][j] - 1 добавляем значение 1. Это означает что в колонке есть число, равное board[i][j] + 1. 
                box[i / 3 * 3 + j / 3][board[i][j] - '1'] = 1;//хеш-таблица полей(боксов). в бокс i / 3 * 3 + j / 3 в элемент board[i][j] - 1 добавляем значение 1. Это означает что в боксе есть число, равное board[i][j] + 1. 
            }//i / 3 * 3 + j / 3 - подробное объяснение в предыдущей задаче.
        }
        dfs(board, 0, 0);//Вызываем рекурсивную функцию. В параметрах оснавная таблица, координаты x и y для начала действия алгоритма.
    }
};




//Моё решение. Рекурсия тупо на прямую.
class Solution {
public:
    bool backTracking(vector<vector<char>>& board, bool box[9][9]) {
        int pointX = 0, pointY = 0;
        bool exit = false;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++)
                if (board[i][j] == '.') {
                    pointX = i; pointY = j;
                    exit = true;
                    break;
                }
            if (exit == true)
                break;
        }
        if (exit == false)
            return true;
        //ищем занятые числа
        vector<int> busyNum;
        int b = (pointX / 3) * 3 + (pointY / 3);
        for (int i = 0; i < 9; i++) {
            if (board[pointX][i] != '.')
                busyNum.push_back(board[pointX][i] - '0');
            if (board[i][pointY] != '.')
                busyNum.push_back(board[i][pointY] - '0');
            if (box[b][i] == true) 
                busyNum.push_back(i + 1);        
        }
        bool answer = false;
        for (int i = 1; i < 10; i++)
        {
            bool ban = false;
            for (int j = 0; j < busyNum.size(); j++) 
                if (busyNum[j] == i) {
                    ban = true;
                    break;
                }                   
            if (ban == false) {
                board[pointX][pointY] = i + '0';
                box[b][i - 1] = true;
                answer = backTracking(board, box);
            }
            else
                continue;
            if (answer == true)
                return true;
            else {
                board[pointX][pointY] = '.';
                box[b][i - 1] = false;
            }
        }
        return false;
    }
    void solveSudoku(vector<vector<char>>& board) {
        bool box[9][9] = { false }; //Заполняем истинность боксов для проверка каждого вложенного поля

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

                box[b][n] = true;
            }
        }
        bool answer = backTracking(board, box);
    }
};








//VS. Тупа на прямую.

//Задание 7 Работа со строками Вариант 1
#include <iostream>
#include <cmath>
//#include <stdio.h>
#include <string> // Работа со строками
#include <fstream> // Работа с файлами в стиле C++
#include <conio.h> //Обработка нажатия на клавиши
#include <Windows.h>
#include <WinCon.h>//Для выделения текста в консоли
#include <vector>
#include <algorithm>
#include <queue>



using namespace std;

bool backTracking(vector<vector<char>>& board, bool box[9][9]) {
	int pointX = 0, pointY = 0;
	bool exit = false;
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++)
			if (board[i][j] == '.') {
				pointX = i; pointY = j;
				exit = true;
				break;
			}
		if (exit == true)
			break;
	}
	if (exit == false)
		return true;
	//ищем занятые числа
	vector<int> busyNum;
	int b = (pointX / 3) * 3 + (pointY / 3);
	for (int i = 0; i < 9; i++) {
		if (board[pointX][i] != '.')
			busyNum.push_back(board[pointX][i] - '0');
		if (board[i][pointY] != '.')
			busyNum.push_back(board[i][pointY] - '0');
		if (box[b][i] == true) 
			busyNum.push_back(i + 1);

			
	}
	//Ищем свободные числа
	//vector<int> availableNum = {1,2,3,4,5,6,7,8,9};

	//запускаем цикл с рекурсией
	bool answer = false;
	for (int i = 1; i < 10; i++)
	{
		bool ban = false;
		for (int j = 0; j < busyNum.size(); j++) 
			if (busyNum[j] == i) {
				ban = true;
				break;
			}
				
		if (ban == false) {
			board[pointX][pointY] = i + '0';
			box[b][i - 1] = true;
			answer = backTracking(board, box);
		}
		else
			continue;
		if (answer == true)
			return true;
		else {
			board[pointX][pointY] = '.';
			box[b][i - 1] = false;
		}
	}
	return false;
}

void solveSudoku(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); //Получаем индекс массива для боксов

			row[r][n] = true; // Если нет, то в каждый массив ставим true
			col[c][n] = true;
			box[b][n] = true;
		}
	}
	bool answer = backTracking(board, box);

}

int main()
{
	setlocale(LC_ALL, "Russian");// Русский язык в консоли

	vector<vector<char>> 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'} };
	solveSudoku(board);

}