Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Потрепаться";
Текущий архив: 2002.10.03;
Скачать: [xml.tar.bz2];

Вниз

Задача-2   Найти похожие ветки 

 
Oleg_Gashev   (2002-09-08 22:11) [0]

В интернете решения не видел. Кто найдет, можете линк бросить, почитаю.
А вот и условие. Всем известна задача о расположении восьми ферзей на шахматной доске. Надо раставить их так, чтобы они не били друг друга. Как известно, на доске 8х8 есть 92 расположения. Причем эти расположения зеркальны. Задача зпключается в нахождении не зеркальных расположений. То есть никакое расположение нельзя получить из другого поворотом доски или его зеркальным отображением.


 
MBo   (2002-09-09 09:28) [1]

http://algolist.manual.ru/maths/combinat/queens.php
зеркальность не учитывается, но проверять такие варианты, imho, нетрудно


 
Kaban   (2002-09-09 09:36) [2]

Как то странно вы расуждаете
>>Задача зпключается в нахождении не зеркальных расположений.

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

Скорее всего задача стоит в нахождении базовых расположений. Т.е. тех, которые не являются зеркальными отображениями друг друга. Всего, насколько я помню, существует 92 отображения, из них 13 базовых


 
RV   (2002-09-09 10:22) [3]

а вот кто короче сформулирует алгоритм хождения по доске коня,
чтоб попал в каждое поле по одному разу?


 
SPeller   (2002-09-09 10:29) [4]

На листе в клетку я такое делал, но непомню уже как.


 
Kaban   (2002-09-09 10:30) [5]

1. Встаем в одну из 64 позиций шахматной доски
2. Вызываем рекурсивную функцию
2.1. Будем ходить конем по часовой стрелки
2.2. Если новая клетка не занята переходим к 2
3.2. Если занята или вышли за край доски переходим к 2.1
3.3. Если не возможно сделать ход во всех направлениях возвращаемся




 
Kaban   (2002-09-09 10:31) [6]

Если имеется в виду вручную, то проще всего по кругу по всей доске


 
RV   (2002-09-09 10:32) [7]

Kaban © (09.09.02 10:30)
так же на олимпиаде делал, но есть короче и красивее!


 
Kaban   (2002-09-09 10:37) [8]

Продемонстрируй, я в этом не уверен. На мой взгляд в общем случае залдачу надо решать именно так.


 
RV   (2002-09-09 10:43) [9]

не беда
тут действительно надо было знать следующее

Делаем ход конем туда, откуда минимальное число продолжений, но не равное 0.



 
Kaban   (2002-09-09 10:48) [10]

да, но чтобы знать это нужно было выполнить некоторые математические исследования и главное ЗНАТЬ. Будет время я обязательно попробую. И главное я по прежнему не уверен, что этот способ быстрее отыщет все решения. Как никак дополнительные затраты на вычисление следующей позиции. И главное не противоречит тому, что если я пойду в другом направлении, то не найду решение.


 
RV   (2002-09-09 10:52) [11]

главное ЗНАТЬ
вот вот, я и говорю.

И главное не противоречит тому, что если я пойду в другом направлении, то не найду решение.
я проверял, одно решение всегда есть
причем на разных досках и с разных позиций (ну не 3х3 и 4х4, стествв)
а программка мертва вместе с винтом :(



 
MBo   (2002-09-09 11:56) [12]

про коня - рядом с данной мной ссылкой


 
Oleg_Gashev   (2002-09-09 18:55) [13]

>Делаем ход конем туда, откуда минимальное число продолжений, но не равное 0.

Ne dlja vseh razmerov doski etot algoritm srabotaet.


 
RV   (2002-09-10 11:12) [14]

(ну не 3х3 и 4х4, стествв)

+ MBo © (09.09.02 11:56)



Страницы: 1 вся ветка

Форум: "Потрепаться";
Текущий архив: 2002.10.03;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.47 MB
Время: 0.007 c
1-8050
ava
2002-09-21 22:50
2002.10.03
Закипел


1-7958
Lamooooooooooooo
2002-09-24 10:52
2002.10.03
В чем разница?


14-8151
MaximatorVeter
2002-09-09 11:43
2002.10.03
Мелочи жизни


6-8095
BaNNeR
2002-08-03 11:25
2002.10.03
DELPHI irc-сервер и irc-клиент


7-8197
МИФИст
2002-07-26 21:35
2002.10.03
Как запустить...





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский