Какуро

Каку́ро — головоломка с числами. Название Каку́ро происходит от японского сокращения касан куросу (яп. 加算クロス перекрёстное сложение); в США головоломка также известна под названием Cross Sums (англ. пересекающиеся суммы).

Лёгкая головоломка каку́ро

Правила игры

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

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

Вычислительная сложность

Задача какуро является NP-полной. К ней сводится задача о Гамильтоновых подграфах планарного смешанного графа со степенями вершин не более 3 (см. Доказательство NP-полноты задачи какуро).

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.