Пять ферзей
Задача: Как расставить 5 ферзей на доске 8x8 так, чтобы они били всю доску? Можно, конечно полным перебором всех позиций, но это как-то многовато. Нет ли способа побыстрее?
Да, комбинаций где-то 1E+9, хотя это не так уж и много...можно попробовать из них выкинуть какие-нибудь лишние комбинации, надо сообразить...
не особенно недежный эвристический алгоритм сокращенного перебора.
Иначе сводится к поиску наименьшего доминирующего множества графа.
Иначе сводится к поиску наименьшего доминирующего множества графа.
здесь получаеться решение и с более частным подходом.
через максимальное перекрытие - каждого ферзя ставить так, чтобы он бил максимальное кол-во еще небитых клеточек.
получаеться и без вычислений видно куда их ставить.
через максимальное перекрытие - каждого ферзя ставить так, чтобы он бил максимальное кол-во еще небитых клеточек.
получаеться и без вычислений видно куда их ставить.
Это конечно не оконченное решение, а общие соображения, но может они помогут.
Если расставить 5 ферзей, например в левом верхнем углу, так что бы они не били друг друга по вертикали и горизонтали, то они будут "покрывать" по горизонтали поле 5*8 и вертикале 5*8. А в нижнем правом углу будет поле 3*3, которое этими ферзями по горизонтали и вертикали не бьется.
Это поле 3*3 можно побить только по диагонали и !тут самое интересное, поле это бьется только 5-ю диагоналями, то есть нужно задействовать все 5 ферзей (причем, так что б остались битыми предыдущие 2 области).
Стало быть, условие покрытия, выполнимо, когда по ферзи не стоят на одной вертикали и горизонтали.
Вот тут сокращение перебираемых вариантов.
Если нужно найти просто множество частных решений (эвристический алгоритм уже вроде предлагали), то можно рассматривать не все поле, а область 5*5, что бы ферзи из него покрывали по диагонали область 3*3.таких областей на поле 4.
Это все мои личные соображения, так что ты бы еще б лишний раз их проверил.
Если расставить 5 ферзей, например в левом верхнем углу, так что бы они не били друг друга по вертикали и горизонтали, то они будут "покрывать" по горизонтали поле 5*8 и вертикале 5*8. А в нижнем правом углу будет поле 3*3, которое этими ферзями по горизонтали и вертикали не бьется.
Это поле 3*3 можно побить только по диагонали и !тут самое интересное, поле это бьется только 5-ю диагоналями, то есть нужно задействовать все 5 ферзей (причем, так что б остались битыми предыдущие 2 области).
Стало быть, условие покрытия, выполнимо, когда по ферзи не стоят на одной вертикали и горизонтали.
Вот тут сокращение перебираемых вариантов.
Если нужно найти просто множество частных решений (эвристический алгоритм уже вроде предлагали), то можно рассматривать не все поле, а область 5*5, что бы ферзи из него покрывали по диагонали область 3*3.таких областей на поле 4.
Это все мои личные соображения, так что ты бы еще б лишний раз их проверил.