Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > Задача о 8 шахматных слонах


Автор: Dioniz 15.2.2005, 18:29
У меня проблема с такой задачей:
Расставить 8 слонов на шахматной доске(8x8) так,чтоб каждое поле было под боем.
Как реализовать это на паскале?Кажется.нужно использовать рекурсию.
Помогите,please!!!

Автор: Guest 10.11.2005, 19:47
А как это реализовать на ПАСКАЛЕ или СИ??

Автор: Pakshin A. S. 10.11.2005, 22:18
Модератор: не относящиеся к сути темы посты были удалены моератором.

Автор: darkart 10.11.2005, 23:21
Примерно так...
Код

program Chess;
const
  n=8;{размерность поля}
type
  TChessBoard=array[1..n,1..n] of boolean;{описание доски}
  TElephants=array[1..n] of 1..n;{описание положения слона}
var
  Elephant:TElephants;
  CB:TChessBoard;
  bol:boolean;{есть ли результат}
function Test(var Elephant:TElephants;var ChessBoard:TChessBoard):boolean;
{функция проверяет все ли поля биты}
var
  i,x,y:integer;
  bolResult:boolean;
begin
  for x:=1 to n do
    for y:=1 to n do
      ChessBoard[x,y]:=False;{инициализация}
  for i:=1 to n do{заполнение полей битых i-ым слоном}
  begin
    x:=i;
    y:=Elephant[i];
    while (x>0) and (y>0) do
    begin
      ChessBoard[x,y]:=True;
      dec(x);
      dec(y);
    end;
    x:=i;
    y:=Elephant[i];
    while(x<=n) and (y>0) do
    begin
      ChessBoard[x,y]:=True;
      inc(x);
      dec(y);
    end;
    x:=i;
    y:=Elephant[i];
    while(x>0) and (y<=n) do
    begin
      ChessBoard[x,y]:=True;
      dec(x);
      inc(y);
    end;
    x:=i;
    y:=Elephant[i];
    while(x<=n) and (y<=n) do
    begin
      ChessBoard[x,y]:=True;
      inc(x);
      inc(y);
    end;
  end;
  bolResult:=true;
  for x:=1 to n do
    for y:=1 to n do
      bolResult:=bolResult and ChessBoard[x,y];
  Test:=bolResult;
end;
function Next(var Elephant:TElephants):boolean;
{функция вычисляет следующее положение слонов}
var
  i:integer;
  bol:boolean;
begin
  bol:=true;
  for i:=1 to n do
    bol:=bol and (Elephant[i]=n);
  if bol then
    Next:=False
  else
  begin
    i:=1;
    while (Elephant[i]=n) and (i<=n) do
    begin
      Elephant[i]:=1;
      inc(i);
    end;
    inc(Elephant[i]);
    Next:=True;
  end;
end;
procedure InitElephants(var Elephant:TElephants);
{начальное положение слонов}
var
  i:integer;
begin
  for i:=1 to n do
    Elephant[i]:=1;
end;
procedure PrintResults(var Elephant:TElephants);
{вывод результата}
var
  i:integer;
begin
  writeln('Result:');
  for i:=1 to n-1 do
    write('(',i,',',Elephant[i],'),');
  writeln('(',n,',',Elephant[n],')');
end;
begin
  writeln('ChessBoard');
  InitElephants(Elephant);
  repeat
    bol:=Test(Elephant,CB);
  until bol or (not Next(Elephant));
  if bol then Printresults(Elephant);{печать первого варианта}
  readln;
end.

Автор: Nestea 11.11.2005, 19:02
Что-то она выводит толко название доски на экран - ChessBoard.. Пробовала пошагово прогонять, она в нек-е циклы вроде как не заходит..please, если можно доработать?

Автор: darkart 11.11.2005, 22:32
Цитата
Что-то она выводит толко название доски на экран - ChessBoard.

Надо подождать...
У меня выводит:
ChessBoard
Result:
(1,2),(2,4),(3,6),(4,3),(5,3),(6,6),(7,4),(8,2)
_

Автор: Guest 12.11.2005, 09:41
darkart Спасибки большие! smile А еще не подскажешь аналогичную задачку : как подсчитать кол-во слонов, чтобы под боем находилось все поле?

Автор: darkart 12.11.2005, 16:56
Вообще вот, но количество слонов для доски (nxn) будет n штук:
Код

program chess;
const
  n=4;{Размерность доски}
type
  TChessBoard=array[1..n,1..n] of boolean;{описание доски}
  TElephant=record{описание положения слона}
    x,y:integer;
  end;
  TElephants=array[1..n] of TElephant;{описание положения слонов}
  TStrIndexes=array[1..n] of integer;{строки доски которые используются}
var
  Elephant:TElephants;
  CB:TChessBoard;
  bol:boolean;{есть ли результат}
  k:integer;{количество слонов}
  strIndex:TStrIndexes;
function mink(n:integer):integer;
{вычисление минимально разумного количества слонов}
{т. к. один слон не может побить более 2*n-1 клеток поля}
begin
  mink:=trunc((n*n)/(2*n-1))+1;
end;
procedure InitStrIndexes(var strIndex:TStrIndexes;k:integer);
{инициализация номеров используемых строк}
var
  i:integer;
