каталог статей
Поиск:
пример: сотовые телефоны расширенный поиск
Начало » » » Как решать судоку?

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

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

В 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 для горизонтальных и вертикальных третей матрицы, мы можем однозначно расставить числа в секторе их пересечения. Это и есть основное правило решения судоку, которое позволяет решить задачи любого уровня сложности.

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

Ресурсы судоку

Судоку онлайн.
Судоку оффлайн.
Клуб любителей судоку

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

Постоянный адрес статьи

Послать ссылку на этот обзор другу по ICQ или E-Mail:


Разместить у себя на ресурсе или в ЖЖ:


На любом форуме в своем сообщении:

Рейтинг статьи

Рейтинг: 3.0/5 (287 голосов)

Добавить на News2.ru Google slashdot YahooMyWeb Digg Technorati Delicious Забобрить эту страницу! Добавить на Newsland.ru Добавить на СМИ2 Добавить на RUmarkz Добавить на Ваау! Добавить на rucity.com Добавить в закладки МоёМесто.ru Добавить на Habr Добавить на Moi Novosti Добавить страницу к Mister Wong Добавить на Moikrug Добавить на Myscoop Добавить на 100zakladok Добавить на NewsGrad




Похожие статьи

1: Видеоигры - в чём их польза?
Хотел бы вам рассказать такую историю. В 10 лет мне купили компьютер. Для каждого школьника это было бы необычайно приятно, как впрочем, и для меня. И вот я начал осваиваться на компьютере, и первое, ...

2: Что такое судоку, или Как решить числовой кроссворд?
Кроссворды... Трудно представить нашу жизнь без них. Мы их решаем всегда и везде: для азарта, удовольствия, да и просто чтобы скоротать время в электричке по дороге на работу. Более того, кроссворды т...

3: Как себя побаловать, или Маленькие радости на каждый день
Себя, любимую, надо баловать. Ежедневно, ежечасно. Потому что наша жизнь - это вовсе не ожидание светлого "завтра". Надо получать удовольствие от каждой прожитой минуты. И не откладывать на ...

4: Как провоцируют зависимость разные компьютерные игры?
По данным специалистов, около 30% людей, увлекающихся компьютерными играми, злоупотребляют нахождением в виртуальности, а 10% – находятся в стадии психологической зависимости. Так можно ли считать ком...

5: YouTube объявил войну бандитским роликам
Видеосервис YouTube, принадлежащий Google, решил не размещать видеоролики, где члены различных банд демонстрируют холодное и огнестрельное оружие, пишет The Times. Как отмечает The Guardian, новые пра...




Copyright © 2006-2019 ExcelioN
Правовая информация
Все права защищены
.