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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Правила игры[править | править исходный текст]

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

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

Вычислительная сложность задачи[править | править исходный текст]

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

Примечания[править | править исходный текст]

Ссылки[править | править исходный текст]