Первый вариант головоломки 1850 года, когда два ферзя заранее установлены на доску, а игрок должен расставить остальных ферзей (два решения задачи см. под катом)
Задача о N ферзях состоит в том, чтобы разместить N ферзей на доске размером N×N таким образом, чтобы ни один ферзь не находился под боем другого, при этом на доске заранее установлены несколько ферзей. То есть в итоге никакие два ферзя не должны находиться на одной линии или диагонали. Впервые задачку сформулировали в 1848 году, а в 1850 году придумали вариант головоломки, когда некоторое количество ферзей заранее поставлено на доску, а игрок должен расставить остальных, если это возможно.
Исследователи из Сент-Эндрюсского университета (Шотландия) опубликовали научную статью, в которой доказывают, что задача о N ферзях является не только #P-полной задачей, но также NP-полной задачей. Более того, Математический институт Клэя (США) готов заплатить миллион долларов любому, кто сможет оптимизировать решение этой задачи как задачи на доказательство P=NP.
Читать полностью »