Судоку ( / s uː ˈ d oʊ k uː , - ˈ d ɒ k -, s ə -/ ; японский :数独, латинизированный : судоку , букв. «цифра-одиночная»; первоначально называлось числовое место ) [1] — это логическая , [2] [3] комбинаторная [4] головоломка с размещением чисел . В классическом судоку цель состоит в том, чтобы заполнить сетку 9 × 9 цифрами так, чтобы каждый столбец, каждая строка и каждая из девяти подсеток 3 × 3, составляющих сетку (также называемых «коробками», «блоками» или «блоками»). регионы") содержит все цифры от 1 до 9. Программа для создания головоломки предоставляет частично заполненную сетку, которая для правильно составленной головоломки имеет единственное решение.
В 19 веке французские газеты публиковали варианты головоломок судоку, а с 1979 года эта головоломка появляется в сборниках головоломок под названием Number Place. [5] Однако современное судоку начало приобретать широкую популярность только в 1986 году, когда оно было опубликовано японской компанией по производству головоломок Николи под названием «Судоку», что означает «одиночное число». [6] Впервые оно появилось в американской газете, а затем в The Times (Лондон) в 2004 году благодаря усилиям Уэйна Гулда , который разработал компьютерную программу для быстрого создания уникальных головоломок.
Числовые головоломки появились в газетах в конце 19 века, когда французские составители головоломок начали экспериментировать с удалением чисел из магических квадратов . Парижская ежедневная газета Le Siècle 19 ноября 1892 года опубликовала частично завершенный магический квадрат 9×9 с подквадратами 3×3 . [7] Это не было судоку, поскольку оно содержало двузначные числа и для решения требовало арифметики, а не логики. , но у него были общие ключевые характеристики: каждая строка, столбец и квадрат в сумме давали одно и то же число.
6 июля 1895 года конкурент Le Siècle , компания La France , усовершенствовала головоломку так, что она стала почти современным судоку, и назвала ее carré magiquediabolique («дьявольский магический квадрат»). Он упростил головоломку с магическим квадратом 9 × 9 так, что каждая строка, столбец и ломаная диагональ содержали только цифры 1–9, но не обозначали подквадраты. Хотя они не были помечены, каждый подквадрат 3×3 действительно содержал числа от 1 до 9, а дополнительное ограничение на ломаные диагонали приводило только к одному решению. [8]
Эти еженедельные головоломки были особенностью французских газет, таких как L'Echo de Paris, около десяти лет, но исчезли во время Первой мировой войны . [9]
Современное судоку, скорее всего, было разработано анонимно Говардом Гарнсом , 74-летним архитектором на пенсии и разработчиком головоломок из Коннерсвилля, штат Индиана , и впервые опубликовано в 1979 году журналом Dell Magazines под названием Number Place (самый ранний известный пример современного судоку). [1] Имя Гарнса всегда присутствовало в списке авторов выпусков Dell Pencil Puzzles and Word Games , которые включали Number Place, и всегда отсутствовало в выпусках, в которых этого не было. [10] Он умер в 1989 году, не успев увидеть свое творение как всемирное явление. [10] Неясно, был ли Гарнс знаком с какой-либо из перечисленных выше французских газет.
Головоломка была представлена в Японии Маки Кадзи (鍜治 真起, Кадзи Маки ) , президентом компании-головоломки Nikoli, в газете Monthly Nikolist в апреле 1984 года [10] как Судзи ва докушин ни кагиру (数字は独身に限る) , что можно перевести как «цифры должны быть одиночными» или как «цифры ограничены одним появлением» (по-японски докушин означает «неженатый человек»). Позже название было сокращено до Судоку (数独), в результате чего для формирования более короткой версии были взяты только первые кандзи составных слов. [10] «Судоку» является зарегистрированным товарным знаком в Японии [11] и головоломка обычно обозначается как Number Place (ナンバープレース, Nanbāpurēsu ) или, более неофициально, как сокращение двух слов, Num(ber) Pla(ce). ) (ナンプレ, Нанпур ) . В 1986 году Николи представил два нововведения: количество данных было ограничено до 32, а головоломки стали «симметричными» (то есть данные были распределены во вращательно-симметричных ячейках ). Сейчас он публикуется в основных японских периодических изданиях, таких как Асахи Симбун .
В 1997 году гонконгский судья Уэйн Гулд увидел в японском книжном магазине частично законченную головоломку. За шесть лет он разработал компьютерную программу для быстрого создания уникальных головоломок. [5] Зная, что британские газеты имеют долгую историю публикации кроссвордов и других головоломок, он продвигал судоку в газете The Times в Великобритании, которая запустила его 12 ноября 2004 года (назвав его Су Доку). Первое письмо в The Times относительно Су Доку было опубликовано на следующий день, 13 ноября, от Яна Пейна из Брентфорда , в котором он жаловался, что из-за головоломки он пропустил остановку на метро . [12] Головоломки судоку быстро распространились в других газетах как регулярная статья. [5] [13]
Быстрый рост судоку в Британии из относительной безвестности на первые полосы национальных газет вызвал комментарии в средствах массовой информации и пародии (например, когда раздел G2 The Guardian рекламировал себя как первое газетное приложение с сеткой судоку на каждой странице). ). [14] Признавая различную психологическую привлекательность простых и сложных головоломок, 20 июня 2005 года The Times представила обе эти задачи одновременно. С июля 2005 года Channel 4 включил ежедневную игру-судоку в свою службу телетекста . 2 августа в программе BBC Radio Times было показано еженедельное Суперсудоку с сеткой 16х16.
В Соединенных Штатах первой газетой, опубликовавшей в 2004 году головоломку-судоку Уэйна Гулда , была The Conway Daily Sun (Нью-Гэмпшир) .
Первое в мире судоку-шоу в прямом эфире, Sudoku Live , представляло собой соревнование по головоломкам, которое впервые транслировалось 1 июля 2005 года на канале Sky One . Его представила Кэрол Вордерман . Девять команд по девять игроков (по одной знаменитости в каждой команде), представляющих географические регионы, соревновались в решении головоломки. У каждого игрока было портативное устройство для ввода чисел, соответствующих ответам на четыре клетки. Фил Коллин из Уинчелси, Англия , стал обладателем главного приза серии, забрав домой более 23 000 фунтов стерлингов за серию игр. Домашняя публика участвовала в отдельном интерактивном конкурсе, который выиграла Ханна Уити из Чешира .
Позже в 2005 году BBC запустила SUDO-Q — игровое шоу , в котором судоку сочеталось с общими знаниями. Однако в нем использовались только головоломки 4×4 и 6×6. До окончания шоу в 2007 году было снято четыре сезона.
В 2006 году на веб-сайте судоку была опубликована песня-трибьют судоку автора песен Питера Леви, [16] но файл MP3 был быстро вынужден удалить из-за большого трафика. Британское и австралийское радио подхватили песню, которая будет представлена [ когда? ] в документальном фильме о судоку британского производства. Посольство Японии также номинировало песню на награду, а Леви вел переговоры с Sony в Японии о выпуске песни как сингла. [17]
Программное обеспечение для судоку очень популярно на ПК, веб-сайтах и мобильных телефонах. Он поставляется со многими дистрибутивами Linux . Программное обеспечение также было выпущено на игровых консолях, таких как Nintendo DS , PlayStation Portable , Game Boy Advance , Xbox Live Arcade , устройстве для чтения электронных книг Nook , планшете Kindle Fire, нескольких моделях iPod и iPhone . Многие телефоны Nokia также имели судоку. Фактически, всего через две недели после того, как Apple Inc. 11 июля 2008 года представила онлайн- магазин приложений App Store в своем iTunes Store , в нем уже было около 30 различных игр-судоку, созданных различными разработчиками программного обеспечения специально для iPhone и iPod Touch. Одна из самых популярных видеоигр с участием судоку — Brain Age: тренируйте свой мозг за минуты в день! . Будучи хорошо принят критиками и коммерчески, он получил особую похвалу за реализацию судоку [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 с шестью областями гептамино и непересекающейся областью. Также возможны более крупные сетки или различные неправильные формы (под различными названиями, такими как Сугуру , Тектоника , Головоломка Судоку и т. д.). The Times предлагает «Додека судоку» размером 12 × 12 с 12 областями по квадратам 4 × 3. Журналы Dell Magazines регулярно публикуют головоломки «Числовое место претендента» размером 16 × 16 (с использованием цифр 1–16 или букв AP). Николи предлагает гигантов «Судоку Гигант» размером 25 × 25. В 2010 году была опубликована головоломка размером 100×100 под названием «Судоку-зилла ».
Под названием «Мини-судоку» вариант 6×6 с областями 3×2 появляется в американской газете USA Today и других изданиях. Цель такая же, как и в стандартном судоку, но в головоломке используются только цифры от 1 до 6. Похожая форма для младших решающих головоломок, названная «Юниорское судоку», появилась в некоторых газетах, например в некоторых изданиях. Дейли Мейл .
Другой распространенный вариант — добавить ограничения на размещение чисел помимо обычных требований к строкам, столбцам и полям. Часто предел принимает форму дополнительного «измерения»; наиболее распространенным является требование, чтобы числа на главных диагоналях сетки также были уникальными. Все вышеупомянутые головоломки «Number Place Challenger» относятся к этому варианту, как и головоломки Sudoku X в The Daily Mail , в которых используются сетки 6×6.
Вариант « Убийца судоку» сочетает в себе элементы судоку и какуро . Убийственная головоломка-судоку состоит из «клеток», обычно изображаемых в виде прямоугольников, обведенных черточками или цветами. Сумма чисел в клетке записывается в левом верхнем углу клетки, числа в клетке повторяться не могут.
Также распространены головоломки, состоящие из более чем двух сеток. Пять сеток 9×9, которые перекрываются в угловых областях в форме квинконса, известны в Японии как Гаттай 5 (пять объединенных) судоку. В The Times , The Age и The Sydney Morning Herald эта форма головоломки известна как самурайское судоку. Газеты Baltimore Sun и Toronto Star публикуют головоломку этого варианта (под названием «Дай пять») в своем воскресном выпуске. Часто в перекрывающихся регионах не размещаются никакие данные. Также публикуются последовательные сетки, в отличие от перекрывающихся, при этом значения в определенных местах сетки необходимо передавать в другие.
В настольную версию судоку можно играть со стандартной колодой набора из 81 карты (см. игру «Сет» ). Трехмерная головоломка судоку была опубликована в The Daily Telegraph в мае 2005 года. The Times также публикует трехмерную версию под названием Tredoku. Кроме того, версия кубика Рубика для судоку называется «Кубик Судоку» .
Было разработано множество других вариантов. [24] [25] [26] Некоторые из них имеют разную форму в виде перекрывающихся сеток 9×9, например бабочка, ветряная мельница или цветок. [27] Другие меняют логику решения сетки. Одним из них является «Больше, чем судоку». При этом сетка судоку 3×3 представлена 12 символами «Больше (>)» или «Меньше (<)» на общей линии двух соседних чисел. [10] Другой вариант логики решения - «Бестолковое судоку», в котором каждая из девяти сеток судоку 9×9 помещена в массив 3×3. Центральная ячейка в каждой сетке 3 × 3 из всех девяти головоломок остается пустой и образует десятую головоломку судоку без заполнения какой-либо ячейки; следовательно, «невежественный». [27] Новый вариант сочетает в себе судоку и головоломку с раздвижными плитками в Sudoku Slide Extreme. В этом варианте все позиции заполнены. Плитки перемещаются в нужное положение для решения головоломки. Этот вариант содержит бонусы и режим кампании. [ нужна цитация ] Примеры и другие варианты можно найти в Глоссарии судоку .
В этом разделе речь идет о классическом судоку, за исключением головоломки, гипер- и других вариантов.
Заполненная сетка судоку представляет собой особый тип латинского квадрата с дополнительным свойством отсутствия повторяющихся значений ни в одном из девяти блоков (или блоков ячеек 3х3). Связь между двумя теориями известна после того, как было доказано, что формула первого порядка , в которой не упоминаются блоки, справедлива для судоку тогда и только тогда, когда она справедлива для латинских квадратов. [28]
Общая задача решения головоломок судоку на сетках n 2 × n 2 блоков n × n , как известно, NP-полна . [29] Многие компьютерные алгоритмы , такие как возврат и танцующие ссылки , могут эффективно решать большинство головоломок 9×9, но с увеличением n происходит комбинаторный взрыв , создавая ограничения для свойств судоку, которые можно строить, анализировать и решать по мере увеличения n . Головоломку судоку можно выразить как задачу раскраски графа . [30] Цель состоит в том, чтобы построить 9-раскраску конкретного графа, учитывая частичную 9-раскраску.
Наименьшее количество подсказок для правильного судоку — 17 (доказано в январе 2012 г. и подтверждено в сентябре 2013 г.). [31] [32] Всего было найдено 49 158 судоку с 17 подсказками, многие из которых созданы японскими энтузиастами. [33] [34] Были найдены судоку с 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. [35] Также были перечислены различные другие размеры сетки — подробности см. В основной статье . Было показано , что число существенно различных решений с учетом таких симметрий , как вращение, отражение, перестановка и перемаркировка, составляет всего 5 472 730 538 [36] (последовательность A109741 в OEIS ).
В отличие от количества полных сеток судоку, количество минимальных головоломок судоку 9×9 точно неизвестно. (Минимальная головоломка — это такая головоломка, в которой нельзя удалить ни одной подсказки без потери уникальности решения.) Однако статистические методы в сочетании с генератором головоломок [37] показывают, что около (с относительной ошибкой 0,065%) 3,10 × 10 37 минимальных головоломок. и существует 2,55 × 10 25 несущественно эквивалентных минимальных головоломок.
Загадка, захватившая нацию, на самом деле началась с небольшого нью-йоркского журнала.
Любое правило разрешения без блоков уже действительно в теории латинских квадратов, распространенной на кандидатов ». Более явно сформулировано во втором издании, стр. 86, как: «формула без блоков действительна для судоку тогда и только тогда. если это справедливо для латинских квадратов