Кто придумал судоку


История судоку

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

Несмотря на японское название, история судоку начинается отнюдь не в Японии. Прообразом головоломки считают латинские квадраты Леонарда Эйлера – знаменитого математика, жившего в XVIII веке. Однако в таком виде, в котором она известна сегодня, ее изобрел Ховард Гарнс. Будучи по образованию архитектором, Гарнс попутно придумывал головоломки для журналов и газет. В 1979 году американское издание под названием «Dell Pencil Puzzles and Word Games» впервые напечатало на своих страницах судоку. Однако тогда головоломка не вызвала у читателей интереса.

Именно японцы первыми оценили ребус по достоинству. В 1984 году одно из японских печатных изданий впервые опубликовало головоломку. Она тут же получила широкое распространение. Тогда же головоломка и получила свое название — судоку. По-японски «су» означает «число», «доку» — «стоящее отдельно». Некоторое время спустя, этот ребус появился во многих печатных изданиях Японии. Кроме этого, выпускали отдельные сборники судоку. В 2004 году головоломку начали печатать газеты Великобритании, что положило начало распространению игры за пределами Японии.

Головоломка представляет собой квадратное поле со стороной из 9 клеток, поделенное в свою очередь на квадраты размером 3 на 3. Таким образом, большой квадрат поделен на 9 малых, общее количество ячеек которых составляет 81. В некоторых клетках изначально проставлены цифры-подсказки. Суть ребуса заключается в том, чтобы заполнить числами пустые ячейки так, чтобы ни в рядах, ни в колонках, ни в квадратах они не повторялись. В судоку используются цифры только от 1 до 9. От расположения цифр-подсказок зависит сложность головоломки. Самой сложной, конечно же, является та, которая имеет всего один вариант решения.

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

xn----dtbjalal8asil4g8c.xn--p1ai

Математики придумали формулу для решения cудоку

Для тех, кому нравится решать загадки cудоку самостоятельно и неспешно, формула, позволяющая быстро вычислить ответы, может показаться признанием слабости или жульничеством

Но для тех, кому разгадывание судоку стоит слишком больших усилий, это может быть буквально идеальным решением.

Два исследователя разработали математический алгоритм, который позволяет решать судоку очень быстро, без предположений и перебора с возвратом.

Исследователи комплексных сетей Золтан Торожкай и Мария Эркси-Раваз из Университета Нотр-Дама также смогли объяснить, почему некоторые загадки судоку более сложные, чем другие. Единственный недостаток в том, что для того, чтобы понять, что они предлагают, нужна степень доктора математики.

Вы можете решить эту головоломку? Она создана математиком Арто Инкалой, и, как утверждают, это самая сложная судоку в мире. Фото с сайта nature.com

Торожкай и Эркси-Раваз начали анализировать судоку как часть своего исследования теории оптимизации и вычислительной сложности. Они говорят, что большинство любителей судоку используют для решения этих задач подход «грубой силы», основанный на технике предположения. Таким образом, любители судоку вооружаются карандашом и пробуют все возможные комбинации чисел, пока не будет найден правильный ответ. Этот метод неизбежно приведет к успеху, но он трудоемок и занимает много времени.

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

Исследователи использовали «детерминированный аналоговый решатель», чтобы заполнить эту судоку. Фото с сайта nature.com

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

Они создали шкалу от 1 до 4, где 1 – «легко», 2 – «средняя степень сложности», 3 – «сложно», 4 – «очень сложно». Для решения головоломки с рейтингом 2 требуется в среднем в 10 раз больше времени, чем для задачки с рейтингом 1. Согласно этой системе, самая сложная загадка из известных до сих пор имеет рейтинг 3.6; более сложные задачи судоку пока неизвестны.

Теория начинается с картографии вероятностей для каждого отдельного квадрата. Фото с сайта nature.com

«Я не интересовался судоку, пока мы не начали работать над более общим классом выполнимости Булевых проблем, – говорит Торожкай. – Так как судоку – часть этого класса, латинский квадрат 9-го порядка оказался для нас хорошим полем для испытаний, так я с ними и познакомился. Меня и многих исследователей, изучающих такие проблемы, захватывает вопрос, как далеко мы, люди, способны зайти в решении судоку, детерминировано, без перебора, который является выбором наугад, и, если догадка не верна, нужно вернуться на шаг или на несколько шагов назад и начать сначала. Наша аналоговая модель решения детерминирована: в динамике нет никакого случайного выбора или возвращения».

Теория хаоса: степень сложности загадок показывается здесь как хаотическая динамика. Фото с сайта nature.com

Торожкай и Эркси-Раваз полагают, что их аналоговый алгоритм потенциально подходит для применения к решению большого количества разнообразных задач и проблем в промышленности, информатике и вычислительной биологии.

Опыт исследования также сделал Торожкая большим любителем судоку.

