Судоку - Sudoku

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

Sudoku (数独, судок , цифры-сингл) ( / s ˙U d к ˙U , - d ɒ к -, s ə - / , первоначально названный Number Place ) является логика основы, комбинаторной номер-размещение головоломки . В классическом судоку цель состоит в том, чтобы заполнить сетку 9 × 9 цифрами так, чтобы каждый столбец, каждая строка и каждая из девяти подсеток 3 × 3, составляющих сетку (также называемых «квадратами», «блоками» или « регионы ") содержат все цифры от 1 до 9. Установщик головоломки предоставляет частично заполненную сетку, которая для хорошо поставленной головоломки имеет единственное решение.

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Варианты

Сетка головоломки судоку с множеством цветов, с девятью строками и девятью столбцами, которые пересекаются в квадратных точках.  Некоторые пробелы заполнены цифрой;  другие - это пустые места, которые нужно решить.
Нонамино или головоломки судоку, как показано в The Sunday Telegraph
Предыдущая головоломка, решаемая цифрами в пробелах.
И его решение (красные цифры)

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

Хотя сетка 9 × 9 с областями 3 × 3 является наиболее распространенной, существует множество других вариантов. Примеры головоломок могут представлять собой сетку 4 × 4 с областями 2 × 2; Сетки 5 × 5 с областями пентамино опубликованы под названием Logi-5; Чемпионат мира по пазлам показал сетку 6 × 6 с областями 2 × 3 и сетку 7 × 7 с шестью областями гептомино и непересекающейся областью. Также возможны более крупные сетки или различные неправильные формы (под разными названиями, такими как Сугуру , Тектоника , Головоломка Судоку и т. Д.). Times предлагает «Додека Судоку» с сеткой 12 × 12 с 12 областями квадратов 4 × 3. Журналы Dell регулярно публикуют головоломки «Number Place Challenger» размером 16 × 16 (с использованием цифр 1–16 или букв AP). Николи предлагает 25 × 25 гигантов Судоку. Пазл с сеткой 100 × 100, получивший название Sudoku-zilla, был опубликован в 2010 году.

Мини судоку

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

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

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

Убийца Судоку

Головоломка-убийца-судоку
И его решение

Вариант Killer Sudoku сочетает в себе элементы судоку и какуро .

Судоку по алфавиту

Загадка Wordoku
И его решение (красные символы)

Появились алфавитные вариации, иногда называемые Wordoku ; Никакой функциональной разницы в головоломке нет, если только буквы что-то не пишут. Некоторые варианты, например, в TV Guide , включают чтение слова по главной диагонали, строке или столбцу после решения; определение слова заранее можно рассматривать как помощь в решении. Wordoku может содержать слова, отличные от основного слова.

" Quadratum latinum " - это вариант судоку с римскими цифрами (I, II, III, IV, ..., IX), предложенный Hebdomada aenigmatum , ежемесячным журналом латинских головоломок и кроссвордов. Как и Wordoku, он не имеет функциональных отличий от обычного судоку, но добавляет визуальную сложность использования римских цифр.

Гипер Судоку / Виндоку

Сетка головоломки судоку с четырьмя синими квадрантами и девятью строками и девятью столбцами, которые пересекаются в квадратных пространствах.  Некоторые поля заполнены одним числом;  другие - это пустые места, которые нужно решить.
Головоломка гиперсудоку
Предыдущая головоломка, решаемая числами в пробелах.
И его решение

Hyper Sudoku или Windoku использует классическую сетку 9 × 9 с областями 3 × 3, но определяет четыре дополнительных внутренних области 3 × 3, в которых числа 1–9 должны появляться ровно один раз. Он был изобретен Питером Ритмистером и впервые опубликован им в голландской газете NRC Handelsblad в октябре 2005 года, а с апреля 2007 года ежедневно в The International New York Times (International Herald Tribune). Впервые это было названо «Hyper Sudoku» в «Любимых вариациях судоку» Уилла Шортца (февраль 2006 г.). Он также известен как Windoku, потому что с заштрихованными четырьмя внутренними областями сетки он напоминает окно с остеклением.

Судоку-близнец

В Twin Sudoku две обычные сетки делят коробку 3x3. Это один из многих возможных типов перекрывающихся сеток . Правила для каждой отдельной сетки такие же, как и в обычном судоку, но цифры в перекрывающейся части разделяются каждой половиной. В некоторых композициях ни одна отдельная сетка не может быть решена в одиночку - полное решение возможно только после того, как каждая отдельная сетка будет хотя бы частично решена.

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

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

Пример большего, чем судоку

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

Было разработано много других вариантов. Некоторые из них имеют разные формы в расположении перекрывающихся сеток 9 × 9, например, бабочка, ветряная мельница или цветок. Другие изменяют логику решения сетки. Один из них - «Больше чем судоку». В этом случае сетка судоку размером 3 × 3 состоит из 12 символов «Больше чем» (>) или «Меньше чем» (<) на общей линии двух соседних чисел. Другой вариант логики решения - «Бестолковая судоку», в которой девять сеток судоку 9 × 9 каждая размещены в массиве 3 × 3. Центральная ячейка в каждой сетке 3 × 3 всех девяти головоломок остается пустой и образует десятую головоломку Судоку без заполненных ячеек; следовательно, «невежественный». В новом варианте судоку сочетается с головоломкой со скользящей плиткой в ​​Sudoku Slide Extreme. В этом варианте все позиции заполнены. Плитки перемещаются в нужное положение для решения головоломки. Этот вариант содержит бонусы и режим кампании. Примеры и другие варианты можно найти в Глоссарии судоку .

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

Автоморфная Судоку с 18 ключей и двухсторонним диагональной симметрии

Этот раздел относится к классической судоку, не считая головоломки, гипер и других вариантов.

Завершенная сетка судоку - это особый тип латинского квадрата с дополнительным свойством отсутствия повторяющихся значений ни в одном из девяти блоков (или блоков размером 3 × 3 ячейки). Связь между двумя теориями известна после того, как было доказано, что формула первого порядка , в которой не упоминаются блоки, действительна для судоку тогда и только тогда, когда она действительна для латинских квадратов.

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

Наименьшее количество подсказок для правильного судоку - 17 (подтверждено в январе 2012 года и подтверждено в сентябре 2013 года). Было найдено более 49000 судоку с 17 подсказками, многие из которых были сделаны японскими энтузиастами. Были найдены судоку с 18 подсказками и вращательной симметрией, и есть по крайней мере одна судоку, которая имеет 18 подсказок, демонстрирует двустороннюю диагональную симметрию и является автоморфной . Максимальное количество подсказок, которое может быть предоставлено, но при этом не будет отображать уникальное решение, составляет четыре от полной сетки (77); если в ячейках, занимающих углы ортогонального прямоугольника, отсутствуют два экземпляра двух чисел в каждом, и ровно две из этих ячеек находятся в одной области, номера можно присвоить двумя способами. Поскольку это относится к латинским квадратам в целом, большинство вариантов судоку имеют одинаковый максимум.

Количество классических сеток для решения судоку 9 × 9 составляет 6 670 903 752 021 072 936 960 (последовательность A107739 в OEIS ) или около6,67 × 10 21 . Это примерно1,2 × 10 −6, умноженное на количество латинских квадратов 9 × 9. Также были перечислены различные другие размеры сетки - подробности см. В основной статье . Было показано, что количество существенно различных решений с учетом таких симметрий , как вращение, отражение, перестановка и перемаркировка, составляет всего 5 472 730 538 (последовательность A109741 в OEIS ).

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

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

Соревнования по судоку в SM City Baliuag
  • Первый чемпионат мира по судоку прошел в Лукке , Италия , с 10 по 12 марта 2006 года. Победителем стала Яна Тылова из Чехии . Конкурс включал в себя множество вариантов.
  • Второй чемпионат мира по судоку прошел в Праге, Чехия , с 28 марта по 1 апреля 2007 года. В личном первенстве чемпион США Томас Снайдер . Чемпионом команды стала Япония.
  • Третий чемпионат мира по судоку был проведен в Гоа, Индия , с 14 по 16 апреля 2008 года. Томас Снайдер снова стал абсолютным чемпионом в личном зачете, а также выиграл первый в истории классический трофей (часть соревнований, учитывающая только классические судоку). Чехия выиграла командное первенство.
  • Четвертый чемпионат мира по судоку прошел в городе Жилина , Словакия , с 24 по 27 апреля 2009 года. После того, как бывший чемпион США Томас Снайдер выиграл общую квалификацию, Ян Мрозовски из Польши вышел из плей-офф с 36 участниками и стал новым мировым судоку. Чемпион. Принимающая страна Словакия вышла в лидеры в отдельном соревновании трехкомпонентных команд.
  • Пятый чемпионат мира по судоку проходил в Филадельфии, штат Пенсильвания , с 29 апреля по 2 мая 2010 года. Ян Мрозовски из Польши успешно защитил свой титул чемпиона мира в личном зачете, а Германия выиграла отдельное командное соревнование. Головоломки были написаны Томасом Снайдером и Вей-Хва Хуангом , бывшими чемпионами США по судоку.
  • 12-й чемпионат мира по судоку (WSC) проходил в Бангалоре, Индия , с 15 по 22 октября 2017 года. Кота Мориниши из Японии выиграл индивидуальный чемпионат мира по игре в судоку, а Китай выиграл командное соревнование.
  • 13-й чемпионат мира по судоку прошел в Чехии.
  • В Соединенных Штатах национальный чемпионат по судоку в Филадельфии проводился трижды, каждый раз предлагая приз в размере 10 000 долларов победителю в продвинутом дивизионе и место в национальной сборной США по судоку, отправляющейся на чемпионаты мира. Победителями конкурса стали Томас Снайдер (2007 г.), Вей-Хва Хуанг (2008 г.) и Тэмми МакЛеод (2009 г.). В турнире 2009 года финалист, занявший третье место в высшем дивизионе, Евгений Варшавский, выступил на сцене довольно плохо после того, как на бумаге установил очень быстрое квалификационное время, что привлекло внимание организаторов и участников, включая бывшего чемпиона Томаса Снайдера, который попросил организаторов пересмотреть его. его результаты из-за подозрения в мошенничестве. После расследования и повторного тестирования Варшавского организаторы дисквалифицировали его и присудили Крису Нарриккатту третье место.

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

использованная литература

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

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