В 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 для горизонтальных и вертикальных третей матрицы, мы можем однозначно расставить числа в секторе их пересечения. Это и есть основное правило решения судоку, которое позволяет решить задачи любого уровня сложности.
Итак, у вас теперь в руках есть всё, что вам потребуется для этой увлекательной и развивающей логическое мышление игры!
Ресурсы судоку
Судоку онлайн.
Судоку оффлайн.
Клуб любителей судоку
Играйте на здоровье!
Что то я зашел в тупик, объясните плис логику дальнейшего решения,файл прилагаются
0 Ответить
Роман Журавлев, а где файл?
Оценка статьи: 5
0 Ответить
Виктор Губерниев,
Я извеняюсь, но в статье всё очень запутанно. и понять, а тем более научиться решать судоку по этой статье по моему невозможно.
Оценка статьи: 3
0 Ответить
присоеденяюсь ко всем комментариям...решать судоку умею и люблю, но если прочитают эту статью те кто не умеет ее решать то, что они не научиться - это точно, да к тому же после всех этих вычислений и желание пропадет учиться
Оценка статьи: 1
0 Ответить
на эту тему уже была опубликована другая статья, написанная более понятным и легким языком...
на самом же деле решать судоку намного проще, чем может показаться после прочтения Вашей, виктор, статьи..
Оценка статьи: 3
0 Ответить
Абсолютно нечитабельный текст. Хороший пример того, насколько проигрывает естественный язык (в данном случае русский) языку математических формул и языкам программирования при описании формальных алгоритмов.
Насколько я понимаю, в статье предпринята попытка описать один из возможных алгоритмов автоматического решения судоку при помощи компьютера, который умеет только тупо складывать, вычитать и сравнивать числа на больше-меньше-равно. Живой мозг (мой, во всяком случае, точно) при решении судоку прекрасно обходится без явного вычисления всех этих сумм и разностей.
Оценка статьи: 3
0 Ответить
Так люблю решать судоку, но в статье все так запутано... не хватило даже сил дочитать до конца...
Оценка статьи: 4
0 Ответить