Математичекая основа судоку


XVII ГОРОДСКАЯ НАУЧНО-ПРАКТИЧЕСКАЯ КОНФЕРЕНЦИЯ
«Первые шаги в науку – 2014»
Секция МАТЕМАТИКА
Математическая основа судоку
(исследовательcкая работа)
Выполнила:
Васильева Екатерина
ученицы 6а класса
МБОУ «Гимназия»
Руководитель работы:
Егармина Л.В.
учитель математики
высшей категории
МБОУ «Гимназия»
Лесосибирск, 2014
Оглавление
TOC \h \z \t "Иой заголовок 1;1;Мой заголовок 2;2"
Введение PAGEREF _Toc378716800 \h 3Основная часть PAGEREF _Toc378716801 \h 4§1. Правила игры Судоку PAGEREF _Toc378716802 \h 4§2. История происхождения PAGEREF _Toc378716807 \h 4§3. Способы и стратегии в решении судоку PAGEREF _Toc378716812 \h 5§4. Разновидности судоку PAGEREF _Toc378716837 \h 10§5. Практическое применение изученных методов в разгадывании судоку PAGEREF _Toc378716843 \h 11§6. Соревнования по решению судоку PAGEREF _Toc378716847 \h 13§7. Определение уровня мастерства разгадывания судоку PAGEREF _Toc378716857 \h 14Заключение PAGEREF _Toc378716862 \h 17Литература PAGEREF _Toc378716863 \h 18
ВведениеУмные люди на то и умны, чтобы разбираться в запутанных вещах.
М.Булгаков.
В незапамятные времена, научившись считать, люди познали меру количества – число. Вглядываясь в сочетания чисел, они с изумлением увидели, что числа имеют какую-то самостоятельную жизнь, удивительную и полную тайны; тайны необъяснимой и поэтому загадочной и многозначительной.
Полки книжного магазина пестрят различными кроссвордами и головоломками для организации досуга людей. Одной из разновидностей предлагаемых нам головоломок является судоку. Меня очень заинтересовала эта головоломка, но тут появилась проблема: я не знаю, что это такое и не умею их разгадывать.
Выдвинем гипотезу: ученик 6 класса может научиться разгадывать судоку..
Цель исследования: изучив правила и методы разгадывания научиться практически разгадывать судоку.
Задачи исследования:
изучить необходимый теоретический материал по теме;
выяснить математическую основу головоломки: способы решения и стратегии;
рассмотреть разновидности судоку;
применить изученные способы на практике, разгадав судоку разных уровней сложности;
определить свой уровень и уровни одноклассников в разгадывании судоку.
Объектом исследования являются головоломки. Предметом нашего исследования является игра Судоку.
Методы исследования: изучение литературы, анализ продуктов деятельности, сравнение и сопоставление, анкетирование.


Основная часть§1. Правила игры Судоку3903980417195Судоку — популярная головоломка с числами. В переводе с японского «су:» — «цифра», «доку» — «стоящая отдельно».рис. 1
Игровое поле представляет собой квадрат размером 9×9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом, всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9), называемые подсказками. От игрока требуется заполнить свободные клетки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась бы только один раз.Сложность судоку зависит не от количества изначально заполненных клеток, а от методов, которые нужно применять для её решения. Самые простые решаются дедуктивно: всегда есть хотя бы одна клетка, куда подходит только одно число. Некоторые головоломки можно решить за несколько минут, на другие можно потратить часы.Правильно составленная головоломка имеет только одно решение. Тем не менее, на некоторых сайтах в интернете под видом усложнённых головоломок пользователю предлагаются варианты судоку с несколькими вариантами решения, а также с ветвлениями самого хода решения.§2. История происхожденияИстория судоку как игры восходит к имени знаменитого швейцарского математика, механика и физика Леонарда Эйлера (1707 – 1783) (рис. 2). В 17 веке он изобрел игру «Латинский квадрат».
В современном виде головоломки судоку впервые были опубликованы в США в 1979 году в журнале Word Games magazine (рис. 3). Автором головоломки был Гарвард Гарис. Он испольовал принцип латинского квадрата Эйлера, применил его в матрице размерностью 9х9 и добавил дополнительные ограничения, цифры не должны повторяться и во внутренних квадратах 3х3.376555076835205422576835-8318576835
рис. 4
рис. 3
рис. 2