begin
  for i:=1 to k do
    strIndex[i]:=i;
end;
procedure InitElephants(var Elephant:TElephants;var strIndex:TStrIndexes;k:integer);
{инициализация положения слонов}
var
  i:integer;
begin
  for i:=1 to k do
  begin
    Elephant[i].x:=strIndex[i];
    Elephant[i].y:=1;
  end;
end;
function Test(var Elephant:TElephants;var ChessBoard:TChessBoard;k:integer):boolean;
{функция проверяет все ли поля биты}
var
  i,x,y:integer;
  bolResult:boolean;
begin
  for x:=1 to n do
    for y:=1 to n do
      ChessBoard[x,y]:=False;{инициализация}
  for i:=1 to k do{заполнение полей битых i-ым слоном}
  begin
    x:=Elephant[i].x;
    y:=Elephant[i].y;
    while (x>0) and (y>0) do
    begin
      ChessBoard[x,y]:=True;
      dec(x);
      dec(y);
    end;
    x:=Elephant[i].x;
    y:=Elephant[i].y;
    while(x<=n) and (y>0) do
    begin
      ChessBoard[x,y]:=True;
      inc(x);
      dec(y);
    end;
    x:=Elephant[i].x;
    y:=Elephant[i].y;
    while(x>0) and (y<=n) do
    begin
      ChessBoard[x,y]:=True;
      dec(x);
      inc(y);
    end;
    x:=Elephant[i].x;
    y:=Elephant[i].y;
    while(x<=n) and (y<=n) do
    begin
      ChessBoard[x,y]:=True;
      inc(x);
      inc(y);
    end;
  end;
  bolResult:=true;
  for x:=1 to n do
    for y:=1 to n do
      bolResult:=bolResult and ChessBoard[x,y];
  Test:=bolResult;
end;
procedure PrintResults(var Elephant:TElephants;k:integer);
{печать результата}
var
  i:integer;
begin
  writeln('Result:');
  for i:=1 to k-1 do
    write('(',Elephant[i].x,',',Elephant[i].y,'),');
  writeln('(',Elephant[k].x,',',Elephant[k].y,')');
end;
function NextStrIndex(var strIndex:TStrIndexes;k:integer):boolean;
{вычисление следующих номеров строк}
var
  i:integer;
  bol:boolean;
begin
  bol:=True;
  for i:=1 to k do
    bol:=bol and (strIndex[i]=n);
  if bol then NextStrIndex:=False
  else
  begin
    i:=1;
    while (strIndex[i]=n) and (i<k) do
    begin
      strIndex[i]:=1;
      inc(i);
    end;
    inc(strIndex[i]);
    NextStrIndex:=True;
  end;
end;
function Next(var Elephant:TElephants;var strIndex:TStrIndexes;k:integer):boolean;
{функция вычисляет следующее положение слонов}
var
  i:integer;
  bol:boolean;
begin
  bol:=true;
  for i:=1 to k do
    bol:=bol and (Elephant[i].x=n-k+i) and (Elephant[i].y=n);
  if bol then Next:=False
  else
  begin
    bol:=True;
    for i:=1 to k do
      bol:=bol and (Elephant[i].y=n);
    if bol then
    begin
      if NextStrIndex(strIndex,k) then InitElephants(Elephant,strIndex,k);
    end
    else
    begin
      i:=1;
      while (Elephant[i].y=n) and (i<k) do
      begin
        Elephant[i].y:=1;
        inc(i);
      end;
      inc(Elephant[i].y);
    end;
    Next:=True;
  end;
end;
begin
  writeln('ChessBoard');
  k:=mink(n);
  repeat
    writeln(k);
    InitStrIndexes(strIndex,k);
    InitElephants(Elephant,strIndex,k);
    repeat
      bol:=Test(Elephant,CB,k);
    until bol or (not Next(Elephant,strIndex,k));
    inc(k);
  until bol or (k>n);
  if bol then Printresults(Elephant,k-1) else writeln('No result.');{печать результата}
  readln;
end.

P.S.
Не задавай большое n(2<=n<=6), ждать за... мучаешься.

Автор: Nestea 12.11.2005, 21:16
Прям выручил!! )) А еще один вопросик, это не метод бэктрекинга случайно?

Автор: Nestea 12.11.2005, 21:28
darkart
При выполнении пишет
3
4
Эти циферки что обозначают?

Автор: darkart 12.11.2005, 22:16
Цитата
Прям выручил!! )) А еще один вопросик, это не метод бэктрекинга случайно?

Да.
Цитата
При выполнении пишет
3
4
Эти циферки что обозначают?

Для какого количества слонов считается.

Автор: Nestea 13.11.2005, 10:23
[/QUOTE]
Для какого количества слонов считается.

Всмысле 4 - это сколько нужно слонов, чтобы побить все поле? а 3 что значит?

Автор: darkart 13.11.2005, 11:01
Работа алгоритма:
1)Вычисление минимально разумного количества слонов - mink,
т. к. один слон не может бить более 2*n-1 клеток поля, где n-размерность поля, то
mink=[(n*n)/(2*n-1)]+1
2)для всех k(mink=<k<=n) идет всевозможная расстановка k слонов на поле и проверяется всяли доска бита
Так вот выводимые числа - это k для которого идет расчет в данный момент. smile

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)