stringtranslate.com

Судоку

Судоку ( / s uː ˈ d oʊ k uː , - ˈ d ɒ k -, s ə -/ ; японский :数独, романизированный :  sūdoku , букв.  «цифра-одиночка»; первоначально называлась Number Place ) [1] — логическая , [2] [3] комбинаторная [4] головоломка на размещение чисел . В классической судоку цель состоит в том, чтобы заполнить сетку 9 × 9 цифрами так, чтобы каждый столбец, каждая строка и каждая из девяти подсеток 3 × 3, составляющих сетку (также называемых «ящиками», «блоками» или «регионами»), содержали все цифры от 1 до 9. Установщик головоломок предоставляет частично заполненную сетку, которая для хорошо поставленной головоломки имеет единственное решение.

Французские газеты публиковали вариации головоломок Судоку в 19 веке, а сама головоломка появилась в книгах-головоломках с 1979 года под названием Number Place. [5] Однако современная Судоку начала приобретать широкую популярность только в 1986 году, когда она была опубликована японской компанией-производителем головоломок Nikoli под названием Sudoku, что означает «одно число». [6] Впервые она появилась в американской газете, а затем в The Times (Лондон) в 2004 году благодаря усилиям Уэйна Гулда , который разработал компьютерную программу для быстрого создания уникальных головоломок.

История

Из газеты La France от 6 июля 1895 года: В инструкции к головоломке говорилось: «Используйте цифры от 1 до 9 по девять раз, чтобы заполнить сетку таким образом, чтобы горизонтальная, вертикальная и две главные диагональные линии в сумме давали одинаковую сумму».

Предшественники

Числовые головоломки появились в газетах в конце 19 века, когда французские составители головоломок начали экспериментировать с удалением чисел из магических квадратов . Le Siècle , парижская ежедневная газета, опубликовала частично завершенный магический квадрат 9×9 с подквадратами 3×3 19 ноября 1892 года. [7] Это не было судоку, поскольку оно содержало двузначные числа и требовало арифметики, а не логики для решения, но оно имело общие ключевые характеристики: каждая строка, столбец и подквадрат в сумме давали одно и то же число.

6 июля 1895 года конкурент Le Siècle , La France , усовершенствовал головоломку так, что она стала почти современным судоку, и назвал ее carré magique diabolique («дьявольский магический квадрат»). Она упростила головоломку с магическим квадратом 9×9 так, что каждая строка, столбец и разорванные диагонали содержали только числа 1–9, но не отмечали подквадраты. Хотя они не были отмечены, каждый подквадрат 3×3 действительно содержал числа 1–9, и дополнительное ограничение на разорванные диагонали приводило только к одному решению. [8]

Эти еженедельные головоломки были особенностью французских газет, таких как L'Écho de Paris , в течение примерно десятилетия, но исчезли примерно во время Первой мировой войны . [9]

Современное судоку

Современная судоку, скорее всего, была разработана анонимно Говардом Гарнсом , 74-летним архитектором на пенсии и внештатным конструктором головоломок из Коннерсвилля, штат Индиана , и впервые опубликована в 1979 году издательством Dell Magazines под названием Number Place (самый ранний из известных примеров современной судоку). [1] Имя Гарнса всегда присутствовало в списке авторов выпусков Dell Pencil Puzzles и Word Games , включавших Number Place, и всегда отсутствовало в выпусках, в которые его не входил. [10] Он умер в 1989 году, так и не получив возможности увидеть свое творение как всемирное явление. [10] Неясно, был ли Гарнс знаком с какой-либо из перечисленных выше французских газет.

