Судоку

Судоку — Двумерные массивы

Судоку

Судоку размера n представляет собой квадратное поле размером n² x n², разделенное на n² подполей размером n x n. В каждом подполе содержатся числа от 1 до n².

Судоку считается правильным, если в каждой строке, каждом столбце и каждом подполе все числа от 1 до n² встречаются ровно один раз.

Недавно Вася нарисовал Судоку размера n. Ваша задача — помочь ему определить, является ли он правильным.

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

В первой строке файла INPUT.TXT записано число n (1 ≤ n ≤ 10). В следующих n² строках содержится по n² чисел, описывающих Судоку, нарисованный Васей.
Все числа в файле — натуральные и не превышают 100.

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

Если Судоку правильный, выведите в файл OUTPUT.TXT слово «Correct», иначе выведите «Incorrect».

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	3 1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 2 3 1 5 6 4 8 9 7 5 6 4 8 9 7 2 3 1 8 9 7 2 3 1 5 6 4 3 1 2 6 4 5 9 7 8 6 4 5 9 7 8 3 1 2 9 7 8 3 1 2 6 4 5	Correct
2	2 1 2 3 4 3 4 1 2 2 1 4 3 4 3 2 1	Correct
3	2 1 2 3 4 3 4 1 2 2 1 4 3 4 3 2 2	Incorrect

Показать решение...

Объяснение кода

Приведенный ниже код проверяет правильность заданной сетки Судоку размера n. Судоку считается правильным, если в каждой строке, каждом столбце и каждом подполе встречаются все числа от 1 до n² ровно один раз.

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

// Функция для проверки правильности Судоку
bool is_valid_sudoku(const vector<vector<int>>& grid, int n) {
    int size = n * n;
    
    // Булевы массивы для отслеживания увиденных чисел
    vector<bool> seen(size + 1, false);

    // Проверка строк
    for (int i = 0; i < size; ++i) {
        fill(seen.begin(), seen.end(), false); // Сброс массива seen для каждой строки
        for (int j = 0; j < size; ++j) {
            if (seen[grid[i][j]]) return false; // Если число уже видели, недопустимо
            seen[grid[i][j]] = true; // Отметить число как увиденное
        }
        // Убедиться, что все числа от 1 до n^2 были видены
        for (int k = 1; k <= size; ++k) {
            if (!seen[k]) return false;
        }
    }

    // Проверка столбцов
    for (int j = 0; j < size; ++j) {
        fill(seen.begin(), seen.end(), false); // Сброс массива seen для каждого столбца
        for (int i = 0; i < size; ++i) {
            if (seen[grid[i][j]]) return false; // Если число уже видели, недопустимо
            seen[grid[i][j]] = true; // Отметить число как увиденное
        }
        // Убедиться, что все числа от 1 до n^2 были видены
        for (int k = 1; k <= size; ++k) {
            if (!seen[k]) return false;
        }
    }

    // Проверка подгрупп
    for (int block_row = 0; block_row < n; ++block_row) {
        for (int block_col = 0; block_col < n; ++block_col) {
            fill(seen.begin(), seen.end(), false); // Сброс массива seen для каждой подгруппы
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    int x = block_row * n + i;
                    int y = block_col * n + j;
                    if (seen[grid[x][y]]) return false; // Если число уже видели, недопустимо
                    seen[grid[x][y]] = true; // Отметить число как увиденное
                }
            }
            // Убедиться, что все числа от 1 до n^2 были видены
            for (int k = 1; k <= size; ++k) {
                if (!seen[k]) return false;
            }
        }
    }

    return true;
}

int main() {
    ifstream inputFile("INPUT.TXT");
    ofstream outputFile("OUTPUT.TXT");

    if (!inputFile.is_open()) {
        cerr << "Не удалось открыть входной файл!" << endl;
        return 1;
    }

    int n;
    inputFile >> n;
    int size = n * n;

    vector<vector<int>> grid(size, vector<int>(size));
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j) {
            inputFile >> grid[i][j];
        }
    }

    inputFile.close();

    if (is_valid_sudoku(grid, n)) {
        outputFile << "Correct" << endl;
    } else {
        outputFile << "Incorrect" << endl;
    }

    outputFile.close();

    return 0;
}

