Задача про ферзей Опции

[Ola]

Помогите, пожалуйста, решить задачу про ферзей: на шахматной доске размером NxN расставить N ферзей, чтобы они не били друг друга. ???

[trminator]

таак... универ пошел

Если вкратце, то это почти полный перебор. Теперь подробнее

Сначала попробуй забыть, что это - ферзи. Пусть это будут ладьи. И расставляй ладей (ладьи? ладьев? брр...). Их хоть расставлять проще (чтобы была одна ладья в каждой строке и столбце).

Итак, у тебя есть как-то расставленные ладьи, друг друга не бьющие. Теперь остается проверить только диагонали

Вариант: после расстановки ладей расставляй слонов. А ферзи - это такие ладьи, которые одновременно еще и слоны

[zx1024]

Перебор с возвратом по вертикалям.
i-ого ферзя ставим на i-ую вертикаль на "небьющееся" место. i := i + 1;
Если i=N+1, то выход(Ok).
Если место под ферзя не нашли, то возврат рекурсии.
(i := i - 1).
Если i=0, то выход (Косяк).

[trminator]

В принципе, достаточно хранить не матрицу, а вектор. Допустим, если в клетке [i, j] стоит ферзь, то A[i] = j
То есть надо заполнить вектор числами от 1 до n так, чтобы...

вроде так: | i - j | <> | A[i] - A[j] | - это условие того, что два ферзя, стоящие в клетках [ i, A[i] ] и [ j, A[j] ] не на одной диагонали.

ЗЫ Куда делся автор вопроса?

[Ola]

Прсто автор уже решила эту задачу с помощью книги Вирта. Могу привести полностью программу.

Код

uses crt;
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.

Сообщение отредактировано: volvo - 17.12.2004 18:23

[borlpasc.narod.ru]

Ola
Все бы такие были!!! Молодец.!!!

[Sam0784]

чёта непонятно что за массивы а б с как эта рекурсия работает.
вроде в цикле от1 од 8 и восемь раз вызывается а тветов больше чем 8*8 как так
мне во бет про ладьи надо мот кто подскажет.