Задача
Судоку — это очень простая задача. Квадратная таблица из $9$ строк и $9$ столбцов разделена на $9$ меньших квадратов $3×3$, как показано на рисунке. В некоторых клетках записаны десятичные цифры от $1$ до $9$. Другие клетки пусты. Цель состоит в том, чтобы заполнить пустые клетки десятичными цифрами от $1$ до $9$, по одной цифре в клетке, таким образом, чтобы в каждой строке, в каждом столбце и в каждой отмеченном подквадрате $3×3$, были все цифры от $1$ до $9$. Напишите программу для решения данной задачи судоку.
Входные данные
Входные данные начинаются со строки с количеством тестов. Для каждого теста далее следует $9$ строк, содержащие соответствующе строки таблицы. В каждой строке размещено ровно $9$ десятичных цифр, соответствующие цифрам в ячейках этой строки. Если ячейка пуста, во входных данных в ней содержится цифра $0$.
Выходные данные
Для каждого теста ваша программа должна вывести решение в том же формате, что и во входных данных. Пустые ячейки должны быть заполнены в соответствии с правилами. Если решение не является уникальным, то программа может вывести любое из них.
Выходные данные для различных тестовых случаев разделяйте пустой строкой.
Тесты
| № | Входные данные | Выходные данные |
| 1 |
1 103000509 002109400 000704000 300502006 060000050 700803004 000401000 009205800 804000107 |
143628579 572139468 986754231 391542786 468917352 725863914 237481695 619275843 854396127 |
| 2 |
1 160920000 000000106 300700084 000002950 002040000 000001840 200400015 000000309 690170000 |
164928573 827354196 359716284 416832957 982547631 573691842 238469715 741285369 695173428 |
| 3 |
1 500008431 107000900 830600050 300502800 000040000 008307005 060003014 003000602 412900003 |
596728431 127435968 834619257 371562849 259841376 648397125 965283714 783154692 412976583 |
| 4 |
1 061030240 005000100 840000069 100090004 600403005 030607080 000000000 008050400 000948000 |
761539248 925864173 843721569 187295634 692483715 534617982 459376821 378152496 216948357 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <iostream> #include <string> #include <vector> class Sudoku { std::vector<std::string> board{9}; bool is_valid(int row, int col, char digit) { for (int i = 0; i < 9; ++i) if (board[row][i] == digit || // проверка строки board[i][col] == digit || // проверка столбца board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] == digit) // проверка квадрата return false; return true; } public: void read() { for (auto &row : board) std::getline(std::cin, row); } void print() const { for (auto &row : board) std::cout << row << '\n'; std::cout << '\n'; } bool solve(int row = 0, int col = 0) { if (col == 9) return solve(row + 1, 0); // в конце строки переходим на следующую if (row == 9) return true; // если достигнут конец доски, то она решена if (board[row][col] != '0') return solve(row, col + 1); // если ячейка не пустая пропускаем её for (char d = '1'; d <= '9'; ++d) // перебираем все цифры if (is_valid(row, col, d)) { // если цифра удовлетворяет правилам судоку board[row][col] = d; // записываем её в ячейку if (solve(row, col + 1)) // переходим к следующей ячейке return true; // если решение найдено, то заканчиваем работу board[row][col] = '0'; // если решение не найдено, возвращаемся назад } return false; // если перебрали все цифры и ни одна не подходит, то решения нет } }; int main() { Sudoku sudoku{}; int n; std::cin >> n; std::cin.ignore(); while (n--) { sudoku.read(); sudoku.solve(); sudoku.print(); } } |
Решение
В коде выше реализовано решение судоку при помощи перебора с возвратом (backtracking). Метод перебора с возвратом это общий метод нахождения решений задачи, в которой требуется полный перебор (brute-force search) всех возможных вариантов. Решение задачи методом перебора с возвратом строится конструктивно последовательным расширением частичного решения. Если на конкретном шаге такое расширение провести не удается, то происходит возврат к более короткому частичному решению, и попытки его расширить продолжаются. Судоку сводится к задаче точного покрытия множества (exact cover), которая является NP-полной, и решается полным перебором.
Ссылки
- Задача на e-olymp
- Код решения на ideone
- Засчитанное решение на e-olymp
