Версия для печати темы
Нажмите сюда для просмотра этой темы в обычном формате
Форум «Всё о Паскале» _ Задачи _ Задача про ферзей
Автор: Ola 27.09.2003 10:20
Помогите, пожалуйста, решить задачу про ферзей: на шахматной доске размером NxN расставить N ферзей, чтобы они не били друг друга. ???
Автор: trminator 27.09.2003 11:41
таак... универ пошел 
Если вкратце, то это почти полный перебор. Теперь подробнее
Сначала попробуй забыть, что это - ферзи. Пусть это будут ладьи. И расставляй ладей (ладьи? ладьев? брр...). Их хоть расставлять проще (чтобы была одна ладья в каждой строке и столбце).
Итак, у тебя есть как-то расставленные ладьи, друг друга не бьющие. Теперь остается проверить только диагонали
Вариант: после расстановки ладей расставляй слонов. А ферзи - это такие ладьи, которые одновременно еще и слоны
Автор: zx1024 1.10.2003 21:19
Перебор с возвратом по вертикалям.
i-ого ферзя ставим на i-ую вертикаль на "небьющееся" место. i := i + 1;
Если i=N+1, то выход(Ok).
Если место под ферзя не нашли, то возврат рекурсии.
(i := i - 1).
Если i=0, то выход (Косяк).
Автор: trminator 2.10.2003 19:43
В принципе, достаточно хранить не матрицу, а вектор. Допустим, если в клетке [i, j] стоит ферзь, то A[i] = j
То есть надо заполнить вектор числами от 1 до n так, чтобы...
вроде так: | i - j | <> | A[i] - A[j] | - это условие того, что два ферзя, стоящие в клетках [ i, A[i] ] и [ j, A[j] ] не на одной диагонали.
ЗЫ Куда делся автор вопроса?
Автор: Ola 4.10.2003 12:06
Прсто автор уже решила эту задачу с помощью книги Вирта. Могу привести полностью программу.
var i:integer;
a:array[1..8] of boolean;
b:array[2..16] of boolean;
c:array[-7..7] of boolean;
x:array[1..8] of integer;
procedure Print;
var k:integer;
begin
for k:=1 to 8 do write(x[k]:3);
writeln;
end;
procedure Try(i:integer);
var j:integer;
begin
for j:=1 to 8 do
if (a[j]=true) and (b[i+j]=true) and (c[i-j]=true) then
begin
x[i]:=j;
a[j]:=false;b[i+j]:=false;c[i-j]:=false;
if i<8 then try(i+1)
else print;
procedure Try(i:integer);
var j:integer;
begin
for j:=1 to 8 do
if (a[j]=true) and (b[i+j]=true) and (c[i-j]=true) then
begin
x[i]:=j;
a[j]:=false;b[i+j]:=false;c[i-j]:=false;
if i<8 then try(i+1)
else print;
a[j]:=true;b[i+j]:=true;c[i-j]:=true;
end;
end;
begin
clrscr;
for i:=1 to 8 do a[i]:=true;
for i:=2 to 16 do b[i]:=true;
for i:=-7 to 7 do c[i]:=true;
try(1);
readln;
end.
Автор: borlpasc.narod.ru 4.10.2003 17:22
Ola
Все бы такие были!!! Молодец.!!!
Автор: Sam0784 6.05.2007 21:05
чёта непонятно что за массивы а б с как эта рекурсия работает.
вроде в цикле от1 од 8 и восемь раз вызывается а тветов больше чем 8*8 как так
мне во бет про ладьи надо мот кто подскажет.