Развитие познавательных способностей по математике, 9-11 класс

Как решать судоку: способы, методы, стратегия ……………….

Что такое судоку? Это многими любимая, почти математическая головоломка [1] . Судоку печатается многими газетами и журналами, издаются брошюры – сборники судоку, существует настольная игра «Судоку». Иногда судоку называют кубиком Рубика 21 века. Три года назад, увидев судоку в газете, очень заинтересовалась ими. Прочитав правила, научилась разгадывать головоломки легкого уровня, а немного позднее – среднего. Затем возникли вопросы: «А можно ли составлять судоку самой? С какой комбинацией цифр это возможно? Сколько различных вариантов игры существует? Есть ли универсальный способ решения?» Начала с составления легкого судоку, стремясь количество изначально входящих цифр свести до минимума. Получалось не все. Поэтому пришла к мысли изучить судоку подробнее. Приступая к выполнению данной работы, ставила перед собой основную цель: научиться составлять судоку разного уровня сложности. Для достижения поставленной цели нужно решить задачи:

1. познакомиться с историей возникновения судоку;

2.изучить разновидности, уровни сложности, методику решения;

3.узнать математическую основу судоку.

В ходе работы в большей степени пользовалась интернет – источниками, использовала работы Б.А. Кордемского «Математическая смекалка», М.М. Постникова «Магические квадраты» и другие.

История возникновения судоку

Судоку — это головоломка - пазл с числами, ставшая в последнее время очень популярной. В переводе с японского «су» — «цифра», «доку» — «стоящая отдельно» [2] . Иногда судоку называют «магическим квадратом», что в общем-то неверно, так как судоку является латинским квадратом 9-го порядка. Судоку активно публикуют газеты и журналы разных стран мира, сборники судоку издаются большими тиражами. Решение судоку — популярный вид досуга.

История судоку как игры восходит к имени знаменитого швейцарского математика, механика и физика Леонарда Эйлера (1707 – 1783) [3] . В бумагах его архива, датированных 17 октября 1776 года, содержатся записи о том, как образовать магический квадрат с определенным числом ячеек, особенно 9, 16, 25 и 36. В другом документе, озаглавленном «Научное исследование новых разновидностей магического квадрата» Эйлер помещал в клетки латинские буквы (латинский квадрат), позже он заполнил клетки греческими буквами и называл квадрат греко-латинским. Исследуя различные варианты магического квадрата, Эйлер обратил внимание на проблему комбинации символов таким образом, чтобы не один из них не повторялся ни в одной строке и ни в одном столбце.

В современном виде головоломки судоку впервые были опубликованы в 1979 году в журнале Word Games magazine [4] .

Журналы рекомендуют детям и взрослым играть в эту игру для совершенствования логики мышления, считается, что игра замедляет развитие умственных расстройств у людей, страдающих болезнью Альцгеймера. Судоку называют кубиком Рубика 21 века, а также самой захватывающей головоломкой в мире [3] .

Судоку – это всеми нами любимая, почти математическая головоломка.

САМУРАЙ СУДОКУ [5]

Представляет собой комбинацию из 5-ти судоку с общими блоками (рис.1). При этом каждая из этих 5-ти головоломок не может быть решена по отдельности, существует только общее решение. Задания в общих блоках отсутствуют.

СУДОКУ 2 D

Другое название - Latin Square.

В этой головоломке - предшественнице судоку - отсутствуют блоки, т.е. числа не должны повторяться только в строках и столбцах (рис. 2).

Другие названия - Alphadoku , Godoku . В этом варианте судоку вместо цифр используются буквы латинского алфавита (рис. 3).

В этом варианте головоломки судоку основные диагонали так же не должны содержать повторяющихся цифр (рис.4).

КЛАССИЧЕСКАЯ СУДОКУ (рис.5)

СУДОКУ-ПАЗЛ (рис.6)

Другие названия - Jigsaw Sudoku, Nonomino Sudoku, Irregular Sudoku . В этом варианте головоломки судоку блоки имеют произвольную форму.

ЦВЕТНАЯ СУДОКУ [6]

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

Настольная судоку [7] .