«У моей жены и у меня есть несколько приложений судоку на наших iPhone, и мы, должно быть, сыграли уже тысячи раз, соревнуясь за меньшее время на каждом уровне, – говорит он. – Она часто интуитивно видит комбинации паттернов, которых я не замечаю. Я должен их выводить. Для меня становится невозможным решить многие головоломки, которые наша шкала категоризирует как трудные или очень трудные, без того, чтобы записывать вероятности карандашом».

Методология Торожкая и Эркси-Раваз была впервые опубликована в журнале Nature Physics, а затем – в журнале Nature Scientific Reports.

www.km.ru

Чем интересна головоломка судоку?

Судоку ошибочно называют «японской головоломкой» или «магическим квадратом». Хотя, на самом деле, изобретение судоку не имеет никакого отношения ни к магии, ни к Японии. Основу данной головоломки — игру «Латинский квадрат» — придумал Леонард Эйлер. Этот знаменитый математик родился в Швейцарии, но трудился многие годы в Петербургской академии на благо российской науки.

После, спустя почти два столетия, к «латинским квадратам» приложил руку Ховард Гарнс, американский архитектор, который подрабатывал, придумывая головоломки для газет. В 1979 году он модернизировал игру Эйлера и опубликовал в американском журнале головоломок и кроссвордов.

Хоть первое появление судоку и не вызвало фурора, чуть позже этот числовой ребус оценили японцы. И даже дали ему своё название, которое дословно переводится как «число, стоящее отдельно». Именно японцы и посодействовали судоку в развитии её популярности. Фото: Источник

Основа поиска решения

Судоку, на первый взгляд, чрезвычайно простой и понятный ребус. Для его решения не требуются определенные знания или словарный запас. Основа головоломки — квадрат, разделенный на 9 меньших квадратов (3 на 3), каждый из которых также разделен на 9 ячеек — по 3 в строке и столбце. То есть основное поле судоку представлено 81 ячейкой. Их необходимо заполнить цифрами от 1 до 9 так, чтобы ни в строке, ни в столбике, ни в отдельных 9-ти квадратах они не повторялись.

При этом в каждом судоку изначально проставлены некоторые цифры-подсказки. Их порядок, месторасположение предопределяет решение ребуса. Чем больше подсказок — тем легче уровень судоку. Максимально сложные судоку (в классическом варианте) могут иметь всего 17−16 подсказок.

Чтобы решить судоку, можно использовать многочисленные правила и стратегии, выведенные почитателями этой головоломки. Например, наиболее очевидное из них: просматривать изначально наиболее заполненные строки и столбцы. Или же полагаться исключительно на собственную логику и память. Фото: Источник

Разные вариации судоку

Эта головоломка со временем стала настолько популярна, что её любителям захотелось разнообразия. Так появились разные вариации данного ребуса:

  1. Судоку нестандартных размеров (от 4×4 до 25×25). Уменьшенные головоломки создатели рекомендуют для детей как отличное развивающее занятие.
  2. Судоку-диагонали — здесь заданы диагонали больших квадратов, на которых цифры также не должны повторяться.
  3. Судоку-суммы, где выделены (помимо основных) разные блоки. В каждом из них обозначается сумма тех цифр, которые должны в него входить.
  4. Судоку с другими заданными условиями, например, «Чётное-нечётное». В таких головоломках выделяются ячейки, где должны быть только четные/нечетные цифры.
  5. Сцепленные судоку большого формата с общими блоками.
Фото: Источник

Свидетельство популярности

Кроме этого, о большой популярности судоку свидетельствует выпуск разнообразных настольных игр судоку, компьютерных, мобильных приложений и т. д. По решению этой головоломки даже проводят международные соревнования, устанавливают рекорды Книги Гиннесса.

А ещё многие математики, ученые «ломают голову» над судоку. К примеру, подсчитывают, сколько есть вариантов расстановки, комбинаций цифр для стандартного размера судоку 9×9 (23-значное число!). Или устанавливают, сколько, как минимум, должно быть подсказок, чтобы головоломка имела одно единственно правильное решение. Фото: Источник

Польза разгадывания судоку

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

Решение судоку развивает внимание, стратегическое мышление и многое другое. И самое главное, каждая разгаданная собственными усилиями головоломка — это маленькая победа, и она делает человека счастливее. Ради этого стоит уделить время судоку! Фото: Источник

Что еще почитать по теме?

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

shkolazhizni.ru

История судоку. Как создавалась и развивалась известная головоломка

Судо́ку (яп. 数独 су:доку, произношение (инф.) ) — головоломка с числами. Иногда судоку называют магическим квадратом, что в общем-то неверно, так как судоку является латинским квадратом 9-го порядка. Судоку активно публикуют газеты и журналы разных стран мира, сборники судоку издаются большими тиражами. Решение судоку — популярный вид досуга.

Правила