Головоломка была представлена ​​в Японии Маки Кадзи (鍜治 真起, Kaji Maki ) , президентом компании-производителя головоломок Nikoli, в газете Monthly Nikolist в апреле 1984 года [10] как Sūji wa dokushin ni kagiru (数字は独身に限る) , что можно перевести как «цифры должны быть одинарными» или как «цифры ограничены одним появлением» (в японском языке dokushin означает «неженатый человек»). Позднее название было сокращено до Sudoku (数独), в результате чего для формирования более короткой версии использовались только первые кандзи сложных слов. [10] «Sudoku» является зарегистрированной торговой маркой в ​​Японии [11] , и головоломка обычно называется Number Place (ナンバープレース, Nanbāpurēsu ) или, более неформально, сокращением двух слов, Num(ber) Pla(ce) (ナンプレ, Nanpure ) . В 1986 году Николи представил два нововведения: количество заданий было ограничено не более чем 32, и головоломки стали «симметричными» (то есть заданные были распределены в ячейках с вращательной симметрией ). Теперь она публикуется в основных японских периодических изданиях, таких как Asahi Shimbun .

Распространение за пределами Японии

В 1997 году судья из Гонконга Уэйн Гулд увидел частично решенную головоломку в японском книжном магазине. За шесть лет он разработал компьютерную программу для быстрого создания уникальных головоломок. [5] Зная, что британские газеты имеют долгую историю публикации кроссвордов и других головоломок, он продвинул Sudoku в The Times в Великобритании, которая запустила его 12 ноября 2004 года (назвав его Su Doku). Первое письмо в The Times относительно Su Doku было опубликовано на следующий день, 13 ноября, от Яна Пейна из Брентфорда , в котором он жаловался, что из-за головоломки он пропустил свою остановку в метро . [12] Головоломки судоку быстро распространились в других газетах как постоянная статья. [5] [13]

Быстрый рост судоку в Великобритании от относительной безвестности до главной страницы национальных газет вызвал комментарии в СМИ и пародию (например, когда раздел G2 газеты The Guardian рекламировал себя как первое газетное приложение с сеткой судоку на каждой странице). [14] Осознавая различную психологическую привлекательность простых и сложных головоломок, The Times представила обе, бок о бок, 20 июня 2005 года. С июля 2005 года Channel 4 включил ежедневную игру судоку в свой телетекстовый сервис. 2 августа в программе BBC Radio Times была показана еженедельная игра Super Sudoku с сеткой 16×16.

В Соединенных Штатах первой газетой, опубликовавшей головоломку судоку Уэйна Гулда, была The Conway Daily Sun (Нью-Гэмпшир) в 2004 году. [15]

Первое в мире шоу судоку в прямом эфире, состоявшееся 1 июля 2005 года на канале Sky One

Первое в мире шоу судоку в прямом эфире, Sudoku Live , было конкурсом головоломок, впервые транслировавшимся 1 июля 2005 года на Sky One . Его вела Кэрол Вордерман . Девять команд по девять игроков (с одной знаменитостью в каждой команде), представляющих географические регионы, соревновались в решении головоломки. У каждого игрока было ручное устройство для ввода чисел, соответствующих ответам для четырех ячеек. Фил Коллин из Уинчелси, Англия , стал победителем главного приза серии, забрав домой более 23 000 фунтов стерлингов за серию игр. Зрители дома участвовали в отдельном интерактивном конкурсе, в котором победила Ханна Уити из Чешира .

Позже в 2005 году BBC запустила SUDO-Q , игровое шоу , которое сочетало судоку с общими знаниями. Однако в нем использовались только головоломки 4×4 и 6×6. Было выпущено четыре сезона, прежде чем шоу закончилось в 2007 году.

В 2006 году сайт Sudoku опубликовал песню-посвящение Sudoku автора песен Питера Леви, [16] но ему пришлось быстро удалить файл MP3 из-за большого трафика. Посольство Японии также номинировало песню на премию, а Леви вел переговоры с Sony в Японии о выпуске песни в качестве сингла. [17]

Программное обеспечение Sudoku очень популярно на ПК, веб-сайтах и ​​мобильных телефонах. Оно поставляется со многими дистрибутивами Linux . Программное обеспечение также было выпущено на игровых консолях, таких как Nintendo DS , PlayStation Portable , Game Boy Advance , Xbox Live Arcade , электронной книге Nook , планшете Kindle Fire, нескольких моделях iPod и iPhone . На многих телефонах Nokia также была Sudoku. Фактически, всего через две недели после того, как Apple Inc. дебютировала в онлайн- магазине App Store в своем iTunes Store 11 июля 2008 года, в нем уже было около 30 различных игр Sudoku, созданных различными разработчиками программного обеспечения специально для iPhone и iPod Touch. Одна из самых популярных видеоигр с Sudoku — Brain Age: Train Your Brain in Minutes a Day!. Критически и коммерчески хорошо принятая, она получила особую похвалу за свою реализацию Sudoku [18] [19] [20] и была продана тиражом более 8 миллионов копий по всему миру. [21] Благодаря своей популярности Nintendo выпустила вторую игру Brain Age под названием Brain Age 2 , в которой было более 100 новых головоломок судоку и других заданий.