Настольная судоку - это игральное поле, черные фишки цифр и задачи различной сложности. В "бумажный" вариант судоку играть надо одному. Но используя фишки – цифры разных цветов, можно попробовать играть вдвоем или даже вчетвером. ВЫ этом случае играть нужно на время, фиксируя время следующего хода каждого игрока. Настольную игру "Судоку" можно брать с собой в дорогу и играть, играть и играть, ведь решив задачу один раз не надо стирать решение ластиком с бумаги - сбросьте фишки цифр с игральной доски и начинайте партию заново!

Уровни сложности судоку

Сложность судоку определяется геометрией расставленных цифр, которая в свою очередь определяет ход разгадывания [8] . В простых судоку всегда существует следующая цифра, которую можно разгадать единственным образом на основе её простого отсутствия в какой-либо строке, столбце, квадратике. В судоку средней сложности некоторые цифры, как правило, две-три, можно разгадать, сделав предположение первого уровня (из двух цифр или комбинаций). В сложных судоку уровень предположения некоторых цифр может достигать двух или трёх:

1) предположим, что, далее…

2) в этом случае, предположим, что…

3) на основе двух предположений, предположим, что.

В большинстве изданий, авторами практикуется вносить много избыточных цифр, которые читатель мог бы угадать сам, не выходя из уровня сложности. Очевидно, так судоку разгадать быстрее. Но правилом хорошего тона считается другое. Нужно стараться делать все судоку: и лёгкие, и сложные без избытка, т.е. с минимально возможным набором предопределенных цифр.

Примеры судоку разного уровня сложности (рис.7).

Как решать судоку: способы, методы и стратегия

Поле судоку представляет собой таблицу 9х9 клеток. В каждую клетку заносится цифра от 1 до 9. Цель игры: расположить цифры таким образом, чтобы в каждой строке, в каждом столбце и в каждом блоке 3х3 не было повторений. Другими словами, в каждом столбце, строке и блоке должны быть все цифры от 1 до 9.Для решения задачи в пустые клетки можно записывать кандидатов. Например, рассмотрим клетку 2-го столбца 4-ой строки (рис.8): в столбце, в котором она находится, уже имеются цифры 7 и 8, в строке - цифры 1, 6, 9 и 4, в блоке - 1, 2, 8 и 9. Следовательно, из кандидатов в данной ячейке вычеркиваем 1, 2, 4, 6, 7, 8, 9, и у нас остается только два возможных кандидата – 3 и 5.

Аналогично, рассматриваем возможных кандидатов для других ячеек и получаем следующую таблицу (рис.9).

С кандидатами решать интереснее и можно применять различные логические методы. Далее мы рассмотрим некоторые из них.

Метод заключается в отыскании в таблице одиночек, т.е. ячеек, в которых возможна только одна цифра и никакая другая. Записываем эту цифру в данную ячейку и исключаем ее из других клеток этой строки, столбца и блока. Например, в таблице на рисунке 10 имеются три «одиночки» (они выделены желтым цветом).

Скрытые одиночки

Если в ячейке стоит несколько кандидатов, но один из них не встречается больше ни в одной другой ячейке данной строки (столбца или блока), то такой кандидат называется «скрытой одиночкой». В примере на рисунке 11 кандидат «4» в зеленом блоке найден только в центральной ячейке. Значит, в этой ячейке обязательно будет «4». Заносим «4» в данную ячейку и вычеркиваем из других ячеек 2-го столбца и 5-ой строки. Аналогично, в желтом столбце кандидат «2» встречается один раз, следовательно, в данную ячейку заносим «2» и исключаем «2» из ячеек 7-ой строки и соответствующего блока.

Предыдущие два метода – это единственные методы, которые однозначно определяют содержимое ячейки. Следующие методы позволяют только уменьшать количество кандидатов в ячейках, что рано или поздно приведет к одиночкам или скрытым одиночкам.

Запертый кандидат

Бывают случаи, когда кандидат в пределах блока находится только в одном строке (или в одном столбце). В силу того, что одна из этих ячеек обязательно будет содержать этого кандидата, из всех остальных ячеек данной строки (столбца) этого кандидата можно исключить. В примере на рисунке 12 центральный блок содержит кандидата «2» только в центральном столбце (желтые ячейки). Значит, одна из этих двух ячеек точно должна быть «2», и никакие другие ячейки в том ряду вне этого блока не могут быть «2». Поэтому «2» может быть исключен как кандидат из других ячеек этого столбца (ячейки зеленого цвета).

