Небезызвесная задача о расстановке 8 ферзей на шахтатной доске так, чтобы они не били друг друга. 
Всего существует 92 решения. Но основных из них 12. Остальные получаются из них при помощи симметрии (центральной, осевой и т.д.) Нигде в нете не удалось найти решение данной задачи для этих 12 расстановок.  у меня есть очевидное решение: идет генерация ВСЕХ 92 решений и последующая проверка на симметрию с сохраненными предыдущими решениями. 

Вопрос: можно ли этот процесс каким либо образом оптимизировать. буду рад в том числе и математическому обоснованию.

Заранее спасибо. 

На мой взгляд, в данном конкретном случае оптимизировать совершенно незачем --- число проверок равно C(92, 2)=4186 --- т.е. совсем небольшое.
Однако поиск решений можно оптимизировать, если вести перебор с оглядкой на симметрию. Например, выдвинув предположения:
- количество ферзей в нижней половине доски не меньше четырех;
- количество ферзей в левой половине доски не меньше четырех.

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

Kuvaldis, Я как то делал программу на нахождение всех комбинаций. Вроде она давала 96 решений. Но в принципе можно покапаться в архиве и уточнить точное значение. Кстати, как ты вышел на цифру 12? Вроде 92 не делется на 12 нацело. Хотя по логике должно. 

Вообще-то более чем очевидно - ибо на каждой вертикали (горизонтали) может быть только 1 ферзь... 

Не должно. 
Например, число способов раскраски каждой стороны квадрата в один из двух цветов равно 16. А с учетом вращений --- 6. 
Это определяется теоремой <забыл кого> и связано с порядком подгрупп допустимых преобразований.

Добавлено @ 17:43 

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

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

Вот код программы. Она герерирует не все 92 а только 74 варианта. Т.е. оптимизация к сожалению не хорошая.

int Queen_Virt(int n) - классическая функция из книги Вирта "Алгоритмы и структуры данных"

int Queen_Virt_optim(int n)  - "оптимизированная" 


Я тут еще подумал о следующем.
Если я не ошибаюсь, то любое размещение ОДНОЗНАЧНО определяется положением первого поставленного ферзя. Если его ставить в 1/8 часть доски: между главной диагональю до середины и вертикальной осью симметрии, то как раз и будут эти 12 вариантов. Но... кардинально меняется алгоритм. Извилин не хватает его реализовать.
 

http://forum.vingrad.ru/index.php?showtopic=75536
http://forum.vingrad.ru/index.php?showtopic=72136

а искать по Инету я даже не пытался - ну просто потому что.

PS. Оптимизация ради оптимизации мне представляется занятием менее чем осмысленным. А цели не видать... разве что вместоделается, наоборот, генерация всех возможных симметричных преобразований при нахождении очередного базового решения. Тогда сравнение с уже найденными можно производить после установки первых 4 ферзей.
 

Представим, что у нас доска не 8 х 8, а 200 х 200 , т.е. смысл есть (для чего, в принципе, все и делается)



Т.е. я нашел вариант, прокрутил все возможные симметрии. Но.. все равно придется дедовским способом генерировать остальные 92 варианта (чтобы ничего не пропустить). Или я не прав? Т.Е. выигрыш маленький

Как найти следующее базовое решение? В этом смысл.

Еще более пристально порылся в нете.

Вот цитата из книги "Шахматы и математика"



методы Пермантье, Ла-Ное, Гюнтера, Глэшера, Лакьера - про них нигде нет.

Добавлено @ 21:39 

C этого я и начал, но там нет ответа на мой вопрос (там решение в лоб) 

Вот нашел в архивах свое решение этой задачи  Она быстренько генерирует все 92 решения. Оказывается я плохо помню, какие результаты были лет пять назад   

  

Я дальше тогда не стал делать оптимизацию, чтобы выкинуть все сеиметричные решения. Но были такие мысли. У меня поле представлено 8 числами от 0 и до 7. В принципе комбинацию можно свести в 24 битовое число. Все комбинации свести в массив чисел. Сделать подпрограмму поворачиваюшую комбинацию на 90 градусов и делаюшую зеркалку. Потом только останется делать перебор всех симетричных комбинаций.
Но это только мысли. Не проверял.     

Это сообщение отредактировал(а) Fin - 26.7.2006, 23:58

Качество оптимизации перебора определяется прежде всего количеством позиций, которые пришлось перебирать при поиске всех решений. 
А используют ли правила отсечения вариантов свойства симметрии или какие другие особенности задачи --- это уже детали.

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

Ну что, граждане? Достаточно серьезная задачка?
На русском языке я ничего не нашел, но на буржуйском кое-что  ... быстрый алгоритм без поиска с возвращением на основе градиентной эвристики (мой перевод)
Кого заинтересовало, смотри ссылкуФерзи 

Неплохо было бы, собственно, увидеть постановку задачи.
Непонятно, что Вас интересует: 
- алгоритм выделения решений с точностью до симметрии среди всех решений;
- алгоритм поиска всех решений для доски 8х8;
- алгоритм поиска всех решений для досок больших размеров;
- алгоритм поиска некоторых решений для досок очень больших размеров (~500000 ферзей).
 

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

И где там написано, что они находят все решения? 

Но алгоритма по гегерации ИМЕННО симметричных решений я так и не нашел   

Мне кажется, Вы как-то неверно оцениваете трудоемкость различных аспектов задачи:
И процедура выделения решениий с точностью до симметрии (я полагаю, Вы это имели в виду, когда написали "симметричных решений") среди всех решений, и, обратно, процедура построения всех решений по множеству "симметричных" решений --- все это мелочи по сравнению с самим поиском решений, основное время тратится обычно на перебор.

Алгоритм же, на который Вы дали ссылку, насколько я понял, эвристический и 
не гарантирует нахождения всех решений, а это совсем другая задача. 

nostromo, 



1. Извините, немного не хватило знаний (по поводу сложности алгоритмов и т.п., только на 2 курс перешел)  
Сегодня его сам внимательно почитал, пришлось буржуйский вспомнить. Полностью с вами согласен: данный алгоритм нацелен на поиск ОДНОГО решения.

2. Съездил в Национальную библиотеку по поводу этой проблемы. Полистал математические журналы.  Вывод: алгоритма генерации только симметричных решений НЕ СУЩЕСТВУЕТ Единственный вариант их получения: сравнение с уже полученными (т.е. решение в лоб)

Но все равно спасибо, стал умнее     

а как насчет алгоритма обхода конем всех полей шахматной доски без повторений и за раз. (т.н. задача Эйлера)
тока влоб? и то не дождешься. 
или я слишком отстал ...... 

Это другая задача, и если она действительно Вас инетересует, то лучше создайте отдельную тему. 

нет ветку создавать я не буду , я к тому что специфика та же и решение в лоб не получается (по крайней мере в "разумное" время ) 

alexius, Я решал и эту задачу. Тут можно применить эвристику и одно решение находится довольно быстро. На моем компе меньше, чем за секунду. 

Сформулируйте свою задачу. Доски каких размеров Вас интересуют? Все ли способы обхода нужно находить, или достаточно одного?

Здесь случайно не то описано?   

Это сообщение отредактировал(а) nostromo - 30.7.2006, 15:53

спасибо добрым людям, (сам бы во век не нашел)
А есть ли что-то для досок другого размера и для всех возможных случаев обхода? Мне так, интересно просто  

Ребята, буквально на прошлой неделе перелопатил все, что мог найти, по задаче о ходе коня. Лучше из найденного  здесь