В июне 2008 года австралийский суд присяжных по делу о наркотиках, стоимость которого превысила 1 миллион австралийских долларов , был прерван, когда выяснилось, что четверо или пятеро из двенадцати присяжных играли в судоку вместо того, чтобы слушать доказательства. [22]

Варианты

Вариации размеров сетки или форм областей

Хотя сетка 9×9 с областями 3×3 является наиболее распространенной, существует множество других вариаций. Примерами головоломок могут быть сетки 4×4 с областями 2×2; сетки 5×5 с областями пентамино были опубликованы под названием Logi-5; на чемпионате мира по головоломкам была представлена ​​сетка 6×6 с областями 2×3 и сетка 7×7 с шестью областями гептамино и непересекающейся областью. Возможны также более крупные сетки или различные нерегулярные формы (под разными названиями, такими как Suguru , Tectonic , Jigsaw Sudoku и т. д.). The Times предлагает сетку 12×12 «Dodeka Sudoku» с 12 областями из квадратов 4×3. Журнал Dell Magazines регулярно публикует головоломки 16×16 «Number Place Challenger» (используя числа 1–16 или буквы AP). Николи предлагает 25×25 "Sudoku the Giant" бегемотов. Головоломка с сеткой 100×100, названная Sudoku-zilla, была опубликована в 2010 году. [23]

Мини-судоку

Под названием «Mini Sudoku» вариант 6×6 с областями 3×2 появляется в американской газете USA Today и в других местах. Объект тот же, что и у стандартного судоку, но головоломка использует только числа от 1 до 6. Похожая форма, для юных решателей головоломок, называемая «The Junior Sudoku», появилась в некоторых газетах, например, в некоторых выпусках The Daily Mail .

Введение дополнительных ограничений

Другой распространенный вариант — добавление ограничений на размещение чисел сверх обычных требований к строкам, столбцам и полям. Часто ограничение принимает форму дополнительного «измерения»; наиболее распространенным является требование, чтобы числа в главных диагоналях сетки также были уникальными. Вышеупомянутые головоломки «Number Place Challenger» — все это головоломки этого варианта, как и головоломки Sudoku X в The Daily Mail , в которых используются сетки 6×6.

Убийственная судоку

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

Другие варианты

Головоломки, составленные из более чем двух сеток, также распространены. Пять сеток 9×9, которые перекрываются в угловых областях в форме квинконса, известны в Японии как Gattai 5 (пять объединенных) судоку. В The Times , The Age и The Sydney Morning Herald эта форма головоломки известна как Samurai Sudoku. Baltimore Sun и Toronto Star публикуют головоломку этого варианта (под названием High Five) в своем воскресном выпуске. Часто в перекрывающихся областях не размещаются никакие данные. Последовательные сетки, в отличие от перекрывающихся, также публикуются, при этом значения в определенных местах в сетках необходимо переносить в другие.

Пример Больше, чем Судоку

В настольную версию судоку можно играть со стандартной колодой из 81 карты Set (см. Игра Set ). Трехмерная головоломка судоку была опубликована в The Daily Telegraph в мае 2005 года. The Times также публикует трехмерную версию под названием Tredoku. Кроме того, версия судоку кубика Рубика называется Sudoku Cube .

