Какуро или Какуро или Какоро ( яп .カックロ) — это разновидность логической головоломки , которую часто называют математической транслитерацией кроссворда . Головоломки Какуро регулярно появляются во многих публикациях по математике и логике по всему миру. В 1966 году [1] канадец Джейкоб Э. Фанк, сотрудник Dell Magazines , придумал оригинальное английское название Cross Sums [2] и другие названия, такие как Cross Addition, также использовались, но японское название Какуро, сокращение от японского kasan kurosu (加算クロス, «крест сложения»), похоже, получило всеобщее признание, и головоломки, по-видимому, теперь называются именно так в большинстве публикаций. Популярность Какуро в Японии огромна, уступая только Судоку среди знаменитых логических головоломок Николи. [ 2]
Каноническая головоломка Какуро играется в сетке заполненных и заштрихованных ячеек, «черных» и «белых» соответственно. Головоломки обычно имеют размер 16×16, хотя эти размеры могут значительно различаться. За исключением верхней строки и самого левого столбца, которые полностью черные, сетка разделена на «записи» — линии белых ячеек — черными ячейками. Черные ячейки содержат диагональную косую черту от верхнего левого угла до нижнего правого и число в одной или обеих половинах, так что каждая горизонтальная запись имеет число в полуячейке непосредственно слева от нее, а каждая вертикальная запись имеет число в полуячейке непосредственно над ней. Эти числа, заимствуя терминологию кроссворда, обычно называются «подсказками».
Цель головоломки — вставить цифру от 1 до 9 включительно в каждую белую клетку так, чтобы сумма чисел в каждой записи соответствовала подсказке, связанной с ней, и чтобы ни одна цифра не дублировалась ни в одной записи. Именно это отсутствие дублирования делает возможным создание головоломок Какуро с уникальными решениями. Как и в судоку, решение головоломки Какуро включает исследование комбинаций и перестановок . Существует негласное правило для создания головоломок Какуро, что каждая подсказка должна иметь по крайней мере два числа, которые ее в сумме составляют, поскольку включение только одного числа математически тривиально при решении головоломок Какуро.
По крайней мере один издатель [3] включает ограничение, согласно которому заданная комбинация чисел может использоваться только один раз в каждой сетке, но по-прежнему продает головоломки как простые какуро.
Некоторые издатели предпочитают печатать свои сетки Какуро точно так же, как сетки кроссвордов, без маркировки черных ячеек, а вместо этого нумеруя записи, предоставляя отдельный список подсказок, похожий на список подсказок кроссворда. (Это исключает строку и столбец, которые полностью черные.) Это чисто вопрос имиджа и не влияет ни на решение, ни на логику, необходимую для решения.
При обсуждении головоломок и тактик Какуро типичным сокращением для ссылки на запись является "(подсказка, в цифрах)-в-(количество ячеек в записи, прописью)", например, "16-в-два" и "25-в-пять". Исключением является то, что иначе называлось бы "45-в-девяти" — используется просто "45", поскольку "-в-девяти" математически подразумевается (девять ячеек — самая длинная возможная запись, и поскольку она не может дублировать цифру, она должна состоять из всех цифр от 1 до 9 один раз). Любопытно, что и "43-в-восемь", и "44-в-восемь" по-прежнему часто называются так, несмотря на то, что суффикс "-в-восемь" в равной степени подразумевается.
Хотя догадка методом грубой силы возможна, более эффективным подходом является понимание различных комбинаторных форм, которые записи могут принимать для различных пар подсказок и длин записей. Пространство решений может быть уменьшено путем разрешения допустимых пересечений горизонтальных и вертикальных сумм или путем рассмотрения необходимых или отсутствующих значений.
Те записи с достаточно большими или маленькими подсказками для их длины будут иметь меньше возможных комбинаций для рассмотрения, и сравнивая их с записями, которые их пересекают, можно вывести правильную перестановку — или ее часть. Самый простой пример — когда 3-из-двух пересекает 4-из-двух: 3-из-двух должны состоять из «1» и «2» в некотором порядке; 4-из-двух (поскольку «2» не может быть продублировано) должны состоять из «1» и «3» в некотором порядке. Следовательно, их пересечение должно быть «1», единственной общей цифрой.
При решении более длинных сумм есть дополнительные способы найти подсказки для нахождения правильных цифр. Одним из таких методов было бы отметить, где несколько квадратов вместе разделяют возможные значения, тем самым исключая возможность того, что другие квадраты в этой сумме могут иметь эти значения. Например, если две подсказки 4-в-двух пересекаются с более длинной суммой, то 1 и 3 в решении должны быть в этих двух квадратах, и эти цифры не могут быть использованы в другом месте этой суммы. [4]
При решении сумм, имеющих ограниченное количество наборов решений, это может привести к полезным подсказкам. Например, сумма 30-из-семи имеет только два набора решений: {1,2,3,4,5,6,9} и {1,2,3,4,5,7,8}. Если один из квадратов в этой сумме может принимать только значения {8,9} (например, если пересекающаяся подсказка — это сумма 17-из-двух), то это не только становится индикатором того, какой набор решений соответствует этой сумме, но и исключает возможность того, что любая другая цифра в сумме будет одним из этих двух значений, даже до определения того, какое из двух значений подходит этому квадрату.
Другой полезный подход в более сложных головоломках — определить, в какой квадрат входит цифра, исключив другие места в сумме. Если все пересекающиеся подсказки суммы имеют много возможных значений, но можно определить, что есть только один квадрат, который может иметь определенное значение, которое должна иметь рассматриваемая сумма, то какие бы другие возможные значения не допускала пересекающаяся сумма, это пересечение должно быть изолированным значением. Например, сумма 36-в-восьми должна содержать все цифры, кроме 9. Если только один из квадратов может принять значение 2, то это должно быть ответом для этого квадрата.
Иногда можно также применять «метод ящика», когда геометрия незаполненных белых ячеек на любом этапе решения позволяет это сделать: суммируя подсказки для ряда горизонтальных записей (вычитая значения любых цифр, уже добавленных к этим записям) и вычитая подсказки для в основном перекрывающихся серий вертикальных записей, разница может выявить значение частичной записи, часто одной ячейки. Этот метод работает, потому что сложение является как ассоциативным , так и коммутативным .
Обычной практикой является отметка потенциальных значений для ячеек в углах ячеек до тех пор, пока все, кроме одного, не будут доказаны как невозможные; для особенно сложных головоломок иногда решатели отмечают целые диапазоны значений для ячеек в надежде в конечном итоге найти достаточные ограничения для этих диапазонов из пересекающихся записей, чтобы иметь возможность сузить диапазоны до отдельных значений. Из-за ограничений по пространству, вместо цифр, некоторые решатели используют позиционную нотацию, где потенциальное числовое значение представлено отметкой в определенной части ячейки, что позволяет легко поместить несколько потенциальных значений в одну ячейку. Это также облегчает различение потенциальных значений от значений решения.
Некоторые решатели также используют миллиметровую бумагу , чтобы попробовать различные комбинации цифр, прежде чем вписывать их в сетку головоломки.
Как и в случае с судоку, только относительно легкие головоломки какуро могут быть решены с помощью вышеупомянутых методов. Более сложные требуют использования различных типов цепочек шаблонов, тех же видов, которые появляются в судоку (см. Pattern-Based Constraint Satisfaction and Logic Puzzles [5] ).
Математически головоломки Какуро можно представить как задачи целочисленного программирования , и они являются NP-полными . [6] См. также Ято и Сета, 2004. [7]
В головоломках Какуро легко распознать два вида математической симметрии: минимальные и максимальные ограничения являются двойственными, как и отсутствующие и требуемые значения.
Все комбинации сумм могут быть представлены с помощью битового представления. Это представление полезно для определения отсутствующих и требуемых значений с помощью побитовых логических операций .
Головоломки какуро появляются почти в 100 японских журналах и газетах. Какуро оставались самой популярной логической головоломкой в японской печатной прессе до 1992 года, когда судоку заняла первое место. [8] В Великобритании они впервые появились в The Guardian , а затем в The Telegraph и Daily Mail . [9]
