Какуро
Какуро или Каккуро или Какоро ( японский : カックロ ) — это своего рода головоломка , которую часто называют математической транслитерацией кроссворда логическая . Головоломки Какуро регулярно появляются во многих публикациях по математическим и логическим головоломкам по всему миру. В 1966 году [1] Канадец Джейкоб Э. Фанк, сотрудник Dell Magazines , придумал оригинальное английское название Cross Sums. [2] и другие названия, такие как перекрестное сложение , также использовались, но японское имя Какуро, аббревиатура японского касан куросу (加算クロス, «сложение креста»), похоже, получило всеобщее признание, и теперь головоломки называются именно так. большинство публикаций. Популярность Какуро в Японии огромна, уступая только судоку среди . знаменитых логических головоломок Николи [2]
Каноническая головоломка Какуро разыгрывается в сетке из заполненных и заштрихованных ячеек, «черных» и «белых» соответственно. Пазлы обычно имеют размер 16×16, хотя эти размеры могут сильно различаться. За исключением верхней строки и крайнего левого столбца, которые полностью черные, сетка разделена на «записи» — строки белых ячеек — черными ячейками. Черные ячейки содержат диагональную черту от верхнего левого угла к нижнему правому и число в одной или обеих половинах, так что каждая горизонтальная запись имеет номер в полуячейке непосредственно слева, а каждая вертикальная запись имеет номер в полуячейка непосредственно над ним. Эти числа, заимствованные из терминологии кроссвордов, обычно называют «подсказками».
Цель головоломки — вставить цифру от 1 до 9 включительно в каждую белую клетку так, чтобы сумма чисел в каждой записи соответствовала подсказке, связанной с ней, и чтобы ни одна цифра не повторялась ни в одной записи. Именно отсутствие дублирования делает возможным создание головоломок Какуро с уникальными решениями. Как и судоку, решение головоломки Какуро включает в себя исследование комбинаций и перестановок . Существует неписаное правило создания головоломок Какуро, согласно которому каждая подсказка должна иметь как минимум два числа, которые складываются в нее, поскольку включение только одного числа математически тривиально при решении головоломок Какуро.
Хотя бы один издатель [3] включает ограничение, заключающееся в том, что данную комбинацию чисел можно использовать только один раз в каждой сетке, но при этом головоломки по-прежнему продаются как простые Какуро.
Некоторые издатели предпочитают печатать свои сетки Какуро точно так же, как сетки кроссвордов, без надписей в черных ячейках и вместо этого нумеруя записи, предоставляя отдельный список подсказок, аналогичный списку разгадок кроссвордов. (Это исключает полностью черные строки и столбцы.) Это чисто проблема изображения и не влияет ни на решение, ни на логику, необходимую для решения.
При обсуждении головоломок и тактики Какуро типичным сокращением для обозначения записи является «(подсказка, цифрами)-в-(количество ячеек в записи, прописано)», например «16-в-два» и «25». - через пять". Исключением является то, что иначе называлось бы «45-в-девяти» — используется просто «45», поскольку математически подразумевается «-в-девяти» (девять ячеек — это самая длинная возможная запись, и поскольку она не может дублировать цифра должна состоять из всех цифр от 1 до 9 один раз). Любопытно, что и «43-в-восьми», и «44-в-8» до сих пор часто называют так, несмотря на то, что суффикс «-в-восьми» одинаково подразумевается.
Методы решения
[ редактировать ]Комбинаторные методы
[ редактировать ]Хотя угадывание методом грубой силы возможно, более эффективным подходом является понимание различных комбинаторных форм, которые записи могут принимать для различных пар подсказок и длин записей. Пространство решения можно уменьшить, разрешив допустимые пересечения горизонтальных и вертикальных сумм или учитывая необходимые или отсутствующие значения.
Те записи, которые имеют достаточно большие или маленькие подсказки для своей длины, будут иметь меньше возможных комбинаций для рассмотрения, и, сравнивая их с записями, которые их пересекают, можно получить правильную перестановку — или ее часть. Самый простой пример: 3-в-два пересекает 4-в-два: 3-в-2 должно состоять из «1» и «2» в некотором порядке; 4-в-два (поскольку «2» не может быть продублировано) должно состоять из «1» и «3» в некотором порядке. Следовательно, их пересечение должно быть «1», единственной общей цифрой.
При решении более длинных сумм есть дополнительные способы найти подсказки для определения правильных цифр. Одним из таких методов было бы отметить, где несколько квадратов вместе имеют общие возможные значения, тем самым исключая возможность того, что другие квадраты в этой сумме могут иметь такие же значения. Например, если две подсказки 4 из 2 пересекаются с более длинной суммой, то 1 и 3 в решении должны находиться в этих двух квадратах, и эти цифры нельзя использовать где-либо еще в этой сумме. [4]
При решении сумм, которые имеют ограниченное количество наборов решений, это может привести к полезным подсказкам. Например, сумма 30 из семи имеет только два набора решений: {1,2,3,4,5,6,9} и {1,2,3,4,5,7,8}. Если один из квадратов в этой сумме может принимать только значения {8,9} (например, если ключом к пересечению является сумма 17 из двух), то это не только становится индикатором того, какой набор решений соответствует этому sum, он исключает возможность того, что любая другая цифра в сумме будет одним из этих двух значений, даже до определения того, какое из двух значений соответствует этому квадрату.
Другой полезный подход к решению более сложных головоломок — определить, в каком квадрате находится цифра, исключив другие места в сумме. Если все признаки пересечения суммы имеют множество возможных значений, но можно определить, что существует только один квадрат, который может иметь определенное значение, которое должна иметь рассматриваемая сумма, то любые другие возможные значения, которые допускает сумма пересечений, это пересечение должно быть изолированным значением. Например, сумма 36 из восьми должна содержать все цифры, кроме 9. Если только один из квадратов может принимать значение 2, то это должно быть ответом для этого квадрата.
Боксовая техника
[ редактировать ]«Техника ящика» также может быть применена в некоторых случаях, когда геометрия незаполненных белых клеток на любом этапе решения поддается этому: путем суммирования подсказок для серии горизонтальных записей (вычитая значения любых уже имеющихся цифр). добавленные к этим записям) и вычитая подсказки для в основном перекрывающихся серий вертикальных записей, разница может выявить значение частичной записи, часто одной ячейки. Этот метод работает, поскольку сложение является одновременно ассоциативным и коммутативным .
Обычной практикой является отмечать потенциальные значения ячеек в углах ячеек до тех пор, пока не будет доказано, что все, кроме одного, невозможно; для особенно сложных головоломок иногда решатели отмечают целые диапазоны значений ячеек в надежде в конечном итоге найти достаточные ограничения для этих диапазонов от пересекающихся записей, чтобы иметь возможность сузить диапазоны до отдельных значений. Из-за нехватки места некоторые решатели используют вместо цифр позиционную запись, где потенциальное числовое значение представляется отметкой в определенной части ячейки, что позволяет легко поместить несколько потенциальных значений в одну ячейку. Это также облегчает отличие потенциальных значений от значений решения.
Некоторые решатели также используют миллиметровую бумагу , чтобы пробовать различные комбинации цифр, прежде чем записывать их в сетку головоломки.
Как и в случае с судоку, с помощью вышеупомянутых методов можно решить только относительно простые головоломки Какуро. Более сложные требуют использования различных типов цепочек, таких же, как в судоку (см. Удовлетворение ограничений на основе шаблонов и логические головоломки). [5] ).
Математика Какуро
[ редактировать ]Математически головоломки Какуро могут быть представлены как задачи целочисленного программирования и являются NP-полными . [6] См. также Ято и Сета, 2004. [7]
В головоломках Какуро легко различить два вида математической симметрии: минимальные и максимальные ограничения двойственны, как и недостающие и необходимые значения.
Все комбинации сумм могут быть представлены с использованием растрового представления. Это представление полезно для определения недостающих и требуемых значений с помощью побитовых логических операций .
Популярность
[ редактировать ]Головоломки Какуро появляются почти в 100 японских журналах и газетах. Какуро оставалось самой популярной логической головоломкой в японской печатной прессе до 1992 года, когда судоку заняло первое место. [8] В Великобритании они впервые появились в The Guardian , а затем в The Telegraph и Daily Mail . [9]
См. также
[ редактировать ]- Убийственное судоку — вариант судоку, который решается с использованием аналогичных техник.
Ссылки
[ редактировать ]- ^ Тиммерман, Чарльз (2006). Книга «Все вызовы Какуро» . Адамс Медиа. п. ix. ISBN 9781598690576 . Проверено 18 ноября 2018 г.
- ↑ Перейти обратно: Перейти обратно: а б «История Какуро» . Проверено 18 ноября 2018 г.
- ^ «Судоку из Денкспорта» . Кизинг Групп Б.В. Проверено 18 ноября 2018 г.
- ^ «Какуро рулит» . Проверено 18 ноября 2018 г.
- ^ Бертье, Дени (5 апреля 2013 г.). «Удовлетворение ограничений на основе шаблонов и логические головоломки». arXiv : 1304.1628 [ cs.AI ].
- ^ Такахиро, Сета (5 февраля 2002 г.). «Сложности головоломок, перекрестная сумма и другие задачи их решения (ASP)» (PDF) . Проверено 18 ноября 2018 г.
- ^ Ято, Такаюки; Сета, Такахиро (2004). «Сложность и полнота поиска другого решения и его применение к головоломкам» (PDF) . Проверено 18 ноября 2018 г.
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ «Что такое Какуро» . Проверено 18 ноября 2018 г.
- ^ «История Какуро» . Проверено 18 ноября 2018 г.
Внешние ссылки
[ редактировать ]
- Новая сетка на блоке : The Guardian с Какуро знакомство газеты
- Отчет IAENG о Какуро
- Решайте головоломки Какуро онлайн
| Базы данных органов управления : Национальные |
|---|
