Задача о ферзях , расстановка ферзей на шахматном поле

[samec]

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

[n0rd]

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

[LuckLess]

очевидно, что ответ <= 7
я бы даже предположил, что он(ответ) равен 6...

[volvo877]

LuckLess, ответ неверный Вполне хватит 5 ферзей (причем не только на доске 8*8, а даже на 11*11)

[Soul :)]

volvo877, а поподробней можно?

[volvo877]

Soul , подробней - здесь ("Задача о ферзях-часовых."):
http://golovolomka.hobby.ru/books/gik/04.shtml

[Bug Hunter]

Цитата volvo877 @ 30.05.06, 09:47

Вполне хватит 5 ферзей (причем не только на доске 8*8, а даже на 11*11)

А на доске 8x8 достаточно трех ферзей и двух ладьей:

Цитата

0 0 0 0 0 0 0 0
0 F 0 0 0 F 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 L
0 0 0 0 0 0 0 0
0 0 0 L 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 F 0 0 0 0

причем это для постановки задачи, когда требуеться, чтобы под боем находились все поля, в том числе и занятые фигурами.

[samec]

Спасибо всем за помощь! Вопрос снят

[samec]

Вот исходник на паскале, если кому понадобится :

program ferz;
{uses
 SysUtils;}
 
type desk = array [1..8,1..8] of 0..2;
{0-пусто; 1-поле которое бьёт ферзь; 2-ферзь}
var
cur_desk : desk;   {текущий статус доски}
now_f    : byte;   {какой ферьз ставится в данный момент}
count    : byte;   {количество на доске ферзей}
variants : word;   {количество возможных вариантов}
fi,fj    : array[1..5] of byte; {координаты ферзей}
i,j      : byte;   {для расстановки первого ферзя}
 
ferzes   : desk;
 
{заполнить "1" столбик и строку с номером позиции ферзя ki, kj}
 
procedure st(ki,kj:byte);
var i:integer;
begin
for i:=1 to 8 do
 begin
  if cur_desk[ki,i] <> 2 then
   cur_desk[ki,i] := 1;
  if cur_desk[i,kj] <> 2 then
   cur_desk[i,kj] := 1;
 end
end;
 
 
{заполнить "1" диагонали, которые бъёт ферзь с номером позиции ki, kj}
procedure diag(ki,kj:byte);
var i,j:integer;
begin
for i:=1 to 8 do
  for j:=1 to 8 do
   begin
    if abs(i-ki)=abs(j-kj) then
     if cur_desk[i,j]<>2 then cur_desk[i,j]:=1;
   end
end;
 
{проверяет бьют ли все 5 ферзей всё поле}
function filled : boolean;
var
i, j : integer;
fl   : boolean;
begin
fl:=true;
for i:=1 to 8 do
 for j:=1 to 8 do
  if cur_desk[i,j] = 0 then fl := false;
filled := fl  
end;
 
{выводит массив ferzes, то есть правильную расстановку}
procedure print_ar;
var
i,j:integer;
begin
for i:=1 to 8 do
 begin
  for j:=1 to 8 do
   write(ferzes[i,j],' ');
  writeln
 end;
readln
end;
 
 
{рекурсивная процедура которая расставляет ферзей
after_i,after_j переменные, которые служат для исключения повторений,
то есть поиск места для след. ферзя идёт по значениям i, j которые
идут после места только что поставленного ферзя}
 
procedure put(after_i,after_j:byte);
var
old_desk : desk;  {в ней хранится значения старой доски, чтоб при возврате из рекурсии}
                  {не терялись предыдущие значения}
 
i,j      : integer;
tempk    : byte;
begin
old_desk := cur_desk;
for i:=after_i to 8 do
begin
if i=after_i then tempk:=after_j
else tempk:=1; {нужно, так как after_j исп-зя один раз когда i=after_i,}
               {ведь дальше j идёт с 1}
 for j:=tempk to 8 do
  begin
   {это условие когда не могут ббить лруг друга, то есть ферзь ставится на место,}
   {где никто его не "обидит" => если нужна возможность бить друг друга}
   {делаем условие cur_desk[i,j] <> 2, тогда будет ставится в любое место, где не}
   {стоит другой ферзь}
   if cur_desk[i,j] = 0  then
    begin
     inc(now_f);    {now_f = now ferz, то есть какого ферзя ставим}
     inc(count);    {кол-во ферзей}
     fi[now_f]:=i;  {запоминаем i,j позицию ферзя с номером now_f}
     fj[now_f]:=j;
     cur_desk[fi[now_f],fj[now_f]]:=2;  {ставим его на доску}
 
     st(fi[now_f],fj[now_f]);    {2 процедуры, описанные выше}
     diag(fi[now_f],fj[now_f]);
 
     if count <> 5 then          {если не все ферзи поставлены}
      begin
       put(i,j);
       {восстанавливает значение, когда один из проходов закончен}
       {при возврате из рекурсии}
       cur_desk := old_desk;
       fi[now_f]:=0;
       fj[now_f]:=0;
       dec(count);
       dec(now_f)
      end
     else
      begin
       {ferzes - массив, которых хранит свеженайденный расклад событий на доске}
       {использунтся чтобы выводить варианты}
       fillchar(ferzes,sizeof(ferzes),0);
       ferzes[fi[1],fj[1]] := 1;
       ferzes[fi[2],fj[2]] := 1;
       ferzes[fi[3],fj[3]] := 1;
       ferzes[fi[4],fj[4]] := 1;
       ferzes[fi[5],fj[5]] := 1;
       {ставим 5-го ферзя и убираем его для дальнейшего его расставления,}
       {или чтобы не была мусорна 5 переменная, когда возвращаемся на расстановку}
       {4 ферзя(когда для 5 ферзя i=j=8)}
       fi[now_f]:=0;
       fj[now_f]:=0;
       dec(count);
       dec(now_f);
             if filled then
              begin
               inc(variants);
               {нашли вариант, и вывели массив если надо}
               print_ar;
               cur_desk:=old_desk;
              end
             else
              begin
               cur_desk:=old_desk;
              end
      end
 
    end
  end
end
end;
 
begin
{цикл по всей доске для выбора куда поставить самого 1 ферзя}
for i:=1 to 8 do
 for j:=1 to 8 do
  begin
   {показываю инициализацию доски для 1 ферзя}
   count := 0;
   now_f := 0;
 
   fillchar(cur_desk,sizeof(cur_desk),0);
   fi[1]:=i;
   fj[1]:=j;
 
   cur_desk[fi[1],fj[1]]:=2;
   st(fi[1],fj[1]);
   diag(fi[1],fj[1]);
 
   inc(count);
   inc(now_f);
 
   put(i,j);
  end;
 write('Число вариантов: ');
 writeln(variants);
 readln
end.