Расстановка фигур на доске

← →
Ricks © (2004-03-17 13:21) [0]

Здраствуйте! Мне задали неделю назад задачу. До сих пор не могу её сделать. Задача такая: расставить на шахматной доске ладьи всеми возможными способами так чтобы они не били друг-друга. Использую при этом рекурсию. Помогите пожайлуста.

← →
Алхимик © (2004-03-17 13:25) [1]

Яндекс, найдётся всё!
http://golovolomka.hobby.ru/books/gik/03.shtml

← →
Ricks © (2004-03-17 13:45) [2]

Спасибо. Я почитал, что-то там не очень понятно.
Я в принципе представляю как сделать, но не получается!
Может, кто-нибудь еще что либо подскажет?

← →
ssk (2004-03-17 13:48) [3]

сколько ладей надо расставить? восемь?

← →
Ricks © (2004-03-17 13:52) [4]

Да, и это, как я прочитал можно сделать 8!=40320 способами. А у меня находило то 62 то 106 тысяч :-(

← →
Sphinx © (2004-03-17 13:54) [5]

> Ricks © (17.03.04 13:45) [2]

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

Ай да, чуть не забыл, книга по Басику была, по простому, не по Вижуал, и алгоритм тоже на Басике.

Нее... это же не серьёзно.

← →
ssk (2004-03-17 14:16) [7]

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

10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000

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

потом сдвиг
01000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000

проверка и т.д.

пока не доберемся до комбинации
00000001 00000001 00000001 00000001 00000001 00000001 00000001 00000001

вот и все.

В Win9X Memo столько строчек не возьмет, на RichEdit надо заменить.

procedure TForm1.Button9Click(Sender: TObject);

procedure TakeNext(AvailPos, PrevPos: string);
var
i, l: Integer;
CurrChar: Char;
begin
l := Length(AvailPos);
CurrChar := Chr(Ord("a") + 8 - l);
if l = 1 then begin
Memo1.Lines.Add(PrevPos + CurrChar + AvailPos);
Exit;
end;
for i := 1 to l do
TakeNext(Copy(AvailPos, 1, i - 1) + Copy(AvailPos, i + 1, l - i),
PrevPos + CurrChar + AvailPos[i] + " ");
end;

begin
Memo1.Lines.BeginUpdate;
TakeNext("12345678", "");
Memo1.Lines.EndUpdate;
Memo1.Lines.Add(IntToStr(Memo1.Lines.Count));
end;

Расстановка фигур на доске Найти похожие ветки