В мир информатики # 78 (1—15 октября).
“Ломаем” голову
Судоку
Как вы, наверное, знаете, в последнее
время в изданиях, публикующих кроссворды,
сканворды и другие головоломки, появились
головоломки, называемые судоку (такое
название имеет японское происхождение). Перед
вами судоку — квадрат 9 х 9:
Он разбит на 9 квадратиков 3 х 3. Задача
состоит в том, чтобы заполнить пустые клетки
таким образом, чтобы в каждом квадратике, в
каждой строке и каждом столбце “большого”
квадрата был полный набор цифр от 1 до 9.
Ясно, что такую задачу путем подбора не
сделаешь. Судоку можно решить только путем
логических умозаключений.
В ряде случаев решение очевидно:
Однако такие ситуации встречаются, как
правило, в конце решения.
Можно привести несколько методов,
которые применяются для нахождения цифры в
какой-то клетке. Прежде чем излагать их,
договоримся столбцы таблицы при рассмотрении их
слева направо обозначать буквами a, b, c,
d, e, f, g, h и i, а строки —
числами от 1
до 9 (при счете снизу вверх). Тогда координаты
отдельной клетки можно задавать в виде b2, i9
и т.п.
Итак, несколько методов решения.
1. Исключение цифр, которые не могут
быть записаны в клетке
Например, рассмотрев цифры, которые не
могут быть записаны в клетке d5, можно понять,
что в этой клетке можно записать только одну
цифру — 2. Некоторые любители судоку записывают
“невозможные” цифры в виде точек в клетке:
 ·
Примечание. На рисунке клетка
показана в увеличенном масштабе.
Можно также наоборот — записывать
(например, карандашом) в клетке только те цифры,
которые могут быть представлены в ней. Если такая
цифра одна, то она и должна быть записана в этой
клетке. Если “возможных” цифр несколько, то и
это будет полезным (потом из них будет отобрана
единственная цифра). Так удобно поступать, когда
“возможных” цифр немного — не более четырех.
Записав найденную цифру (2), можно
аналогичным методом установить цифру в клетке f5
— это 4.
2. Нахождение клеток для двух
оставшихся цифр путем исключения клетки для
одной из них
Рассмотрим столбец d. В нем
остались незаписанными цифры 1 и 3. Видно, однако,
что в клетке цифра 1 не может быть представлена.
Следовательно, 1 нужно записать в d8, а 3 — в d2.
Этот метод можно применять и для строк,
и для квадратиков, в которых остались
незаполненными две клетки:
Конечно, ситуации, при которых
используются оба приведенных метода, также
встречаются, как правило, в конце решения.
3. Определение единственно возможной
клетки квадратика, в которой может быть записана
некоторая цифра
Рассмотрим квадратик в центре
приведенного в начале статьи судоку. Где в нем
может быть записана цифра 7? В столбцах e и f
и в строке 5 она уже представлена, следовательно,
единственно возможная клетка для этой цифры — d4.
Еще пример:
Где в правом среднем квадратике может
быть записана цифра 5?
Этот метод удобно применять в случаях,
когда в строке, в столбце или в квадратике
остались незаполненными 2–4 цифры:
4. Учет наличия “сдвоенных” цифр
Этот метод используется в случаях,
когда методом исключения (см. выше) установлено,
что в клетке может быть записана одна из нескольких
еще неиспользованных цифр. Например, установлены
возможные цифры в трех клетках:
Две цифры будем называть
“сдвоенными”, если их (и только их) можно
записать в две некоторые клетки. В только что
приведенном примере сдвоенными являются цифры 2
и 8.
Можно понять, что во второй справа
клетке может быть записана только цифра 5.
Предлагаем читателям доказать это утверждение с
помощью законов логики4 .
Другой пример — если возможные цифры
следующие:
— то можно убедиться, что в третьей
слева клетке цифра 4 записана быть не может.
Доказательство этого факта также предлагаем
читателям провести самостоятельно.
В общем случае рассматриваемый метод
можно сформулировать так: если в строке, в
столбце или в квадратике имеются сдвоенные
цифры, то они не могут быть представлены ни в
одной из остальных клеток строки, столбца или
квадратика.
5. Учет наличия “строенных” цифр
Этот метод аналогичен предыдущему, но
связан с тремя цифрами. Три цифры x, y, z
будем называть “строенными”, если их (и только
их) можно записать в три некоторые клетки:
Здесь также можно доказать, что ни одна
из этих цифр не может быть представлена ни в
одной из остальных клеток строки (аналогично —
столбца или квадратика). Это же правило
распространяется и на такой вариант возможного
расположения цифр x, y, z:
Присылайте в редакцию также полное
решение приведенного выше судоку. Все приславшие
правильное решение будут награждены дипломами. |