Открытые пары

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

Тоже самое правило можно сформулировать для 3 и 4-х кандидатов, только участвует уже 3 и 4 ячейки, соответственно. Открытые тройки: из ячеек зеленого цвета исключаем значения ячеек желтого цвета (рис.14).

Открытые четверки: из ячеек зеленого цвета исключаем значения ячеек желтого цвета (рис.15).

Скрытые пары

Если в двух ячейках в группе (строке, столбце, блоке) содержат кандидаты, среди которых идентичная пара, не встречающаяся ни в одной другой ячейке данного блока, то никакие другие ячейки этой группы не могут иметь значения этой пары. Следовательно, все другие кандидаты этих двух ячеек могут быть исключены. В примере на рисунке 16 кандидаты «7» и «5» в центральной колонке находятся только в ячейках желтого цвета, значит, всех остальных кандидатов из этих ячеек можно исключить.

Аналогично, можно искать скрытые тройки и четверки.

x - wing

Если значение имеет только два возможных местоположения в какой-то строке (столбце), то оно обязательно должно быть назначено в одну из этих ячеек. Если же существует еще одна строка (столбец), где этот же кандидат также может быть только в двух ячейках и столбцы (строки) этих ячеек совпадают, то ни одна другая ячейка этих столбцов (строк) не может содержать данную цифру (рис. 17). В 4-ой и 5-ой строках цифра «2» может быть только в двух ячейка желтого цвета, при чем эти ячейки находятся в одинаковых столбцах. Следовательно, цифра «2» может быть записана только двумя способами: 1) если «2» записать в 5-ый столбец 4-ой строки, то из желтых ячеек «2» надо исключит и тогда в 5-ой строке положение «2» определяется однозначно 7-ым столбцом (рис.18). 2) если «2» записать в 7-ой столбец 4-ой строки, то из желтых ячеек «2» надо исключит и тогда в 5-ой строке положение «2» определяется однозначно 5-ым столбцом (рис.19).

Следовательно, 5-ый и 7-ой столбец обязательно будут иметь цифру «2» либо в 4-ой строке, либо в 5-ой. Тогда из других ячеек данных столбцов цифру «2» можно исключить (зеленые клетки).

Математик Бертхам Фельгенхауэр посчитал количество теоретических комбинаций в стандартном поле размерами 9 на 9, и пришёл к выводу, что там можно сделать 6 670 903 752 021 072 936 960 [9] (6 секстиллионов 670 квинтиллионов 903 квадриллионов 752 триллиона 21 миллиард 72 миллиона 936 тысяч 960) разных судоку.

Латинский квадрат — таблица n × n , заполненная n различными символами таким образом, чтобы в каждой строке и в каждом столбце встречались все n символов (каждый по одному разу) [10] . Ниже приводятся два примера:

Латинский квадрат существует для любого n . Свое название он берёт начало от Леонарда Эйлера, который использовал латинские буквы вместо цифр в таблице.

Два латинских квадрата называются ортогональными , если различны все пары символов ( a , b ), где a - символ в некоторой клетке первого латинского квадрата, b - символ в той же клетке второго латинского квадрата. Пример пары ортогональных латинских квадратов:

Среди всех латинских квадратов наибольший интерес представляют магические квадраты.

Магический , или волшебный квадрат — это квадратная таблица , заполненная n 2 числами таким образом, что сумма чисел в каждой строке, каждом столбце и на обеих диагоналях одинакова. Если в квадрате равны суммы чисел только в строках и столбцах, то он называется полумагическим . Нормальным называется магический квадрат, заполненный целыми числами от 1 до n 2 . Магический квадрат называется симметричным , если сумма любых двух чисел, расположенных симметрично относительно центра квадрата, равна n 2 + 1.

Нормальные магические квадраты существуют для всех порядков , за исключением n = 2, хотя случай n = 1 совсем прост - квадрат состоит из одного числа. Минимальный непростейший случай показан ниже, он имеет порядок 3(рис.20).