В Японии эта головоломка была опубликована компанией Nicoly Inc., крупным издателем сборников различных головоломок, в газете Monthly Nicolist в апреле 1984 года под заголовком «Число может использоваться только один раз». Название головоломке дал руководитель Nicoli - Кадзи Маки (Кaji Maki). В названии Sudocu Su обозначает число, а doku – единственное.
12 ноября 2004 года британская газета The Times (рис. 4) впервые на своих страницах опубликовала головоломку судоку. Эта публикация стала сенсацией, головоломка быстро распространилась по всей Британии, Австралии, Новой Зеландии; приобрела популярность и в США.360616593980§3. Способы и стратегии в решении судокурис. 5
Для решения задачи в пустые клетки можно записывать кандидатов. Например, рассмотрим клетку 2-го столбца 4-ой строки: в столбце, в котором она находится, уже имеются цифры 7 и 8, в строке - цифры 1, 6, 9 и 4, в блоке - 1, 2, 8 и 9. Следовательно, из кандидатов в данной ячейке вычеркиваем 1, 2, 4, 6, 7, 8, 9, и у нас остается только два возможных кандидата – 3 и 5 (рис. 5).Аналогично, рассматриваем возможных кандидатов для других ячеек и получаем следующую таблицу (рис. 6):
107950-114300
рис. 6

2947035514985С кандидатами решать интереснее и можно применять различные логические методы. Далее мы рассмотрим некоторые из них.
ОдиночкиМетод заключается в отыскании в таблице одиночек, т.е. ячеек, в которых возможна только одна цифра и никакая другая. Записываем эту цифру в данную ячейку и исключаем ее из других клеток этой строки, столбца и блока. Например: в данной таблице имеются три «одиночки» (они выделены желтым цветом) (рис. 7)рис. 7
Скрытые одиночкиЕсли в ячейке стоит несколько кандидатов, но один из них не встречается больше ни в одной другой ячейке данной строки (столбца или блока), то такой кандидат называется «скрытой одиночкой». В следующем примере кандидат «4» в зеленом блоке найден только в центральной ячейке. Значит, в этой ячейке обязательно будет «4». Заносим «4» в данную ячейку и вычеркиваем из других ячеек 2-го столбца и 5-ой строки. Аналогично, в желтом столбце кандидат «2» встречается один раз, следовательно, в -221615-114300данную ячейку заносим «2» и исключаем «2» из ячеек 7-ой строки и соответствующего блока (рис. 8).Предыдущие два метода – это единственные методы, которые однозначно определяют содержимое ячейки. Следующие методы позволяют только уменьшать количество кандидатов в ячейках, что рано или поздно приведет к одиночкам или скрытым одиночкам.рис. 8

Запертый кандидат3002280472440Бывают случаи, когда кандидат в пределах блока находится только в одном строке (или в одном столбце). В силу того, что одна из этих ячеек обязательно будет содержать этого кандидата, из всех остальных ячеек данной строки (столбца) этого кандидата можно исключить.В примере ниже, центральный блок содержит кандидата «2» только в центральном столбце (желтые ячейки). Значит, одна из этих двух ячеек точно должна быть «2», и никакие другие ячейки в том ряду вне этого блока не могут быть «2». Поэтому «2» может быть исключен как кандидат из других ячеек этого столбца (ячейки зеленого цвета).рис. 9
(рис. 9)Открытые парыЕсли две ячейки в группе (строке, столбце, блоке) содержат идентичную пару кандидатов и ничего более, то никакие другие ячейки этой группы не могут иметь значения этой пары. Эти 2 кандидата могут быть исключены из других ячеек в группе. В примере ниже, кандидаты «1» и «5» в колонках восемь и девять формируют Открытую Пару в пределах блока (желтые ячейки). Поэтому, так как одна из этих ячеек должна быть «1», а другая должны быть «5», кандидаты «1» и «5» исключаем из всех других ячеек этого блока (зеленые ячейки) (рис. 10).-221615-1269365
рис. 10

Тоже самое можно сформулировать для 3 и 4-х кандидатов, только участвует уже 3 и 4 ячейки, соответственно. Открытые тройки: из ячеек зеленого цвета исключаем значения ячеек желтого цвета (рис. 11).рис. 12
рис. 11
290449097790-38100097790
Открытые четверки: из ячеек зеленого цвета исключаем значения ячеек желтого цвета (рис. 12).Скрытые парырис. 13
2776855-93345Если в двух ячейках в группе (строке, столбце, блоке) содержаться кандидаты, среди которых идентичная пара, не встречающаяся ни в одной другой ячейке данного блока, то никакие другие ячейки этой группы не могут иметь значения этой пары. В примере ниже кандидаты «7» и «5» в центральной колонке находятся только в ячейках желтого цвета, значит, всех остальных кандидатов из этих ячеек можно исключить (рис. 13).X-wing-253365340995Если значение имеет только два возможных местоположения в какой-то строке (столбце), то оно обязательно должно быть назначено в одну из этих ячеек. Если же существует еще одна строка (столбец), где этот же кандидат также может быть только в двух ячейках и столбцы (строки) этих ячеек совпадают, то ни одна другая ячейка этих столбцов (строк) не может содержать данную цифру. Рассмотрим пример (рис. 14):рис. 14
В 4-ой и 5-ой строках цифра «2» может быть только в двух ячейках желтого цвета, причем эти ячейки находятся в одинаковых столбцах.
Следовательно, цифра «2» может быть записана только двумя способами:
если «2» записать в 5-ый столбец 4-ой строки, то из желтых ячеек «2» надо исключить и тогда в 5-ой строке положение «2» определяется однозначно 7-ым столбцом (рис. 15);3087370810895если «2» записать в 7-ой столбец 4-ой строки, то из желтых ячеек «2» надо исключить и тогда в 5-ой строке положение «2» определяется однозначно 5-ым столбцом (рис.16).-25336522225рис. 16
рис. 15

