Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Легкая головоломка Какуро
Решение вышеуказанной головоломки

Какуро или Kakkuro или Kakoro ( японский :カックロ) является своего рода логической головоломки , который часто называют математической транслитерации в кроссворде . Головоломки Какуро регулярно появляются во многих публикациях по математике и логике по всему миру. В 1966 году [1] канадец Джейкоб Э. Функ, сотрудник Dell Magazines , придумал оригинальное английское название Cross Sums [2] , также использовались другие названия, такие как Cross Addition , но японское название Kakuro, сокращение от Японский касан куросу(加 算 ク ロ ス, «сложение креста»), похоже, получил всеобщее признание, и теперь в большинстве публикаций загадки называются именно так. Популярность Какуро в Японии огромна, уступая только Судоку среди знаменитых предложений Николи по логической головоломке. [2]

В канонической головоломке Какуро используется сетка из заполненных и заштрихованных ячеек, «черных» и «белых» соответственно. Пазлы обычно имеют размер 16 × 16, хотя эти размеры могут сильно различаться. За исключением верхней строки и крайнего левого столбца, которые полностью черные, сетка делится на «записи» - линии белых ячеек - черными ячейками. Черные ячейки содержат диагональную косую черту от верхнего левого угла до нижнего правого и числа в одной или обеих половинах, так что каждая горизонтальная запись имеет номер в черной половине ячейки непосредственно слева от нее, а каждая вертикальная запись имеет номер в черная полуклетка непосредственно над ней. Эти числа, заимствованные из кроссвордов, обычно называются «подсказками».

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

По крайней мере, один издатель [3] включает ограничение, согласно которому данная комбинация чисел может использоваться только один раз в каждой сетке, но по-прежнему продает головоломки как простые Какуро.

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

При обсуждении головоломок и тактик Какуро типичное сокращение для обозначения записи - «(подсказка цифрами) -в- (количество ячеек в записи, прописано)», например «16-в-двух» и «25». -в-пяти ». Исключением является то, что иначе назвали бы «45 из девяти» - используется просто «45», поскольку математически подразумевается «-in-девять» (девять ячеек - это самая длинная возможная запись, и поскольку они не могут дублировать цифра он должен состоять из всех цифр от 1 до 9 один раз). Любопытно, что и «43 из восьми», и «44 из восьми» по-прежнему часто называют таковыми, несмотря на то, что суффикс «-in-8» подразумевается одинаково.

Методы решения [ править ]

Комбинаторные техники [ править ]

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

Записи с достаточно большими или маленькими подсказками для их длины будут иметь меньшее количество возможных комбинаций для рассмотрения, и, сравнивая их с записями, которые их пересекают, можно получить правильную перестановку или ее часть. Самый простой пример - это когда 3-в-двух пересекает 4-в-два: 3-в-двух должно состоять из «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] См. Также Yato and Seta, 2004. [7]

В головоломках Какуро есть два вида математической симметрии: минимальные и максимальные ограничения двойственны, так же как и пропущенные, и требуемые значения.

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

Популярность [ править ]

Головоломки Какуро появляются почти в 100 японских журналах и газетах. Какуро оставался самой популярной логической головоломкой в ​​японской печатной прессе до 1992 года, когда первое место заняла судоку. [8] В Великобритании они впервые появились в The Guardian, а затем в The Telegraph и Daily Mail . [9]

Варианты [ править ]

Относительно распространенным вариантом Какуро является перекрестное произведение (или перекрестное умножение ), где подсказки являются произведением цифр в записях, а не суммой. Журналы Dell выпускали такие головоломки, но также разрешали повторение цифр, кроме 1, из-за ограничений по количеству цифр в каждом продукте в головоломке. Головоломки от Games Magazines больше похожи на кроссворды, позволяющие реализовать правило неповторения цифр.

Другой вариант - это другой диапазон значений, которые вставляются в ячейки, например от 1 до 12, вместо стандартных от 1 до 9.

Подлинной комбинацией судоку и какуро является так называемая «кросс-сумма судоку», в которой подсказки даются в виде перекрестных сумм на стандартной сетке судоку 9 x 9. Соответствующий вариант - это так называемый «Загадочный Какуро», где подсказки даются в алфавитном порядке, а каждое число представляет собой цифру от 1 до 9.

Последняя головоломка отборочного турнира Соединенных Штатов к чемпионату мира по головоломкам 2004 года называется Cross Number Sums Place : это кросс-сумма, где каждая строка и столбец сетки (кроме верхней строки и крайнего левого столбца, как обычно) содержат ровно девять белых ячеек. , ни один из которых даже через несколько записей, не разрешается использовать ту же цифру в два раза, как номер Место ( Sudoku ); кроме того, маленькие кружочки печатаются на границах между некоторыми белыми клетками; числовые соседние цифры должны располагаться по обеим сторонам этих кругов и не могут казаться смежными перпендикулярно, если они не расположены по обе стороны круга.

См. Также [ править ]

  • Убийственная судоку , разновидность судоку, в которой используются похожие техники.

Ссылки [ править ]

  1. ^ Тиммерман, Чарльз (2006). Книга испытаний Everything Kakuro . Адамс Медиа. п. ix. ISBN 9781598690576. Проверено 18 ноября 2018 года .
  2. ^ a b "История Какуро" . Проверено 18 ноября 2018 года .
  3. ^ "Судоку от Denksport" . Keesing Group BV . Проверено 18 ноября 2018 года .
  4. ^ "Какуро правила" . Проверено 18 ноября 2018 года .
  5. ↑ Бертье, Дени (5 апреля 2013 г.). «Удовлетворение ограничений на основе шаблонов и логические головоломки». arXiv : 1304.1628 [ cs.AI ].
  6. ↑ Такахиро, Сета (5 февраля 2002 г.). «Сложности головоломок, кросс-сумма и другие задачи их решения (ASP)» (PDF) . Проверено 18 ноября 2018 года .
  7. ^ Йато, Такаюки; Сета, Такахиро (2004). «Сложность и полнота поиска другого решения и его применение к головоломкам» (PDF) . Проверено 18 ноября 2018 года . Cite journal requires |journal= (help)
  8. ^ "Что такое Какуро" . Проверено 18 ноября 2018 года .
  9. ^ «История Какуро» . Проверено 18 ноября 2018 года .

Внешние ссылки [ править ]

  • The New Grid on the Block : введение газеты The Guardian в Какуро
  • Отчет IAENG о Какуро
  • Решайте головоломки Какуро онлайн