Описание тега n-queens

Головоломка N -королев (канонически, головоломка 8 ферзей) - известная и классическая задача информатики из-за ее сложного характера и ее способности решать с помощью рекурсивного поиска с возвратом. Он часто используется для введения концепции поиска с возвратом.

Задний план

Проблема N ферзей появилась еще до компьютеров, и впервые была предложена и решена шахматистами в 19 веке. Задача задает вопрос, учитывая шахматную доску N x N, сколько существует уникальных способов разместить N ферзей на доске, чтобы ни один ферзь не напал на другого ферзя. Ферзь может перемещаться по вертикали, горизонтали и диагонали, поэтому при размещении каждого ферзя количество оставшихся допустимых позиций становится все меньше и меньше.

Процедура решения

Разумное рекурсивное решение с возвратом к проблеме N ферзей размещает по одному ферзю за раз, ограничивая пространство решений, рассматриваемое для дальнейших размещений ферзя, только законными позициями (в отличие от решения грубой силы, которое ожидает, пока все N ферзей не будут размещены для проверки. если размещение каждого ферзя действительно).

Вариации

Существуют вариации проблемы N ферзей - например, проблема N ладей (размещение N ладей на шахматной доске N x N таким образом, чтобы ни одна ладья не атаковала другую ладью), которая является немного менее ограниченной версией проблемы N ферзей, поскольку ладьи могут атаковать вертикально и горизонтально, но не по диагонали. Существуют и другие варианты с участием коней, слонов и королей, но эти фигуры обычно включают размещение более N фигур, чтобы задача не стала тривиальной.

Математики и компьютерные ученые опубликовали различные исследования по решению головоломки N -ферзей в различных контекстах: трехмерные шахматные доски, торроидальные шахматные доски и чрезвычайно большие шахматные доски.

Полезные ресурсы

Ресурсы, объясняющие проблему N-Queens

• Статья в Википедии о загадке 8 королев
• Задача N Queens в Wolfram Mathworld - дает полином производящей функции для определения решения как функции N
• Целочисленная последовательность A000170 в онлайн-энциклопедии целочисленных последовательностей - последовательность "Количество способов размещения n не атакующих ферзей на доске размером N x N" по мере увеличения N

Решения N-Queens в коде

• 8 Проблема Куинса в Rosetta Code - Решения проблемы N Куинса почти на 100 различных языках программирования
• Решение проблемы N Queens с помощью библиотеки оптимизации Google Operations Research
• Code Golf Stack Exchange: N Queens Puzzle - чрезвычайно компактные решения головоломки N Queens на различных языках программирования.