Было разработано много других вариантов. [24] [25] [26] Некоторые из них представляют собой различные формы в расположении перекрывающихся сеток 9×9, таких как бабочка, мельница или цветок. [27] Другие изменяют логику решения сетки. Одна из них - «Больше, чем судоку». В ней дана сетка судоку 3×3 с 12 символами Больше, чем (>) или Меньше, чем (<) на общей линии двух соседних чисел. [10] Другой вариант логики решения - «Бездумный судоку», в котором девять сеток судоку 9×9 помещены в массив 3×3. Центральная ячейка в каждой сетке 3×3 всех девяти головоломок остается пустой и образует десятую головоломку судоку без какой-либо заполненной ячейки; отсюда и «бездумный». [27] Примеры и другие варианты можно найти в Глоссарии судоку .

Математика судоку

Судоку с 18 подсказками и двусторонней диагональной симметрией.

Этот раздел относится к классическому судоку, не принимая во внимание головоломки, гипер и другие варианты. Завершенная сетка судоку — это особый тип латинского квадрата с дополнительным свойством отсутствия повторяющихся значений в любом из девяти блоков (или ячеек 3×3). [28]

Известно, что общая задача решения головоломок судоку на сетках n 2 × n 2 из n × n блоков является NP-полной . [29] Многие алгоритмы решения судоку , такие как полный перебор с возвратом и танцующие связи , могут эффективно решать большинство головоломок 9×9, но комбинаторный взрыв происходит по мере увеличения n , создавая практические ограничения на свойства судоку, которые могут быть построены, проанализированы и решены по мере увеличения n . Головоломка судоку может быть выражена как задача раскраски графа . [30] Цель состоит в том, чтобы построить 9-раскраску конкретного графа, учитывая частичную 9-раскраску.

Наименьшее возможное количество подсказок для правильной головоломки судоку — 17. [31] Десятки тысяч различных головоломок судоку имеют всего 17 подсказок. [32]

Число классических сеток решений судоку 9×9 составляет 6 670 903 752 021 072 936 960, или около того6,67 × 10 21 . [33] Число существенно различных решений, если принять во внимание такие симметрии , как вращение, отражение, перестановка и перемаркировка, намного меньше, 5 472 730 538. [34]

В отличие от числа полных сеток судоку, число минимальных головоломок судоку 9×9 точно не известно. (Минимальная головоломка — это та, в которой ни одна подсказка не может быть удалена без потери уникальности решения.) Однако статистические методы в сочетании с генератором головоломок показывают, что существует около (с относительной погрешностью 0,065%) 3,10 × 10 37 минимальных головоломок и 2,55 × 10 25 не по существу эквивалентных минимальных головоломок. [35]

Соревнования

Соревнования по судоку в SM City Baliuag

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

