Модифицированные версии задачи о 8 ферзях

[frankenstein]

Добрый день народ. Сегодня наверное день, которого многие из нас ждут всю неделю.
Все занимаются своим любимым делом в том числе я. Сегодня я запасся огромным
количеством еды, и до упаду буду решать задачи соревнований по спортивному
программированию. Но здесь не об этом. Все, наверное, знают известную задачу о восьми
ферзях http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%B2%D0%BE%D1%81%D1%8C%D0%BC%D0%B8_%D1%84%D0%B5%D1%80%D0%B7%D1%8F%D1%85

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

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



Мутант 2, задачи о восьми ферзях.
Дана доска размера $20x20$, определите минимальное количество
ферзей, которые покроют всю доску, т. е. после их расположения не останется
неатакованных клеток, разрешается ставить их так, что они могут атаковать друг друга.

[Deggial]

Тема перемещена из форума «Беседы на околонаучные темы» в форум «Программирование»
Причина переноса: данная тема больше подходит к этому разделу.

[alex7851]

frankenstein в сообщении #917872 писал(а):

Мутант 2, задачи о восьми ферзях.

Жадный алгоритм + перебор с возвратом не поможет ли? Для досок размером до 8 не врет. Для 20 получилось 13 ферзей.

[frankenstein]

alex7851 в сообщении #918863 писал(а):

frankenstein в сообщении #917872 писал(а):

Мутант 2, задачи о восьми ферзях.

Жадный алгоритм + перебор с возвратом не поможет ли? Для досок размером до 8 не врет. Для 20 получилось 13 ферзей.

На каждом шаге ставить ферзя в клетку, так чтобы он бил как можно больше клеток - отличное решение.
Можете дать оценку сложности вашего решения?
Так же цель темы, собрать разные версии этой задачи, поэтому буду очень благодарен если предложите свою измененную версию задачи.

[mserg]

Линейное программирование - 12 ферзей

[frankenstein]

mserg в сообщении #921847 писал(а):

Линейное программирование - 12 ферзей

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

[mserg]

Нет, не жадину. Линейное программирование. Нижняя граница - не менее 8-ми. Для повышения оценки нужно много-много памяти.

[frankenstein]

Можете рассказать про свой метод?

[mserg]

Могу. Формулируется задача линейного программирования и решается с помощью готового математического пакета.

Пример можно найти тут:
http://np-soft.ru/npproject/projects/pu ... vering.htm
Описание ("программа") сделано на NP-языке, в качестве решателя в программе Quick NP использовался в CPLEX.

[frankenstein]

Цель которой я хотел достигнуть этом темой - собрать много разных версий задачи о восьми ферзях.
Ребята, очень круто, что вы решили задачи ( Признаюсь они очень скучные ).
Давайте собирать тут задачи о восьми ферзях.
Ведь интересно придумывать свою задачу, а тут еще узкая тематика.