Обобщённое судоку

Обобщённое судоку

Обобщённое судоку — головоломка с числами, являющая естественным обобщением головоломки судоку на случай доски произвольного размера.

Содержание

Правила игры

Игровое поле состоит из квадрата размером N²×N², разделенного на меньшие квадраты со стороной N клеток. Таким образом, всего игровое поле насчитывает N4 клеток. В некоторых из них уже в начале игры стоят числа от 1 до N².

Задача состоит в том, чтобы заполнить свободные клетки числами от 1 до N² так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате N×N каждое число встречалось бы ровно один раз.

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

Задача обобщенного судоку NP-полна. К ней сводится задача о заполнении латинского квадрата.

Примечания

Ссылки


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Полезное


Смотреть что такое "Обобщённое судоку" в других словарях:

  • Обобщенное судоку — Обобщённое судоку  головоломка с числами, являющая естественным обобщением головоломки судоку на случай доски произвольного размера. Содержание 1 Правила игры 2 Вычислительная сложность задачи 3 Примечания …   Википедия

  • Судоку — Так выглядит судоку Судоку (яп. 数独 су:доку …   Википедия

  • Задача о коммивояжере — Задача коммивояжёра (коммивояжёр  бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с… …   Википедия

  • Задача о коммивояжёре — Задача коммивояжёра (коммивояжёр  бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с… …   Википедия

  • Задача коммивояжера — Задача коммивояжёра (коммивояжёр  бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с… …   Википедия

  • Коммивояжёра задача — Задача коммивояжёра (коммивояжёр  бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с… …   Википедия

  • Задача о независимом наборе — Задача о независимом множестве относится к классу NP полных задач в области теории графов. По сути, она полностью эквивалентна задаче о клике. Независимый набор из 9 голубых вершин Множество вершин графа называется независимым, если никакие две… …   Википедия

  • Задача SAT — Задача выполнимости булевых формул (SAT или ВЫП) задача распознавания, важная для теории вычислительной сложности. Экземпляром задачи SAT является булева формула, состоящая только из имен переменных, скобок и операций (И), (ИЛИ) и (HE). Задача… …   Википедия

  • Задача ВЫП — Задача выполнимости булевых формул (SAT или ВЫП) задача распознавания, важная для теории вычислительной сложности. Экземпляром задачи SAT является булева формула, состоящая только из имен переменных, скобок и операций (И), (ИЛИ) и (HE). Задача… …   Википедия

  • Задача о рюкзаке — Задача о ранце (рюкзаке) одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов ограничен. Подобные… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»