Следовательно 5-ый и 7-ой столбец обязательно будут иметь цифру «2» либо в 4-ой строке, либо в 5-ой. Тогда из других ячеек данных столбцов цифру «2» можно исключить (зеленые клетки).§4. Разновидности судокуКроме классической головоломки судоку существует множество других не менее увлекательных вариантов: ленты, строения, цепочка, судоку с «Загогулинами», крест, числовой кроссворд, расстояния, точки, четность, фигурная судоку, больше-меньше, нерегулярная судоку, судоку-пазл, счастливая семерка, магический квадрат, умножение, зигзаг судоку, XV-судоку, диагональная судоку, морской бой, трио судоку, полоски, сплит судоку, улитка, киллер, рото-судоку. Киллер
Используются стандартные ограничения судоку. Сумма цифр в каждом выделенном блоке указана в углу этого блока. В пределах выделенного блока цифры не должны повторяться (рис. 17)рис. 17
-114935-210185
352107554610Судоку – пазл
Целиком заполните сетку 9x9 цифрами от 1 до 9 так чтоб каждая цифра встречалась по одному разу в строке столбце и в каждом из 9 кусочке пазла (рис. 18).
рис. 18

рис. 14

§5. Практическое применение изученных методов в разгадывании судокуИзучив весь теоретический материал по теме, рассмотрев способы и стратегии в разгадывании судоку на примерах, попробуем сами разгадать предложенные нам головоломки. Начнем простого уровня сложности (рис. 19).Вот, что у нас получилось.5
7
2
2
6
4
8
5
1
2
7
6
6
5
3
7
8
4
5
5
8
7
6
5
6
3
1
6
4
3
5
1
3
5
рис. 19
-36576032385291084032385
Судоку среднего уровня сложности (рис. 20)7
8
6
5
4
72
5
4
9
1
6
3
5
9
9
3
6
7
1
7
6
5
3
2
2
6
8
4
3
9
8
4
2
7
2
7
1
6
7
3
1
8
9
2891790224155
рис. 20
-29908548895
Судоку сложного уровня (рис. 21)4
6
2
9
5
3
8
5
7
9
1
9
2
3
8
4
7
3
2
5
8
7
9
6
5
7
8
4
4
6
2
3
1
6
3
4
1
9
2
2
4
6
1
8
5
1
8
9
2
4
рис. 21
289179038100-12763538100
§6. Соревнования по решению судокурис. 22
1524071755Рекорд по разгадыванию судоку побит трижды. Мировой рекорд по разгадыванию судоку до последнего времени принадлежал бельгийцу Винценту Бертранд. Его время составляло 3 минуты 6 секунд. Оно было зафиксировано на Всемирном чемпионате Судоку в 2009 году в Словакии и занесено в книгу рекордов Гиннеса.
4530090523875 В июне 2010 на традиционном фестивале рекордов и курьезов в Чехии свои силы решили попробовать Яна Тилова (первая чемпионка мира), Гонза Кортек и Якуб Ондрошек.
рис. 23
В первой попытке Якуб сразу же установил новый рекорд 2 минуты 53 секунды, во второй попытке Кортек решил судоку за 2 минуты 16 секунд, но Якуб справился за 1 минуту 25 секунд. Таким образом, рекорд бельгийца был побит трижды, а Якуб Ондрошек стал новым рекордсменом по разгадыванию судоку.
Польский студент Ян Мрозовски стал двукратным чемпионом мира по решению головоломок судоку (рис. 24).
-127635127635В финальном состязании 23-летний Мрозовски, студент строительного факультета одного из университетов Кракова, решил десять головоломок за 54 минуты и 4 секунды. Этот результат обеспечил ему победу над соперниками и второй титул чемпиона мира.
19818351429385рис. 24
Второе место досталось представителю Чехии, а третье - японцу. Однако в общекомандном зачете победу праздновала Германия, набравшая наибольшее количество очков. В 2010 году за титул чемпиона мира боролись 120 представителей 32 стран мира. До Мрозовски одержать две победы подряд удалось также Томасу Снайдеру из США.
Чемпионат мира по судоку впервые прошел в Италии в городе Лука в 2006 году и с тех пор проводится ежегодно. Первым победителем стала Яна Тилова из Чехии (рис. 25).
-299085194945
рис. 25