Игровое поле представляет собой квадрат размером 9×9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом, всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9), называемые подсказками. От игрока требуется заполнить свободные клетки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась бы только один раз.

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

Правильно составленная головоломка имеет только одно решение. Тем не менее, на некоторых сайтах в интернете под видом усложнённых головоломок пользователю предлагаются варианты судоку с несколькими вариантами решения, а также с ветвлениями самого хода решения.

Происхождение

В XVIII веке Леонард Эйлер изобрёл игру «Carré latin» («Латинский квадрат»). На основе этой игры в 70-х годах прошлого века в Северной Америке были придуманы специальные числовые головоломки. Так, в США судоку появилась впервые в 1979 году в журнале «Dell Puzzle Magazine». Тогда она называлась «Number Place». Настоящую популярность судоку завоевала в 1980—1990-х годах, когда японский журнал «Nikoli» начал регулярно публиковать на своих страницах эту головоломку (с 1986 года). Сегодня судоку — обязательный компонент многих газет. Среди них много изданий с многомиллионными тиражами, например, немецкая газета «Die Zeit»[, австрийский «Der Standard». Также публикует судоку российская газета «Труд».

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

Задача обобщённого судоку на поле {\displaystyle N^{2}\times N^{2}} [{\displaystyle N^{2}\times N^{2}}]  является NP-полной, так как к ней сводится задача о заполнении латинского квадрата.

Долгое время оставался открытым вопрос о минимальном количестве подсказок, необходимых для однозначного решения судоку. В частности, не было известно, существует ли однозначно решаемая судоку с 16 подсказками. Проект распределённых вычислений [email protected] на платформе BOINC занимался поиском такой судоку. В январе 2012 года появилось доказательство того, что однозначно решаемых судоку с 16 подсказками не существует.

Разновидности

Существует множество вариаций судоку:

  • Нерегулярное судоку (их ещё называют Судоку-пазл, Судоку-фигуры, Области). В этой головоломке вместо стандартных областей 3x3 используются области произвольной формы. Цифры не должны повторяться в каждой такой области.
  • Судоку разных размеров. Встречаются судоку размером от 4x4 (такие уменьшенные головоломки называют «шидоку» (Shidoku) от японского shi — четыре) до 25x25. Наиболее распространены судоку небольших размеров для детей.
  • Судоку с дополнительными областями. В этих задачах помимо стандартных областей (вертикалей, горизонталей и блоков) задаются дополнительные области, в которых цифры не могут повторяться. Наиболее распространены диагональные судоку.
  • Судоку с дополнительными условиями. В таких задачах помимо стандартного условия неповторяемости цифр задаются ещё дополнительные условия на значения. Например:
  • Судоку «Суммы» и множество её вариаций («Судоку-Произведения», «Судоку-Арифметика», «Квадросудоку», «Суммы-сбоку», «Суммы по диагонали» и т. п.), где всё поле делится на блоки, для которых сообщается сумма (произведение, разность и т. п.) всех входящих в него цифр.
  • Судоку «Чёт-нечёт». В них некоторые клетки изначально выделены цветом, в этих клетках находятся или только чётные, или только нечётные цифры.
  • Судоку «Больше-меньше». Для некоторых соседних клеток указан знак, показывающий в какой из клеток цифра больше.
  • Судоку «Точки», где между соседними клетками выводится точка белого или чёрного цвета, когда соседние цифры отличаются на 1 или в два раза.
  • Судоку «Перегородки» («Судоку-Соседи»), где отмечены все места с цифрами в соседних клетках отличающихся на 1.
  • Судоку другой формы. В головоломке используется не квадратная сетка, а треугольная, шестиугольная или более хитроумной формы.
  • Сцепленные судоку. «Судоку-Самурай» («Судоку-Комбо», «Судоку-Конструкции», «Тудоку» и др.), в которых несколько отдельных судоку имеют общие блоки и решаются взаимозависимо.

Настольная игра судоку

Существуют также настольные варианты игры. Подобные игры были изданы по всему миру различными издателями и разработчиками (к примеру, известный разработчик настольных игр Reiner Knizia издал свой вариант этой логической игры). В России можно встретить настольные судоку от фирмы Астрель и польской компании Trefi.

Компьютерные игры

Для персональных компьютеров существует достаточно много вариантов данной игры, выпускаемых различными компаниями-разработчиками для разных платформ, например,

Sudoku (из набора игр GNOME Games) или KSudoku (из набора игр KDE Games) — для Linux-платформ, Microsoft Sudoku (доступная для ОС Windows 8.1 или Windows 10 в Windows Store) — для Windows-платформ.

Версии для мобильных телефонов

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

С появлением смартфонов игра заняла достойное место среди самых популярных. С выходом на рынок устройств на базе Android и iOS, количество поклонников игры резко возросло.

По материалам https://ru.wikipedia.org/

biggestgame.ru


Смотрите также

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>