Требуется решить головоломку "судоку". На входе
головоломки "судоку" находится поле 9×9 клеток, некоторые
клетки поля пустые, в других записаны числа от 1 до 9. Требуется вписать в
пустые клетки числа от 1 до 9, чтобы стали выполняться следующие условия:
· в каждой строке находится перестановка чисел от 1 до
9,
· в каждом столбце находится перестановка чисел от 1 до
9 и
· в каждом из 9 квадратов 3×3 (на рисунках далее
разделены жирными линиями) находится перестановка чисел от 1 до 9.
|
Исходные данные
|
Решение
|
|
|
8
|
|
|
3
|
|
|
|
7
|
|
7
|
|
2
|
|
|
8
|
3
|
6
|
|
|
|
3
|
1
|
5
|
|
|
4
|
9
|
|
|
3
|
2
|
|
6
|
|
|
5
|
|
|
|
5
|
|
9
|
8
|
|
1
|
6
|
|
4
|
|
|
|
6
|
|
|
4
|
|
2
|
9
|
|
|
4
|
7
|
|
|
9
|
8
|
5
|
|
|
|
6
|
3
|
7
|
|
|
1
|
|
2
|
|
2
|
|
|
|
1
|
|
|
7
|
|
|
|
4
|
8
|
5
|
9
|
3
|
6
|
2
|
1
|
7
|
|
7
|
9
|
2
|
1
|
4
|
8
|
3
|
6
|
5
|
|
6
|
3
|
1
|
5
|
7
|
2
|
4
|
9
|
8
|
|
3
|
2
|
4
|
6
|
9
|
7
|
5
|
8
|
1
|
|
5
|
7
|
9
|
8
|
2
|
1
|
6
|
3
|
4
|
|
8
|
1
|
6
|
3
|
5
|
4
|
7
|
2
|
9
|
|
1
|
4
|
7
|
2
|
6
|
9
|
8
|
5
|
3
|
|
9
|
6
|
3
|
7
|
8
|
5
|
1
|
4
|
2
|
|
2
|
5
|
8
|
4
|
1
|
3
|
9
|
7
|
6
|
|
Гарантируется, что исходные данные таковы, что решение
существует и единственно.
Формат входных и выходных данных
Входные данные представляют собой 9 строк по 9 чисел,
числа в строках разделены одиночными пробелами. Число от 1 до 9 означает, что оно
находится в соответствующей клетке, число 0 означает, что клетка пуста.
Выведите в также 9 строк по 9 чисел, разделённых
одиночными пробелами — решение головоломки. До первого числа строки и после
последнего не должно быть пробелов.
Примеры
|
Входные данные
|
Выходные данные
|
|
0 8 0 0 3 0 0 0 7
7 0 2 0 0 8 3 6 0
0 3 1 5 0 0 4 9 0
3 2 0 6 0 0 5 0 0
5 0 9 8 0 1 6 0 4
0 0 6 0 0 4 0 2 9
0 4 7 0 0 9 8 5 0
0 6 3 7 0 0 1 0 2
2 0 0 0 1 0 0 7 0
|
4
8 5 9 3 6 2 1 7
7
9 2 1 4 8 3 6 5
6
3 1 5 7 2 4 9 8
3
2 4 6 9 7 5 8 1
5
7 9 8 2 1 6 3 4
8
1 6 3 5 4 7 2 9
1
4 7 2 6 9 8 5 3
9
6 3 7 8 5 1 4 2
2
5 8 4 1 3 9 7 6
|
|
0
3 0 0 0 0 6 0 0
0
2 0 0 8 0 0 0 0
1
0 0 9 0 0 0 3 0
0
0 0 0 0 0 4 0 7
6
0 0 0 0 0 0 0 2
0
0 0 1 0 0 0 0 0
0
0 9 0 0 0 0 0 3
8
0 1 0 6 0 0 0 0
0
0 0 0 2 7 0 0 8
|
4
3 8 7 5 1 6 2 9
9
2 5 6 8 3 7 4 1
1
6 7 9 4 2 8 3 5
5
1 3 2 9 6 4 8 7
6
9 4 8 7 5 3 1 2
7
8 2 1 3 4 9 5 6
2
7 9 4 1 8 5 6 3
8
5 1 3 6 9 2 7 4
3
4 6 5 2 7 1 9 8
|
