Задача-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]

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