ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrey Ponomarenko                   2:5022/81.13   19 Oct 2001  18:42:22
 To : Alex Matzukevich
 Subject : 8 феpзей
 -------------------------------------------------------------------------------- 
 

 
 18 октября 2001 года (а было тогда примерно, блин, 14:28)
 некто Alex Matzukevich в своем письме к некому All писал:
 
  AM>     Подскажите пожалуйста алгоpитм pасстановки 8 феpзей на шахматной
  AM> доске. Очень нужно. Заpанее thanks
 
     Ставишь первого ферзя в первую клетку, ставишь второго, проверяешь бьтся ли
 они. Если да, то убираешь его и ставишь в следующую клетку и так далее. Если
 дошел до конца доски, а не все ферзи еще расставлены, то убираешь предыдущего
 ферзя и пытаешься ставить его на новое место.
 
 #include <conio.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <dos.h>
 #define N 8 // размер доски и число ферзей, котрых надо разместить на ней
 
 int Board[N+1][N+1]; // шахматная доска
 int Pos[N+1]; // поставленные позиции
 int Amount=0;
 
 // напечатать доску с расставленными ферзями
 void Print()
 {
   int i,j;
   clrscr();
   for(i=1;i<=N;i++) {
     for(j=1;j<=N;j++) {
       if(Pos[i]==j) textcolor(14); else textcolor(7);// если стоит - подсветим
       cprintf("%d ",Board[i][j]);
     }
     textcolor(7);
     cprintf("\n\r");
   }
 }
 
 // поставить ферзя Count в клетку [i,j]
 // если Count совпадает с уже стоящим - последний стирается
 int Put(int i, int j, int Count)
 {
   int x,y,k;
   // предварительный анализ
   if(Board[i][j]!=0) { // если клетка занята
     if(Board[i][j]!=Count) // если в клетке не тот же ферзь
       return 0; // нельзя поставить
     else // если в клетке тот же ферзь
       Pos[Count]=0; // сотрем позицию
   }
   else // если клетка свободна
     Pos[Count]=j; // запомним позицию
   // собственно действие с ферзем
   if(Board[i][j]==Count) // если в клетке тот же ферзь
     Board[i][j]=0; // уберем его
   else if(Board[i][j]==0) // если клетка свободна
     Board[i][j]=Count; // поставим его
   // пометка клеток доски по которым распространяется угроза
   for(k=1;k<=N;k++) { // по горизонтали
     if(k==j) continue;
     if(Board[i][k]==Count) Board[i][k]=0;
       else if(Board[i][k]==0) Board[i][k]=Count;
   }
   for(k=1;k<=N;k++) { // по вертикали
     if(k==i) continue;
     if(Board[k][j]==Count) Board[k][j]=0;
       else if(Board[k][j]==0) Board[k][j]=Count;
   }
   x=j; y=i; // по диагонали вправо-вниз
   while(x<=N && y<=N) {
     if(x==j && y==i) {
       x++; y++;
       continue;
     }
     if(Board[y][x]==Count) Board[y][x]=0;
       else if(Board[y][x]==0) Board[y][x]=Count;
     x++; y++;
   }
   x=j-1; y=i-1; // по диагонали влево-вверх
   while(x>=1 && y>=1) {
     if(x==j && y==i) {
     x--,y--;
       continue;
     }
     if(Board[y][x]==Count) Board[y][x]=0;
       else if(Board[y][x]==0) Board[y][x]=Count;
     x--,y--;
   }
   x=j; y=i; // по диагонали влево-вниз
   while(x>=1 && y<=N) {
     if(x==j && y==i) {
       x--,y++;
       continue;
     }
     if(Board[y][x]==Count) Board[y][x]=0;
       else if(Board[y][x]==0) Board[y][x]=Count;
     x--,y++;
   }
   x=j+1; y=i-1; // по диагонали вправо-вверх
   while(x<=N && y>=1) {
     if(x==j && y==i) {
       x++,y--;
       continue;
     }
     if(Board[y][x]==Count) Board[y][x]=0;
       else if(Board[y][x]==0) Board[y][x]=Count;
     x++,y--;
   }
   return 1; // удачно поставили
 }
 
 // поверка решения
 // возвращает число ?
 int Chech()
 {
   int i,j,Num=0,flag;
   for(i=1;i<=N;i++) {
     flag=0;
     for(j=1;j<=N;j++) {
       if(Board[i][j]==i && flag!=0) Num++;
     }
   }
   return Num;
 }
 
 // рекурсивная функция анализа
 // раскрывает дерево в глубину до первого решения
 int Analyse(int n, int row)
 {
   int col,Can,Move;
   char ch;
   for(col=1;col<=N;col++) { // проход по вертикалям
     if(n>0) { // если не достигли глубины
       Can=Put(row,col,row); // пробуем поставить ферзя в клетку [row,j]
       if(Can) { // если удачно
     Move=Analyse(n-1,row+1); // анализ на следующем уровне
     if(Move==1) { // если ход удачный
       Pos[row]=col; // запомним его
       return 1; // и вернемся
     }
     else // если ход неудачный
       Pos[row]=0; // сотрем его
       }
       Put(row,col,row); // убрать поставленного ферзя из клетки [row,j]
     }
     else { // если достигли глубины - анализируем ситуацию
       if(Chech()==0) {
     Print();
     cprintf("\n\rРешение #%d",++Amount);
     ch=getch();
     if(ch==27) exit(1);
     //delay(100);
       }
       return 0; // зашли в тупик
     }
   }
   return 0; // после перебора всех вертикалей неудача
 }
 
 void main()
 {
   int i,j;
   clrscr();
   for(i=0;i<=N;i++) for(j=0;j<=N;j++) Board[i][j]=0;
   for(i=0;i<=N;i++) Pos[i]=0;
   Analyse(N,1); // алгоритм вернет возможность решения
   if(Amount) cprintf("\n\n\Hайдено %d возможных решения.",Amount);
   else cprintf("Hет решения!!!.");
 }
 
 Могу также дать исходники на Лиспе и Прологе.
     Засим прощаюсь (может больше и не увидимся), Andrey
 
 ... .  Вынамп орет: БИ-2 - AudioTrack 03
 --- *Время работы Винды: 00 часа(ов) 49 минут(ы) 49 секунд(ы).*
  * Origin: Кто к нам с пивом придет, тот за водкой и побежит (2:5022/81.13)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    8 феpзей   Alex Matzukevich   18 Oct 2001 14:28:12   8 феpзей   Andrey Ponomarenko   19 Oct 2001 18:42:22   8 феpзей   Andrey Ponomarenko   22 Oct 2001 01:53:28