Какуро | это... Что такое Какуро? (original) (raw)
Какуро
Какуро
Лёгкая головоломка каку́ро
Каку́ро — головоломка с числами, которую можно назвать математическим аналогом кроссворда. Название Каку́ро происходит от японского сокращения kasan kurosu (加算クロス, перекрестное сложение); в США головоломка также известна под названием Cross Sums (пересекающиеся суммы).
Правила игры
Поле состоит из клеток чёрного и белого цвета. Несколько белых клеток, идущих подряд по горизонтали или по вертикали, называются блоком. Про каждый блок известна сумма цифр, которые должны стоять в этом блоке. Для горизонтальных блоков эта сумма обычно записывается непосредственно слева от блока, а для вертикальных — непосредственно сверху.
Во все белые клетки нужно вписать по одной цифре от 1 до 9 так, чтобы, во-первых, сумма цифр в каждом блоке сошлась с указанным числом, а во-вторых, чтобы в каждом блоке все цифры были различны.
Вычислительная сложность
Задача какуро является NP-полной. К ней сводится задача о Гамильтоновых подграфах планарного смешанного графа со степенями вершин не более 3 (см. Доказательство NP-полноты задачи какуро).
См. также
Ссылки
Какуро на Викискладе? |
---|
- Как решать какуро (инструкция от издательства Nikoli) (en)
- Список комбинаций чисел для решения какуро (en)
- Сайт о какуро на русском языке
- Решебник какуро on-line
NP-полные задачи | |
---|---|
Математика | |
Исследование операций:Оптимизация:Комбинаторная оптимизация | |
Максимизационная задача укладки (упаковки) | Упаковка в контейнеры (двумерная упаковка • линейная упаковка • упаковка по весу • упаковка по стоимости) • Задача о ранце (рюкзаке) |
Теория графов теория множеств | Задача о вершинном покрытии • Задача о клике • Задача о независимом множестве (наборе) • Задача о покрытии множества • Задача Штейнера • Задача коммивояжёра • Обобщённая задача коммивояжёра |
Алгоритмические задачи | Задача выполнимости булевых формул (в конъюнктивной нормальной форме) |
Логические игры и головоломки | Обобщённые пятнашки с костяшками >15) (задача поиска кратчайшего решения) • Задачи, решения которых применяются в Тетрис • Задача обобщённого судоку • Задача о заполнении латинского квадрата • Задача какуро |
См. также | Прикладная математика • Теория алгоритмов • Динамическое программирование • 21 NP-полная задача Карпа |
Классы сложности |
Категории:
- NP-полные задачи
- Головоломки
Wikimedia Foundation.2010.
Полезное
Смотреть что такое "Какуро" в других словарях:
- Кроссворд — Сетка классического кроссворда (соблюдена поворотная симметрия) Кроссворд (англ. Crossword пересечение слов) или крестословица (дословный перевод, предложенный … Википедия
- Задача о независимом наборе — Задача о независимом множестве относится к классу NP полных задач в области теории графов. По сути, она полностью эквивалентна задаче о клике. Независимый набор из 9 голубых вершин Множество вершин графа называется независимым, если никакие две… … Википедия
- Задача SAT — Задача выполнимости булевых формул (SAT или ВЫП) задача распознавания, важная для теории вычислительной сложности. Экземпляром задачи SAT является булева формула, состоящая только из имен переменных, скобок и операций (И), (ИЛИ) и (HE). Задача… … Википедия
- Задача ВЫП — Задача выполнимости булевых формул (SAT или ВЫП) задача распознавания, важная для теории вычислительной сложности. Экземпляром задачи SAT является булева формула, состоящая только из имен переменных, скобок и операций (И), (ИЛИ) и (HE). Задача… … Википедия
- Задача о коммивояжере — Задача коммивояжёра (коммивояжёр бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с… … Википедия
- Задача о коммивояжёре — Задача коммивояжёра (коммивояжёр бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с… … Википедия
- Задача коммивояжера — Задача коммивояжёра (коммивояжёр бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с… … Википедия
- Задача о рюкзаке — Задача о ранце (рюкзаке) одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов ограничен. Подобные… … Википедия
- Задача о рюказаке — Задача о ранце (рюкзаке) одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов ограничен. Подобные… … Википедия
- Задача трехмерной упаковки в объем — В теории сложности вычислений задача об упаковке в контейнеры NP трудная комбинаторная задача. Задача заключается в упаковке объектов предопределённой формы в конечное число контейнеров предопределённой формы таким способом, чтобы число… … Википедия