Пару месяцев назад появилась [занятная статья][1] с анализом классической задачи о расстановке ферзей на шахматной доске (см. детали и историю ниже). Задача невероятно известная и вся уже рассмотрена под микроскопом, поэтому было удивительно, что появилось что-то действительно новое.



[![image][2]
][3]Сможете поставить ещё шесть? А найти все решения?
(картинка из статьи)



Далее, к сожалению, произошла какая-то совершенно невразумительная история из цепочки вот таких вот превращений:


* Отличная статья ---пресс служба университета---> [невразумительный пресс-релиз][4].
* Пресс релиз ---занятный перевод---> [непонятная статья на гиктаймс][5]

Стоит отметить, что пять наугад открытых ссылок на русском ещё меньше проясняли картину происходящего.



Я тут подумал — надо бы кому-то эту странную цепочку прервать и нормальным языком изложить суть событий.



О чём пойдёт речь:


* [История задачи][6]
* [Латинский квадрат][7]
* [Задача о восьми ферзях][8]
* [Три типа задачи "о ферзях"][9]
* [Расстановка N ферзей][10]
* [Подсчет числа решений][11]
* [Дополнение до N ферзей][12]
* [Вариации задачи][13]
* [Модели и сложность][14]
* [Линейный поиск для N ферзей][15]
* [Как считать число решений на практике][16]
* [Дополнение до N][17]
* [Выводы][18][Читать дальше →][19]

[1]: http://www.jair.org/papers/paper5512.html
[2]: https://habrastorage.org/web/21b/c20/ab9/21bc20ab9a964a86886b5fff17a94799.png
[3]: https://habr.ru/topic/343738/
[4]: https://www.st-andrews.ac.uk/news/archive/2017/title,1539813,en.php
[5]: https://geektimes.ru/post/292631/
[6]: https://habr.ru/post/343738/#history
[7]: https://habr.ru/post/343738/#latin_square
[8]: https://habr.ru/post/343738/#eight_queens
[9]: https://habr.ru/post/343738/#types
[10]: https://habr.ru/post/343738/#classic
[11]: https://habr.ru/post/343738/#counting_problem
[12]: https://habr.ru/post/343738/#completion
[13]: https://habr.ru/post/343738/#other
[14]: https://habr.ru/post/343738/#problems
[15]: https://habr.ru/post/343738/#linear
[16]: https://habr.ru/post/343738/#counting
[17]: https://habr.ru/post/343738/#asp
[18]: https://habr.ru/post/343738/#conclusions
[19]: https://habrahabr.ru/post/343738/?utm_source=habrahabr&utm_medium=rss&utm_campaign=feed_posts#habracut