Ссылки

  1. ^ ab Grossman, Lev (11 марта 2013 г.). "The Answer Men". Time . New York. Архивировано из оригинала 1 марта 2013 г. Получено 4 марта 2013 г.( требуется регистрация )
  2. ^ Арнольди, Бен. «Стратегии судоку». The Christian Science Monitor .
  3. ^ Шашек, Сара (22 марта 2006 г.). «Сюрпризная победа чемпиона по судоку». The Prague Post . Архивировано из оригинала 13 августа 2006 г. Получено 18 февраля 2009 г.
  4. ^ Gradwohl, Ronen; Naor, Moni; Pinkas, Benny; Rothblum, Guy N. (2007). «Криптографические и физические системы доказательства с нулевым разглашением для решений головоломок судоку». В Crescenzi, Pierluigi; Prencipe, Giuseppe; Pucci, Geppino (ред.). Fun with Algorithms, 4-я международная конференция, FUN 2007, Кастильончелло, Италия, 3-5 июня 2007 г., Труды . Заметки лекций по информатике. Том 4475. Springer. стр. 166–182. doi :10.1007/978-3-540-72914-3_16. ISBN 978-3-540-72913-6.
  5. ^ abc Smith, David (15 мая 2005 г.). "Так вы думали, что судоку пришло из Страны восходящего солнца..." The Observer . Получено 13 июня 2008 г. Головоломка , захватившая нацию, на самом деле началась в небольшом нью-йоркском журнале
  6. ^ Хейс, Брайан (2006). «Неженатые числа». American Scientist . 94 (1): 12–15. doi :10.1511/2006.57.3475.
  7. ^ Бойер, Кристиан (май 2006 г.). «Дополнение к статье «Французские истории судоку»» (PDF) . Pour la Science (на французском языке): 1–6. Архивировано из оригинала (PDF) 10 декабря 2006 г. Проверено 3 августа 2009 г.
  8. ^ Бойер, Кристиан (2007). «Французские предки судоку» (на французском). (персональная веб-страница). Архивировано из оригинала 10 октября 2007 г. Получено 3 августа 2009 г.
  9. ↑ Malvern, Jack (3 июня 2006 г.). «Les fiendish French beat us to Su Doku». Times Online . Лондон . Получено 16 сентября 2006 г.[ мертвая ссылка ]
  10. ^ abcde Pegg, Ed Jr. (15 сентября 2005 г.). "Математические игры Эда Пегга-младшего: вариации судоку". MAA Online . Математическая ассоциация Америки . Получено 3 октября 2006 г.
  11. ^ "Reg. No. 5056856". Японская торговая марка 5056856. Японская платформа информации о торговых марках . Получено 3 октября 2018 г.
  12. ↑ Пэйн, Иэн (13 ноября 2004 г.). «В глубокой задумчивости». The Times .
  13. ↑ Девлин, Кит (28–29 января 2012 г.). «Игра чисел (рецензия на книгу «Серьезное отношение к судоку» Джейсона Розенхауса и др.)». The Wall Street Journal . Weekend Edition. стр. C5.
  14. ^ "G2, дом взыскательного любителя судоку". The Guardian . Лондон. 13 мая 2005 г. Получено 16 сентября 2006 г.
  15. ^ "Исправление, добавленное к "Inside Japan's Puzzle Palace"". The New York Times . 21 марта 2007 г.
  16. ^ "Sudoku the song, by Peter Levy". Sudoku.org.uk . 17 августа 2006 г. Получено 5 октября 2008 г.
  17. ^ "Hit Song Has the Numbers". The Herald Sun. 17 августа 2006 г. Получено 5 октября 2008 г.
  18. ^ «Brain Age: Тренируйте свой мозг за несколько минут в день!». Gamerankings.com .
  19. ^ "Brain Age: ... Обзор". Gamespot.com .
  20. ^ Харрис, Крейг (18 апреля 2006 г.). «Возраст мозга: тренируйте мозг за несколько минут в день». IGN . Получено 8 февраля 2023 г. .
  21. ↑ Торсен, Тор (26 октября 2006 г.). «Nintendo получает прибыль в размере 456,6 млн долларов». GameSpot . Получено 29 марта 2013 г.
  22. ↑ Нокс, Малкольм (11 июня 2008 г.). «Игра окончена: присяжные, играющие в судоку, отменяют судебное разбирательство». The Sydney Morning Herald . Получено 11 июня 2008 г.
  23. ^ Эйзенхауэр, Уильям (2010). Судоку-зилла . CreateSpace. стр. 220. ISBN 978-1-4515-1049-2.
  24. ^ Снайдер, Томас; Хуан, Вэй-Хва (2009). Mutant Sudoku . Puzzlewright Press. ISBN 978-1-402765025.
  25. ^ Conceptis, Puzzles (2013). Удивительные варианты судоку . Puzzlewright. ISBN 978-1454906520. OCLC  700343731.
  26. ^ Мурали, А.В. (2014). Коллекция увлекательных игр и головоломок . CreateSpace Independent Publishing. ISBN 978-1500216429. OCLC  1152132274.
  27. ^ аб "Заленраецель". Янко.at.​
  28. ^ Keedwell, AD (ноябрь 2006 г.). «Два замечания о квадратах судоку». The Mathematical Gazette . 90 (519): 425–430. doi :10.1017/s0025557200180234. JSTOR  40378190.
  29. ^ Ято, Такаюки; Сета, Такахиро (2003). «Сложность и полнота поиска другого решения и его применение к головоломкам» (PDF) . IEICE TRANSACTIONS по основам электроники, связи и компьютерных наук . E86-A (5): 1052–1060. Архивировано из оригинала (PDF) 3 марта 2020 г.
  30. ^ Льюис, Р. (2015). Руководство по раскраске графов: алгоритмы и приложения . Springer. doi :10.1007/978-3-319-25730-3. ISBN 978-3-319-25728-0. OCLC  990730995. S2CID  26468973.
  31. ^ МакГвайр, Г.; Тугеманн, Б.; Чиварио, Г. (2014). «Судоку с 16 подсказками не существует: решение проблемы минимального количества подсказок в судоку». Экспериментальная математика . 23 (2): 190–217. arXiv : 1201.0749 . doi : 10.1080/10586458.2013.870056.
  32. ^ Ройл, Гордон . "Minimum Sudoku". Архивировано из оригинала 26 ноября 2006 г. Получено 28 февраля 2012 г.
  33. ^ Слоан, Н. Дж. А. (ред.). "Последовательность A107739 (Количество (завершенных) судоку (или судоку) размера n^2 X n^2)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
  34. ^ Слоан, Н. Дж. А. (ред.). "Последовательность A109741 (Число неэквивалентных (завершенных) n^2 X n^2 судоку (или судоку))". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
  35. ^ Бертье, Денис (4 декабря 2009 г.). «Непредвзятая статистика CSP – генератор с контролируемым смещением». В Elleithy, Khaled (ред.). Инновации в вычислительной технике и программной инженерии . Springer. стр. 165–70. Bibcode : 2010iics.book.....S. doi : 10.1007/978-90-481-9112-3. ISBN 978-90-481-9111-6. Получено 4 декабря 2009 г. .
  36. ^ "Название судоку для чешского бухгалтера". BBC News . 11 марта 2006 г. Получено 11 сентября 2006 г.
  37. ^ "World Sudoku Championship 2006 Instructions Booklet" (PDF) . BBC News . Архивировано (PDF) из оригинала 10 июня 2006 года . Получено 24 мая 2010 года .
  38. ^ "Отчет о 8-й Генеральной ассамблее Всемирной федерации головоломок". Всемирная федерация головоломок . 30 октября 2006 г. Архивировано из оригинала 26 сентября 2007 г. Получено 15 ноября 2006 г.
  39. ^ "Томас Снайдер выигрывает чемпионат мира по судоку". US Puzzle Team . 31 марта 2007 г. Получено 18 апреля 2008 г.
  40. ↑ Харви, Майкл (17 апреля 2008 г.). «Это головоломка, но солнце, море и пиво не могут конкурировать с судоку для британской команды». TimesOnline . Лондон. Архивировано из оригинала 20 июля 2008 г. Получено 18 апреля 2008 г.
  41. ↑ Malvern, Jack (27 апреля 2009 г.). «Битва Су Доку немного выходит за рамки». TimesOnline . Лондон. Архивировано из оригинала 15 июня 2011 г. Получено 27 апреля 2009 г.
  42. ^ "23-летний поляк снова стал чемпионом мира по судоку". PhillyInquirer . 2 мая 2009 г. Архивировано из оригинала 5 мая 2010 г. Получено 3 августа 2013 г.
  43. ^ "WSPC 2017 - Мастера логики Индия". wspc2017.logicmastersindia.com .
  44. ^ "Чемпионат мира по судоку | WPF". orldpuzzle.org .
  45. ^ "Томас Снайдер, чемпион мира по судоку". The Philadelphia Inquirer . 21 октября 2007 г. Получено 21 октября 2007 г.
  46. ↑ Шапиро, Ховард (25 октября 2009 г.). «Going for 2d, she wins 1st». The Philadelphia Inquirer . Архивировано из оригинала 2 ноября 2009 г. Получено 3 августа 2013 г.
  47. ↑ Timpane, John (27 октября 2009 г.). «Возможное мошенничество расследовано на Национальном чемпионате по судоку». The Philadelphia Inquirer . Архивировано из оригинала 1 ноября 2009 г. Получено 3 августа 2013 г.
  48. ^ "Победитель, занявший 3-е место, дисквалифицирован из-за скандала с судоку". The Philadelphia Inquirer . 24 ноября 2009 г. Архивировано из оригинала 27 ноября 2009 г. Получено 3 августа 2013 г.

Дальнейшее чтение

Внешние ссылки

На Викискладе есть медиафайлы по теме Судоку .