Задача 96
Су Доку

Су Доку (по-японски значит место числа) - название популярной головоломки. Ее происхождление неизвестно, однако нужно отдать должное Леонарду Эйлеру, который придумал идею похожей, но более сложной головоломки под названием Латинские Квадраты. Целью Су Доку является заменить пустые места (или нули) в сетке 9 x 9 цифрами таким образом, чтобы в каждой строке, колонке и квадрате 3 x 3 содержались все цифры от 1 до 9. Ниже приведен пример типичной исходной головоломки и ее решение.

0 0 3
9 0 0
0 0 1
0 2 0
3 0 5
8 0 6
6 0 0
0 0 1
4 0 0
0 0 8
7 0 0
0 0 6
1 0 2
0 0 0
7 0 8
9 0 0
0 0 8
2 0 0
0 0 2
8 0 0
0 0 5
6 0 9
2 0 3
0 1 0
5 0 0
0 0 9
3 0 0

4 8 3
9 6 7
2 5 1
9 2 1
3 4 5
8 7 6
6 5 7
8 2 1
4 9 3
5 4 8
7 2 9
1 3 6
1 3 2
5 6 4
7 9 8
9 7 6
1 3 8
2 4 5
3 7 2
8 1 4
6 9 5
6 8 9
2 5 3
4 1 7
5 1 4
7 6 9
3 8 2

Правильно составленная головоломка Су Доку имеет единственное решение и может быть решена с помощью логики, однако иногда необходимо применять метод "гадай и проверяй", чтобы исключить неверные варианты (существует очень спорное мнение по этому поводу). Сложность поиска определяет уровень головоломки. Приведенный выше пример считается легким, так как его можно решить прямой дедукцией.

6 КБ текстовый файл sudoku.txt (правый клик и Save Link/Target As...) содержит пятьдесят разных головоломок Су Доку различной сложности, но каждая имеет единственное решение (первая головоломка в файле рассмотрена выше).

Решив все пятьдесят головоломок, найдите сумму трехзначных чисел, находящихся в верхнем левом углу каждого решения. Например, 483 является трехзначным числом, находящимся в верхнем левом углу приведенного выше решения.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net