#include <iostream>

#include <fstream>

#include <vector>

using namespace std;

// Функция для проверки правильности Судоку

bool is_valid_sudoku(const vector<vector<int>>& grid, int n) {

int size = n * n;

// Булевы массивы для отслеживания увиденных чисел

vector<bool> seen(size + 1, false);

// Проверка строк

for (int i = 0; i < size; ++i) {

fill(seen.begin(), seen.end(), false); // Сброс массива seen для каждой строки

for (int j = 0; j < size; ++j) {

if (seen[grid[i][j]]) return false; // Если число уже видели, недопустимо

seen[grid[i][j]] = true; // Отметить число как увиденное

}

// Убедиться, что все числа от 1 до n^2 были видены

for (int k = 1; k <= size; ++k) {

if (!seen[k]) return false;

}

// Проверка столбцов

for (int j = 0; j < size; ++j) {

fill(seen.begin(), seen.end(), false); // Сброс массива seen для каждого столбца

for (int i = 0; i < size; ++i) {

if (seen[grid[i][j]]) return false; // Если число уже видели, недопустимо

seen[grid[i][j]] = true; // Отметить число как увиденное

}

// Убедиться, что все числа от 1 до n^2 были видены

for (int k = 1; k <= size; ++k) {

if (!seen[k]) return false;

}

// Проверка подгрупп

for (int block_row = 0; block_row < n; ++block_row) {

for (int block_col = 0; block_col < n; ++block_col) {

fill(seen.begin(), seen.end(), false); // Сброс массива seen для каждой подгруппы

for (int i = 0; i < n; ++i) {

for (int j = 0; j < n; ++j) {

int x = block_row * n + i;

int y = block_col * n + j;

if (seen[grid[x][y]]) return false; // Если число уже видели, недопустимо

seen[grid[x][y]] = true; // Отметить число как увиденное

}

// Убедиться, что все числа от 1 до n^2 были видены

for (int k = 1; k <= size; ++k) {

if (!seen[k]) return false;

}

return true;

}

int main() {

ifstream inputFile("INPUT.TXT");

ofstream outputFile("OUTPUT.TXT");

if (!inputFile.is_open()) {

cerr << "Не удалось открыть входной файл!" << endl;

return 1;

}

int n;

inputFile >> n;

int size = n * n;

vector<vector<int>> grid(size, vector<int>(size));

for (int i = 0; i < size; ++i) {

for (int j = 0; j < size; ++j) {

inputFile >> grid[i][j];

}

inputFile.close();

if (is_valid_sudoku(grid, n)) {

outputFile << "Correct" << endl;

} else {

outputFile << "Incorrect" << endl;

}

outputFile.close();

return 0;

}

Объяснение кода

Программа состоит из нескольких частей, каждая из которых выполняет определенную функцию для проверки правильности Судоку.

Заголовки и пространство имен

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#include <iostream>

#include <fstream>

#include <vector>

using namespace std;

Здесь подключаются необходимые заголовочные файлы для работы с вводом-выводом и векторами.

Функция проверки валидности Судоку

bool is_valid_sudoku(const vector<vector<int>>& grid, int n) {
    int size = n * n;
    vector<bool> seen(size + 1, false);

    // Проверка строк
    for (int i = 0; i < size; ++i) {
        fill(seen.begin(), seen.end(), false); // Сброс массива seen для каждой строки
        for (int j = 0; j < size; ++j) {
            if (seen[grid[i][j]]) return false; // Если число уже видели, недопустимо
            seen[grid[i][j]] = true; // Отметить число как увиденное
        }
        for (int k = 1; k <= size; ++k) {
            if (!seen[k]) return false;
        }
    }

    // Проверка столбцов
    for (int j = 0; j < size; ++j) {
        fill(seen.begin(), seen.end(), false); // Сброс массива seen для каждого столбца
        for (int i = 0; i < size; ++i) {
            if (seen[grid[i][j]]) return false; // Если число уже видели, недопустимо
            seen[grid[i][j]] = true; // Отметить число как увиденное
        }
        for (int k = 1; k <= size; ++k) {
            if (!seen[k]) return false;
        }
    }

    // Проверка подгрупп
    for (int block_row = 0; block_row < n; ++block_row) {
        for (int block_col = 0; block_col < n; ++block_col) {
            fill(seen.begin(), seen.end(), false); // Сброс массива seen для каждой подгруппы
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    int x = block_row * n + i;
                    int y = block_col * n + j;
                    if (seen[grid[x][y]]) return false; // Если число уже видели, недопустимо
                    seen[grid[x][y]] = true; // Отметить число как увиденное
                }
            }
            for (int k = 1; k <= size; ++k) {
                if (!seen[k]) return false;
            }
        }
    }

    return true;
}

bool is_valid_sudoku(const vector<vector<int>>& grid, int n) {

int size = n * n;

vector<bool> seen(size + 1, false);

// Проверка строк

for (int i = 0; i < size; ++i) {

fill(seen.begin(), seen.end(), false); // Сброс массива seen для каждой строки

for (int j = 0; j < size; ++j) {

if (seen[grid[i][j]]) return false; // Если число уже видели, недопустимо

seen[grid[i][j]] = true; // Отметить число как увиденное

}

for (int k = 1; k <= size; ++k) {

if (!seen[k]) return false;

}

// Проверка столбцов

for (int j = 0; j < size; ++j) {

fill(seen.begin(), seen.end(), false); // Сброс массива seen для каждого столбца

for (int i = 0; i < size; ++i) {

if (seen[grid[i][j]]) return false; // Если число уже видели, недопустимо

seen[grid[i][j]] = true; // Отметить число как увиденное

}

for (int k = 1; k <= size; ++k) {

if (!seen[k]) return false;

}

// Проверка подгрупп

for (int block_row = 0; block_row < n; ++block_row) {

for (int block_col = 0; block_col < n; ++block_col) {

fill(seen.begin(), seen.end(), false); // Сброс массива seen для каждой подгруппы

for (int i = 0; i < n; ++i) {

for (int j = 0; j < n; ++j) {

int x = block_row * n + i;

int y = block_col * n + j;

if (seen[grid[x][y]]) return false; // Если число уже видели, недопустимо

seen[grid[x][y]] = true; // Отметить число как увиденное

}

for (int k = 1; k <= size; ++k) {

if (!seen[k]) return false;

}

return true;

}

Эта функция проверяет строки, столбцы и подгруппы в сетке Судоку на наличие всех чисел от 1 до n² ровно один раз.

Основная функция

int main() {
    ifstream inputFile("INPUT.TXT");
    ofstream outputFile("OUTPUT.TXT");

    if (!inputFile is_open()) {
        cerr << "Не удалось открыть входной файл!" << endl;
        return 1;
    }

    int n;
    inputFile >> n;
    int size = n * n;

    vector<vector<int>> grid(size, vector<int>(size));
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j) {
            inputFile >> grid[i][j];
        }
    }

    inputFile.close();

    if (is_valid_sudoku(grid, n)) {
        outputFile << "Correct" << endl;
    } else {
        outputFile << "Incorrect" << endl;
    }

    outputFile.close();

    return 0;
}

int main() {

ifstream inputFile("INPUT.TXT");

ofstream outputFile("OUTPUT.TXT");

if (!inputFile is_open()) {

cerr << "Не удалось открыть входной файл!" << endl;

return 1;

}

int n;

inputFile >> n;

int size = n * n;

vector<vector<int>> grid(size, vector<int>(size));

for (int i = 0; i < size; ++i) {

for (int j = 0; j < size; ++j) {

inputFile >> grid[i][j];

}

inputFile.close();

if (is_valid_sudoku(grid, n)) {

outputFile << "Correct" << endl;

} else {

outputFile << "Incorrect" << endl;

}

outputFile.close();

return 0;

}

Основная функция программы выполняет следующие действия:

Открывает входной файл для чтения и выходной файл для записи.
Считывает размерность n и размер сетки size.
Инициализирует сетку Судоку, считывая значения из входного файла.
Закрывает входной файл.
Проверяет валидность Судоку с помощью функции is_valid_sudoku.
Записывает результат проверки в выходной файл: «Correct» или «Incorrect».
Закрывает выходной файл.