Другая задача про ферзей (язык Си)

[xakep139]

Задача звучит следующим образом: для заданного клеточного поля найти все размещения наименьшего числа ферзей таким образом, чтобы они били все его свободные поля.
Если можно подскажите пожалуйста литературу в помощь или алгоритм решения. Хотя можно и текст программы
Заранее спасибо!

[counter]

это тебе надо дискретную математику почитать про графы

Для этого достаточно найти наименьшее доминирующее множество в графе, вершины которого соответствуют клеткам шахматной
доски и две вершины связаны ребром, если и только если они взаимно достижимы ходом ферзя. Найденное множество вершин указывает, куда надо поставить ферзей, а их число, которое в данном случае равно пяти, есть число доминирования данного графа.

[xakep139]

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

Сообщение от counter

их число, которое в данном случае равно пяти

Почему именно пяти? И что значит в данном случае? Размер поля ведь произвольный.
Можно ли использовать алгоритм Магу для поиска множеств внешней устойчивости и как это реализовать??

[counter]

Почему именно пяти? И что значит в данном случае?

это в книге пример был какойто, так что не обращайте внимания


Вот что я нашел, посмотрите может пригодится:

http://forum.sources.ru/index.php?showtopic=143686
http://www.refal.net/doc/romanenko/rfplus/chp-1101.html
http://golovolomka.hobby.ru/books/gik/04.shtml
http://www.codenet.ru/progr/alg/8-queens/
http://www.mgopu.ru/PVU/2.1/Recurs/B...turn/queen.htm
http://www.piter.com/lib/97858878227...ml?fil=oop_ch5