Как решать судоку?

Латинский квадрат

В XVIII веке великий швейцарский математик Леонард Эйлер придумал занятную числовую структуру, названную «латинский квадрат» (Carré latin), которая стала прообразом новой игры – числового кроссворда, появившегося в США в 70-х годах прошлого века. Особой популярности эта игра в те годы не имела, т.к. не соответствовала динамичному американскому менталитету. Однако, попав в Японию спустя десятилетие, игра обрела огромную популярность и получила название «Судоку» (в переводе с японского дословно означает «числа-рядом»). Уже из Японии игра стремительно распространилась по всему миру, составив серьёзную конкуренцию обычным кроссвордам.

Правила игры

Правила игры просты: в классическом варианте задаётся матрица размером 9х9, разделённая на 9 блоков размером 3х3. Часть клеток заранее заполнена цифрами от 1 до 9. Чем меньше клеток заранее заполнено, тем выше сложность игры. Блоки размером 3х3, очерченные жирной линией, я буду называть секторами, ряды клеток, расположенных по горизонтали – строками, а по вертикали – столбцами. Сектора, строки и столбцы я буду в целом называть кластерами, а всю исходную таблицу 9х9 – матрицей. Единственное правило этой замечательной игры заключается в том, что цифры в каждом кластере матрицы не должны повторяться.

Цель игры

Цель игры состоит в том, чтобы заполнить пустые клетки (ячейки) матрицы по правилам игры. Заполнять пустые ячейки рекомендуется карандашом, чтобы легко было исправить ошибки и убирать неверные варианты.

Решение судоку

Правило №1. Самое простое и очевидное правило заключается в том, что если в кластере не заполнена 1 ячейка, то она заполняется числом 45 – S, где S – сумма чисел в кластере.

Правило №2. Предположим, что мы достоверно знаем, что число N может быть только в двух незаполненных ячейках кластера. В этом случае эти ячейки я буду называть полузаполненными. Если только в этих же двух ячейках кластера может быть также число M, то эти ячейки следует считать заполненными. Итак, две ячейки, полузаполненные двумя цифрами, являются заполненными. Другими словами, в них не может быть никаких других цифр.

Из этого простого и очевидного правила есть интересное следствие: если в кластере не заполнены 3 ячейки, но две из них полузаполненны числами N и M, то в третьей ячейке должно находиться число 45 – N – M – S, где S – сумма заполненных цифр в кластере. Это следствие распространяется на любое число пар полузаполненных ячеек.

Правило №2А. Предположим, что мы достоверно знаем, что число N может быть только в трех незаполненных ячейках кластера. В этом случае эти ячейки я буду называть заполненными на 1/3. Если только в этих же трех ячейках кластера могут быть также числа M и L, то эти ячейки следует считать заполненными. Итак, три ячейки, заполненные на 1/3 тремя цифрами, являются заполненными. Другими словами, в них не может быть никаких других цифр.

Продолжая по индукции, получаем аналогичное правило для четырёх, пяти и т.д. ячеек.

Правило №3. Два кластера, имеющие общие ячейки, я буду называть сопряжёнными. Если один из сопряжённых кластеров – сектор, а другой – столбец или строка, то пересечение составляет три ячейки, если столбец и срока, то одну. Если в пересечении сопряжённых кластеров встречается число N, то оно не может быть в непересекающихся частях обоих кластеров.

Из этого очевидного правила есть следствие: если в непересекающейся части одного из сопряженных кластеров есть число N, то оно также есть в непересекающейся части другого кластера.

Из этого следствия получаем ещё одно правило:

Правило №4. Всю матрицу можно разделить по горизонтали и по вертикали на 3 равных части (трети) по три строки или три столбца. В каждой из этих частей каждое число встречается трижды: по одному разу в каждой строке (столбце), и в каждом секторе. Если число N в какой-либо трети встречается дважды, то третье число должно находиться на пересечении той строки (столбца) и того сектора, в которых это число не встречается.

А теперь самое интересное: это правило работает также для полузаполненных и на 1/3 заполненных ячеек, если они расположены в одном секторе и идут вдоль строки для горизонтальных (состоящих из строк) третей матрицы, и вдоль столбца для вертикальных (состоящих из столбцов) третей.

Пример: пусть одна из горизонтальных третей матрицы заполнена следующим образом:
2.х.х.х.х.х.х.х.х
Х.х.х.х.2?.2?.х.х.х
Х.х.х.х.х.х.z.z.z

Где х и z – незаполненные ячейки, а 2? – ячейки, полузаполненные числом 2.
Тогда пересечение нижней строки с последним сектором (клетки обозначенные буквой z) должны быть на 1/3 заполнены числом 2.

Сочетая правило №4 для горизонтальных и вертикальных третей матрицы, мы можем однозначно расставить числа в секторе их пересечения. Это и есть основное правило решения судоку, которое позволяет решить задачи любого уровня сложности.

Итак, у вас теперь в руках есть всё, что вам потребуется для этой увлекательной и развивающей логическое мышление игры!

Играйте на здоровье!

Автор: Bиктop Гyбepниeв
Просмотров страницы: 262