e-olymp 3522. Судоку

Задача

Судоку — это очень простая задача. Квадратная таблица из $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

Код

Решение

В коде выше реализовано решение судоку при помощи перебора с возвратом (backtracking). Метод перебора с возвратом это общий метод нахождения решений задачи, в которой требуется полный перебор (brute-force search) всех возможных вариантов. Решение задачи методом перебора с возвратом строится конструктивно последовательным расширением частичного решения. Если на конкретном шаге такое расширение провести не удается, то происходит возврат к более короткому частичному решению, и попытки его расширить продолжаются. Судоку сводится к задаче точного покрытия множества (exact cover), которая является NP-полной, и решается полным перебором.

Ссылки

Добавить комментарий