Российский онлайн чемпионат по судоку 2010 состоялся 7 февраля.
рис. 26
Победителями стали: Jakub Hrazdira (Чехия, Злин) 534 балла, Hideaki Jo (Япония, Токио) 534 балла, Jan Mrozowski (Польша, Краков) 528 баллов.§7. Определение уровня мастерства разгадывания судокуВ открытом чемпионате по судоку США призы разыгрывались в трех категориях: начинающий, средний и продвинутый. Организаторы опубликовали правила, по которым участники могут заранее определить свой уровень мастерства.
Продвинутый уровень. Если вы можете решить обе судоку сложного уровня (рис. 27) менее чем за 30 минут (общее время), то поздравляем вас, вы продвинутый судокер.
805815-72390
рис. 27

Средний уровень. Если вы решили обе судоку среднего уровня сложности за 10-20 минут, то это ваш уровень (рис. 28).
95821529210
рис. 28

Начинающий уровень. Если вы закончили обе судоку простого уровня сложности менее чем за 10 минут, то попробуйте более сложные уровни. Если вы справились с простым уровнем сложности более, чем за 10 минут, то вы – начинающий судокер (рис. 29).739140168910
рис. 29

Определим свой уровень мастерства в разгадывании судоку.
-80010634365Предложенные два судоку простого уровня мною разгаданы за 30 минут (рис. 30). Значит я – начинающий судокер.
6
6
4
2
9
4
9
3
2
6
5
7
3
5
4
6
9
2
2
4
8
7
5
3
6
1
3
9
4
7
9
4
2
7
5
1
5
5
2
7
1
3
4
8
6
7
9
8
6
8
2
9
3
4
1
7
5
7
8
9
6
2
6
4
5
7
8
9
1
1
9
5
8
3
5
6
9
1
2
4
7
3
2
1
4
9
7
8
1
2
3
5
6
4
9
3
1

рис. 30

Нами проведено анкетирование учащихся 6а класса МБОУ «Гимназия». Ребятам были предложены следующие вопросы:
Знакомы ли вы с такой головоломкой как судоку?
Умеете ли вы разгадывать судоку?
Ребятам, которые положительно ответили на последний вопрос было предложено разгадать два судоку простого уровня и определить по времени угадывания уровень их мастерства.
Получили следующие результаты.
В опросе принимали участие 26 человек.
Знакомы с судоку - 10 чел. не знакомы с судоку – 16 чел.
Умеют разгадывать - 3 чел. не умеют разгадывать – 23 чел.
Кроме того был проверен уровень мастерства у этих 3 учащихся и выяснилось, что предложенные два судоку ребята разгадали за урок 45 мин. Значит, они тоже начинающие судокеры.
ЗаключениеИнтересно отметить, что задача судоку чрезвычайно популярна по нескольким причинам. Судоку развивает память, логическое мышление, помогает с концентрацией внимания. Судоку полезна в любом возрасте для развития умственных способностей и поддержания их в отличном состоянии. Психологи утверждают, что судоку позволяет излечить депрессию.
Заслуживает внимания то, что эта задача судоку вызвала несколько проблем математической природы, которые пока нерешены. Проблема "минимальной задачи судоку": существование задачи судоку с 16 или меньшими данными, которые допускают единственное решение.
В результате исследования мы достигли поставленной цели: изучив правила и методы разгадывания научились практически разгадывать судоку, что доказали разгадыванием судоку различных уровней сложности. Тем самым мы подтвердили нашу гипотезу: ученик 6 класса может научиться разгадывать судоку. В процессе исследования мы определили свой уровень и уровни одноклассников в разгадывании судоку. Нам всем есть, куда стремиться и усовершенствовать свое мастерство.

ЛитератураАдолин В.А. Самоучитель решения судоку / В.А. Адолин. – М.: Мир, 2005. – 150 с.
Леонтьева О.С. Судоку. Супер головоломки / О.С. Леонтьева. – М.: Маг, 2003. – 120 с.
Херон Э. Судоку для «чайников» / Э.Херон, Э.Джеймс. – М.: Диалектика, 2007. – 336 с.
Википедия. Свободная энциклопедия [электронный ресурс] / Режим доступа: http://ru.wikipedia.org/wiki/%D1%F3%E4%EE%EA%F3Судоку-клуб [электронный ресурс] / Режим доступа: http://www.sudoku-club.ru/blog/vash-uroven-sudoku.html

Приложенные файлы

  • docx file4
    Размер файла: 1 MB Загрузок: 1

Добавить комментарий