Головоломка «Восемь королев»

Математическая задача, поставленная на шахматной доске

Единственное симметричное решение головоломки восьми ферзей ( с точностью до поворота и отражения )

Головоломка о восьми королевах — это задача размещения восьми шахматных королев на шахматной доске 8×8 таким образом, чтобы никакие две королевы не угрожали друг другу; таким образом, решение требует, чтобы никакие две королевы не находились в одной строке, столбце или диагонали. Существует 92 решения. Задача была впервые поставлена ​​в середине 19 века. В современную эпоху ее часто используют в качестве примера задачи для различных методов компьютерного программирования .

Головоломка о восьми ферзях является частным случаем более общей задачи о n ферзях , заключающейся в размещении n неатакующих ферзей на шахматной доске n × n . Решения существуют для всех натуральных чисел n, за исключением n = 2 и n = 3. Хотя точное число решений известно только для n ≤ 27, асимптотическая скорость роста числа решений составляет приблизительно (0,143 n ) ⁿ .

История

Шахматный композитор Макс Беззель опубликовал задачу о восьми ферзях в 1848 году. Франц Наук опубликовал первые решения в 1850 году. ^[1] Наук также расширил задачу до задачи о n ферзях, с n ферзями на шахматной доске размером n × n клеток.

С тех пор многие математики , включая Карла Фридриха Гаусса , работали как над головоломкой с восемью ферзями, так и над ее обобщенной версией с n -ферзями. В 1874 году С. Гюнтер предложил метод, использующий определители для поиска решений. ^[1] Дж. В. Л. Глейшер усовершенствовал подход Гюнтера.

В 1972 году Эдсгер Дейкстра использовал эту задачу, чтобы проиллюстрировать мощь того, что он называл структурным программированием . Он опубликовал очень подробное описание алгоритма поиска с возвратом в глубину . ^[2]

Построение и подсчет решений прин= 8

Задача поиска всех решений задачи о 8 ферзях может быть довольно затратной в вычислительном отношении, поскольку существует 4 426 165 368 возможных расположений восьми ферзей на доске 8×8, ^[a] , но только 92 решения. Можно использовать сокращения, которые уменьшают вычислительные требования, или правила большого пальца, которые избегают вычислительных методов грубой силы . Например, применяя простое правило, которое выбирает одного ферзя из каждого столбца, можно уменьшить количество возможностей до 16 777 216 (то есть 8 ⁸ ) возможных комбинаций. Генерация перестановок еще больше уменьшает количество возможностей до всего лишь 40 320 (то есть 8! ), которые затем можно проверить на диагональные атаки.

Головоломка с восемью королевами имеет 92 различных решения. Если решения, которые отличаются только операциями симметрии вращения и отражения доски, считаются одним, то головоломка имеет 12 решений. Они называются фундаментальными решениями; представители каждого из них показаны ниже.

Фундаментальное решение обычно имеет восемь вариантов (включая его исходную форму), полученных путем поворота на 90, 180 или 270° и последующего отражения каждого из четырех вариантов вращения в зеркале в фиксированном положении. Однако одно из 12 фундаментальных решений (решение 12 ниже) идентично своему собственному повороту на 180°, поэтому имеет только четыре варианта (само решение и его отражение, его поворот на 90° и его отражение). ^[b] Таким образом, общее число различных решений равно 11×8 + 1×4 = 92.

Все основные решения представлены ниже:

Решение 10 имеет дополнительное свойство: никакие три ферзя не находятся на одной прямой .

Наличие решений

Алгоритмы грубой силы для подсчета количества решений вычислительно управляемы для n  = 8 , но будут неразрешимы для задач n  ≥ 20 , так как 20! = 2,433 × 10 ¹⁸ . Если цель состоит в том, чтобы найти единственное решение, можно показать, что решения существуют для всех n ≥ 4 без какого-либо поиска. ^{[3] [4]} Эти решения демонстрируют ступенчатые шаблоны, как в следующих примерах для n = 8, 9 и 10:

Приведенные выше примеры можно получить с помощью следующих формул. ^[3] Пусть ( i , j ) — квадрат в столбце i и строке j на шахматной доске n × n , k — целое число.

Один из подходов ^[3] заключается в следующем:

1. Если остаток от деления n на 6 не равен 2 или 3, то список представляет собой просто все четные числа, за которыми следуют все нечетные числа, не превышающие n .
2. В противном случае напишите отдельные списки четных и нечетных чисел (2, 4, 6, 8 – 1, 3, 5, 7).
3. Если остаток равен 2, поменяйте местами 1 и 3 в нечетном списке и переместите 5 в конец ( 3, 1 , 7, 5 ).
4. Если остаток равен 3, переместите 2 в конец четного списка, а 1,3 — в конец нечетного списка (4, 6, 8, 2 – 5, 7, 9, 1, 3 ).
5. Добавьте нечетный список к четному списку и расставьте ферзей в рядах, указанных этими номерами, слева направо (a2, b4, c6, d8, e3, f1, g7, h5).

Для n  = 8 это приводит к фундаментальному решению 1 выше. Далее следует еще несколько примеров.

• 14 ферзей (остаток 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
• 15 ферзей (остаток 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
• 20 ферзей (остаток 2): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 9, 11, 13, 15, 17, 19, 5.

Решения для подсчета других размеровн

Точное перечисление

Не существует известной формулы для точного числа решений для размещения n ферзей на доске n × n, т. е. числа независимых множеств размера n в графе ферзей n × n . Доска 27×27 является доской наивысшего порядка, которая была полностью пронумерована. ^[5] В следующих таблицах указано число решений задачи n ферзей, как фундаментальных (последовательность A002562 в OEIS ), так и всех (последовательность A000170 в OEIS ), для всех известных случаев.

Известно число размещений, в которых ни одна из трех ферзей не выстраивается на одной прямой (последовательность A365437 в OEIS ). ${\displaystyle n\leq 25}$

Асимптотическое перечисление

В 2021 году Майкл Симкин доказал, что для больших чисел n число решений задачи о n ферзях приблизительно равно . ^[6] Точнее, число решений имеет асимптотический рост , где — константа, лежащая в диапазоне от 1,939 до 1,945. ^[7] (Здесь o (1) представляет собой небольшую нотацию o .) ${\displaystyle (0.143n)^{n}}$ ${\displaystyle {\mathcal {Q}}(n)}$ $${\displaystyle {\mathcal {Q}}(n)=((1\pm o(1))ne^{-\alpha })^{n}}$$ ${\displaystyle \alpha }$

Если вместо этого рассмотреть тороидальную шахматную доску (где диагонали «заворачиваются» от верхнего края к нижнему и от левого края к правому), то на доске можно разместить n ферзей только при условии , что В этом случае асимптотическое число решений равно ^{[8] [9]} ${\displaystyle n\times n}$ ${\displaystyle n\equiv 1,5\mod 6.}$ $${\displaystyle T(n)=((1+o(1))ne^{-3})^{n}.}$$

Связанные проблемы

Более высокие измерения

Найдите количество неатакующих ферзей, которые можно разместить в d -мерном шахматном пространстве размера n . Более n ферзей можно разместить в некоторых более высоких измерениях (наименьший пример — четыре неатакующих ферзя в шахматном пространстве 3×3×3), и на самом деле известно, что для любого k существуют более высокие измерения, где n ^k ферзей недостаточно для атаки всех пространств. ^{[10] [11]}

Использование фигур, отличных от ферзей

На доске 8×8 можно разместить 32 коня , или 14 слонов , 16 королей или 8 ладей , так что никакие две фигуры не атакуют друг друга. В случае с конями простым решением будет разместить по одному на каждую клетку заданного цвета, так как они ходят только на противоположный цвет. Решение также просто для ладей и королей. Шестнадцать королей можно разместить на доске, разделив ее на клетки 2×2 и поместив королей в эквивалентные точки на каждой клетке. Размещение n ладей на доске n × n находится в прямом соответствии с матрицами перестановок порядка n .

Шахматные вариации

Похожие задачи можно задать для шахматных вариаций, таких как сёги . Например, задача n + k драконьих королей требует разместить k пешек сёги и n + k взаимно неатакующих драконьих королей на доске сёги n × n . ^[12]

Нестандартные доски

Полиа изучил задачу о n ферзях на тороидальной («бубликообразной») доске и показал, что решение на доске n × n существует тогда и только тогда, когда n не делится на 2 или 3. ^[13]

Доминирование

При наличии доски n × n число доминирования — это минимальное число ферзей (или других фигур), необходимых для атаки или занятия каждой клетки. Для n = 8 число доминирования ферзя равно 5. ^{[14] [15]}

Королевы и другие фигуры

Варианты включают смешивание ферзей с другими фигурами; например, размещение m ферзей и m коней на доске n × n так, чтобы ни одна фигура не атаковала другую ^[16] или размещение ферзей и пешек так, чтобы никакие два ферзя не атаковали друг друга. ^[17]

Магические квадраты

В 1992 году Демирёрс, Рафраф и Таник опубликовали метод преобразования некоторых магических квадратов в решения с n -ферзями и наоборот. ^[18]

латинские квадраты

В матрице n × n разместите каждую цифру от 1 до n в n местах матрицы так, чтобы никакие два экземпляра одной и той же цифры не находились в одной строке или столбце.

Точное покрытие

Рассмотрим матрицу с одним основным столбцом для каждого из n рядов доски, одним основным столбцом для каждого из n рядов и одним вторичным столбцом для каждой из 4 n − 6 нетривиальных диагоналей доски. Матрица имеет n ² строк: по одной для каждого возможного размещения ферзя, и каждая строка имеет 1 в столбцах, соответствующих рангу, ряду и диагоналям этого квадрата, и 0 во всех остальных столбцах. Тогда задача n ферзей эквивалентна выбору подмножества строк этой матрицы таким образом, что каждый основной столбец имеет 1 ровно в одной из выбранных строк, а каждый вторичный столбец имеет 1 не более чем в одной из выбранных строк; это пример обобщенной задачи точного покрытия , другим примером которой является судоку .

n- королев завершение

Задача завершения заключается в том, возможно ли, имея шахматную доску n × n , на которой уже размещены некоторые ферзи, разместить ферзя в каждом оставшемся ряду так, чтобы никакие два ферзя не атаковали друг друга. Этот и связанные с ним вопросы являются NP-полными и #P-полными . ^[19] Любое размещение не более чем n /60 ферзей может быть завершено, в то время как существуют частичные конфигурации примерно из n /4 ферзей, которые не могут быть завершены. ^[20]

Упражнение по разработке алгоритма

Поиск всех решений головоломки восьми королев — хороший пример простой, но нетривиальной проблемы. По этой причине ее часто используют в качестве примера проблемы для различных методов программирования, включая нетрадиционные подходы, такие как программирование ограничений , логическое программирование или генетические алгоритмы . Чаще всего ее используют в качестве примера проблемы, которую можно решить с помощью рекурсивного алгоритма , индуктивно формулируя проблему n королев в терминах добавления одной королевы к любому решению проблемы размещения n −1 королев на шахматной доске n × n . Индукция заканчивается решением «проблемы» размещения 0 королев на шахматной доске, которая является пустой шахматной доской.

Эту технику можно использовать гораздо более эффективно, чем наивный алгоритм поиска методом грубой силы , который рассматривает все 64 ⁸  = 2 ⁴⁸  = 281 474 976 710 656 возможных слепых размещений восьми ферзей, а затем фильтрует их, чтобы удалить все размещения, которые размещают двух ферзей либо на одном поле (оставляя только 64!/56! = 178 462 987 637 760 возможных размещений), либо во взаимно атакующих позициях. Этот очень плохой алгоритм, помимо прочего, будет выдавать одни и те же результаты снова и снова во всех различных перестановках назначений восьми ферзей, а также повторять одни и те же вычисления снова и снова для различных подмножеств каждого решения. Лучший алгоритм поиска методом грубой силы размещает одного ферзя в каждой строке, что приводит только к 8 ⁸  = 2 ²⁴  = 16 777 216 слепым размещениям.

Можно сделать гораздо лучше. Один алгоритм решает головоломку восьми ладей , генерируя перестановки чисел от 1 до 8 (которых 8! = 40 320), и использует элементы каждой перестановки в качестве индексов для размещения ферзя в каждом ряду. Затем он отклоняет доски с диагональными атакующими позициями.

Эта анимация иллюстрирует возврат к решению проблемы. Ферзь помещается в столбец, который, как известно, не вызывает конфликта. Если столбец не найден, программа возвращается к последнему хорошему состоянию, а затем пробует другой столбец.

Программа поиска в глубину с возвратом , небольшое улучшение метода перестановки, строит дерево поиска , рассматривая одну строку доски за раз, исключая большинство нерешительных позиций доски на очень ранней стадии их построения. Поскольку она отклоняет атаки ладьей и диагональю даже на неполных досках, она исследует только 15 720 возможных размещений ферзя. Дальнейшее улучшение, которое исследует только 5 508 возможных размещений ферзя, заключается в объединении метода, основанного на перестановке, с методом ранней обрезки: перестановки генерируются в глубину, и пространство поиска обрезается, если частичная перестановка производит диагональную атаку. Программирование ограничений также может быть очень эффективным для этой проблемы.

мин-конфликты решение для 8 ферзей

Альтернативой исчерпывающему поиску является алгоритм «итеративного ремонта», который обычно начинается со всех ферзей на доске, например, с одного ферзя на столбец. ^[21] Затем он подсчитывает количество конфликтов (атак) и использует эвристику для определения того, как улучшить размещение ферзей. Эвристика « минимальных конфликтов » — перемещение фигуры с наибольшим количеством конфликтов на клетку в том же столбце, где количество конфликтов наименьшее — особенно эффективна: она легко находит решение даже для задачи о 1 000 000 ферзей. ^{[22] [23]}

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

В качестве альтернативы обратному отслеживанию решения могут быть подсчитаны путем рекурсивного перечисления действительных частичных решений, по одной строке за раз. Вместо того, чтобы строить целые позиции доски, заблокированные диагонали и столбцы отслеживаются с помощью побитовых операций. Это не позволяет восстановить отдельные решения. ^{[24] [25]}

Образец программы

Следующая программа является переводом решения Никлауса Вирта на язык программирования Python , но обходится без индексной арифметики , найденной в оригинале, и вместо этого использует списки , чтобы сохранить программный код максимально простым. Используя сопрограмму в форме функции-генератора , обе версии оригинала могут быть объединены для вычисления одного или всех решений. Рассматривается всего 15 720 возможных размещений ферзя. ^{[26] [27]}

def  queens ( n :  int ,  i :  int ,  a :  list ,  b :  list ,  c :  list ):  if  i  <  n :  for  j  in  range ( n ):  if  j  не  в  a  и  i  +  j  не  в  b  и  i  -  j  не  в  c :  yield from  queens ( n ,  i  +  1 ,  a  +  [ j ],  b  +  [ i  +  j ],  c  +  [ i  -  j ])  else :  yield  aдля  решения  в  ферзях ( 8 ,  0 ,  [],  [],  []):  распечатать ( решение )

В популярной культуре

• В игре «Седьмой гость » восьмая головоломка: «Дилемма королевы» в игровой комнате особняка Штауфов — это де-факто головоломка восьми королев. ^{[28] : 48–49, 289–290}
• В игре «Профессор Лейтон и любопытная деревня » 130-я головоломка: «Слишком много королев 5» (クイーンの問題5 ) представляет собой головоломку с восемью королевами. ^[29]

Смотрите также

• Математическая игра
• Математическая головоломка
• Проблема отсутствия трех в ряд
• Ладийный многочлен
• массив Костаса

Примечания

1. Количество комбинаций 8 квадратов из 64 равно биномиальному коэффициенту ₆₄ C ₈ .
2. Другие симметрии возможны для других значений n . Например, существует размещение пяти неатакующих ферзей на доске 5×5, которое идентично его собственному повороту на 90°. Такие решения имеют только два варианта (само решение и его отражение). Если n > 1, решение не может быть равно своему собственному отражению, поскольку для этого потребовалось бы, чтобы два ферзя стояли друг напротив друга.

Ссылки

1. WW Rouse Ball (1960) «Проблема восьми королев», в Mathematical Recreations and Essays , Macmillan, Нью-Йорк, стр. 165–171.
2. О.-Дж. Даль , Э. В. Дейкстра , К. А. Хоар Структурное программирование , Academic Press, Лондон, 1972 ISBN  0-12-200550-3 , стр. 72–82.
3. Бо Бернхардссон (1991). "Явные решения проблемы N-ферзей для всех N". ACM SIGART Bulletin . 2 (2): 7. doi :10.1145/122319.122322. S2CID  10644706.
4. EJ Hoffman et al., "Constructions for the Solution of the m Queens Problem". Mathematics Magazine , Vol. XX (1969), pp. 66–72. [1] Архивировано 8 ноября 2016 года на Wayback Machine
5. Проект Q27
6. Сломан, Лейла (21 сентября 2021 г.). «Математик отвечает на шахматную задачу об атаке ферзей». Журнал Quanta . Получено 22 сентября 2021 г.
7. Симкин, Майкл (28 июля 2021 г.). «Число конфигураций $n$-ферзей». arXiv : 2107.13460v2 [math.CO].
8. Лурия, Зур (15 мая 2017 г.). «Новые границы числа конфигураций n-ферзей». arXiv : 1705.05225v2 [math.CO].
9. Боутелл, Кандида; Киваш, Питер (16 сентября 2021 г.). «Проблема $n$-ферзей». arXiv : 2109.08083v1 [math.CO].
10. Дж. Барр и С. Рао (2006), Проблема n-ферзей в высших измерениях, Elemente der Mathematik, т. 61 (4), стр. 133–137.
11. Мартин С. Пирсон. «Королевы на шахматной доске – за пределами второго измерения» (php) . Получено 27 января 2020 г.
12. Чатем, Дуг (1 декабря 2018 г.). «Размышления о проблеме n +k драконьих королей». Журнал занимательной математики . 5 (10): 39–55. doi : 10.2478/rmm-2018-0007 .
13. Г. Полиа, Uber die "doppelt- periodischen" Losungen des n-Damen-Problems, Джордж Полиа: Сборник статей Vol. IV, ГК. Рота, изд., MIT Press, Кембридж, Лондон, 1984, стр. 237–247.
14. Burger, AP; Cockayne, EJ; Mynhardt, CM (1997), «Доминирование и неизбыточность в графе ферзей», Discrete Mathematics , 163 (1–3): 47–66, doi : 10.1016/0012-365X(95)00327-S, hdl : 1828/2670 , MR  1428557
15. Weakley, William D. (2018), «Королевы мира за двадцать пять лет», в Gera, Ralucca ; Haynes, Teresa W. ; Hedetniemi, Stephen T. (ред.), Теория графов: любимые гипотезы и открытые проблемы – 2 , Задачники по математике, Cham: Springer, стр. 43–54, doi : 10.1007/978-3-319-97686-0_5, ISBN 978-3-319-97684-6, г-н  3889146
16. "Проблема ферзей и коней". Архивировано из оригинала 16 октября 2005 г. Получено 20 сентября 2005 г.
17. Белл, Джордан; Стивенс, Бретт (2009). «Обзор известных результатов и областей исследований для n-ферзей». Дискретная математика . 309 (1): 1–31. doi : 10.1016/j.disc.2007.12.043 .
18. O. Demirörs, N. Rafraf и MM Tanik. Получение n-ферзевых решений из магических квадратов и построение магических квадратов из n-ферзевых решений. Журнал занимательной математики, 24:272–280, 1992
19. Gent, Ian P.; Jefferson, Christopher; Nightingale, Peter (август 2017 г.). «Сложность завершения n-Queens». Journal of Artificial Intelligence Research . 59 : 815–848. doi : 10.1613/jair.5512 . hdl : 10023/11627 . ISSN  1076-9757 . Получено 7 сентября 2017 г.
20. Глок, Стефан; Коррейя, Дэвид Мунха; Судаков, Бенни (6 июля 2022 г.). «Проблема завершения n-ферзей». Исследования в области математических наук . 9 (41): 41. doi : 10.1007 /s40687-022-00335-1 . PMC 9259550. PMID 35815227.  S2CID  244478527. 
21. Полиномиальный алгоритм для задачи N-ферзей Рока Сосича и Джуна Гу, 1990. Описывает время выполнения для 500 000 ферзей, что было максимальным временем, которое они могли выполнить из-за ограничений памяти.
22. Минтон, Стивен; Джонстон, Марк Д.; Филипс, Эндрю Б.; Лэрд, Филипп (1 декабря 1992 г.). «Минимизация конфликтов: эвристический метод исправления для удовлетворения ограничений и проблем планирования». Искусственный интеллект . 58 (1): 161–205. doi :10.1016/0004-3702(92)90007-K. hdl : 2060/19930006097 . ISSN  0004-3702. S2CID  14830518.
23. Sosic, R.; Gu, Jun (октябрь 1994 г.). «Эффективный локальный поиск с минимизацией конфликтов: исследование случая n-ферзей». IEEE Transactions on Knowledge and Data Engineering . 6 (5): 661–668. doi :10.1109/69.317698. ISSN  1558-2191.
24. Цю, Цзунъянь (февраль 2002 г.). «Битово-векторное кодирование проблемы n-ферзя». ACM SIGPLAN Notices . 37 (2): 68–70. doi :10.1145/568600.568613.
25. Ричардс, Мартин (1997). Алгоритмы обратного отслеживания в MCPL с использованием битовых шаблонов и рекурсии (PDF) (Технический отчет). Компьютерная лаборатория Кембриджского университета. UCAM-CL-TR-433.
26. Вирт, Никлаус (1976). Алгоритмы + Структуры данных = Программы . Серия Prentice-Hall по автоматическим вычислениям. Prentice-Hall. Bibcode :1976adsp.book.....W. ISBN 978-0-13-022418-7.стр. 145
27. Вирт, Никлаус (2012) [оригинал 2004]. «Проблема восьми королев». Алгоритмы и структуры данных (PDF) . Версия Oberon с исправлениями и авторизованными изменениями. стр. 114–118.
28. ДеМария, Русел (15 ноября 1993 г.). Седьмой гость: официальное руководство по стратегии (PDF) . Prima Games. ISBN 978-1-5595-8468-5. Получено 22 апреля 2021 г. .
29. «ナゾ130 クイーンの問題5».ゲームの匠(на японском языке) . Проверено 17 сентября 2021 г.

Дальнейшее чтение

• Белл, Джордан; Стивенс, Бретт (2009). «Обзор известных результатов и областей исследований для n-ферзей». Дискретная математика . 309 (1): 1–31. doi : 10.1016/j.disc.2007.12.043 .
• Уоткинс, Джон Дж. (2004). Across the Board: Математика шахматных задач . Принстон: Princeton University Press. ISBN 978-0-691-11503-0.
• Эллисон, Л.; Йи, КН; Макгоги, М. (1988). «Трехмерные задачи NxN-ферзей». Кафедра компьютерных наук, Университет Монаша, Австралия.
• Нудельман, С. (1995). «Проблема модульных N-ферзей в высших размерностях». Дискретная математика . 146 (1–3): 159–167. doi : 10.1016/0012-365X(94)00161-5 .
• Энгельхардт, М. (август 2010 г.). «Der Stammbaum der Lösungen des Damenproblems (по-немецки означает Родословная схемы решений проблемы 8 ферзей». Spektrum der Wissenschaft : 68–71.
• О модульной проблеме N-ферзя в более высоких измерениях, Рикардо Гомес, Хуан Хосе Монтеллано и Рикардо Штраус (2004), Институт математики, Область научных исследований, Внешний вид цепи, Университетский городок, Мексика.
• Бадд, Тимоти (2002). "Исследование случая: головоломка восьми королев" (PDF) . Введение в объектно-ориентированное программирование (3-е изд.). Эддисон Уэсли Лонгман. стр. 125–145. ISBN 0-201-76031-2.
• Вирт, Никлаус (2004) [обновлено в 2012]. «Проблема восьми королев». Алгоритмы и структуры данных (PDF) . Версия Oberon с исправлениями и авторизованными изменениями. С. 114–118.

Внешние ссылки

• Вайсштейн, Эрик В. «Проблема королев». MathWorld .
• queens-cpm на GitHub Головоломка «Восемь королев» в Turbo Pascal для CP/M
• eight-queens.py на GitHub Решение головоломки «Восемь королев» в одну строку на Python
• Решения на более чем 100 различных языках программирования (на Rosetta Code )