Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Задача с пятью ферзями

Автор: Greeneyed 21.4.2006, 13:55

Нужно написать программу, расставляющию 5 ферзей но поле 8х8 так,чтобы каждая клетка была под ударом хотябы одного ферзя. Нельзя пользоваться вызывами функцмй,т.е. всё должно быть в одном мудуле. Написать это нужно на С.

Автор: Akina 21.4.2006, 14:20

Нужно - ПИШИ, когда напишешь, ту часть кода что работает неверно - в студию.

Алгоритм прост - перебор. 5 вложенных циклов перебора позиций, в них 4 вложенных цикла проверки боев, и никаких функций.

Автор: SoWa 21.4.2006, 18:29

Да. Иных решений нету. Перебор долгий конечно, если не сокращать. А вообще уже обсуждалось, но немного другая задача- чтобы ферзи друг друга не били. Поищи.

Автор: Greeneyed 22.4.2006, 09:44

Задачу я, вроде бы, решил. Вот только она выдаёт 5728 вариантом. По-моему многова-то. А ещё я в инете видел, что их всего 4860. Если кому не лень, посмотрити прикреплённый файл.

Автор: SoWa 22.4.2006, 19:50

А ты повторы проверял? smile

Автор: Greeneyed 22.4.2006, 21:37

Цитата(SoWa @ 22.4.2006, 19:50)

А ты повторы проверял? smile

Нет. Их там,вроде бы, быть не должно.

Автор: mes 23.4.2006, 00:02

Цитата(Greeneyed @ 22.4.2006, 21:37)

Цитата(SoWa @ 22.4.2006, 19:50)

А ты повторы проверял? smile

Нет. Их там,вроде бы, быть не должно.

Как минимум есть повторения относительно поворота доски на 180 градусов. smile

Взять хотя бы последнюю позицию, если повернуть доску - то она станет первой.
Чтоб такого не происходило перемешение одного из ферзей надо ограничить половиной доски:
Т.е вместо

Код


for(a=0;a<60;a++)

Поставить

Код


for(a=0;a<32;a++)

К сожалению нет возможности проверить , буду рад если кто проверит и скажет сколько вариантов получится.

P.S. Я думаю в строчке:

Код


int j;

не хватает обнуленя:

Код


int j=0;

P.S.S.

Способ определения битых полей у тебя слишком "громоздкий" - много бесполезных операций- поле деятельности для оптимизации. smile

Автор: Greeneyed 23.4.2006, 14:40

Цитата(mes @ 23.4.2006, 00:02)

Как минимум есть повторения относительно поворота доски на 180 градусов. smile

Ну, тогда поворот на 90 градусов.

Цитата(mes @ 23.4.2006, 00:02)

Способ определения битых полей у тебя слишком "громоздкий" - много бесполезных операций- поле деятельности для оптимизации. smile

Да я и сам знаю. Но ничего попроще придумать не могу.

Автор: mes 23.4.2006, 18:08

Цитата(Greeneyed @ 23.4.2006, 14:40

)

Да я и сам знаю. Но ничего попроще придумать не могу.

Ну например чтоб найти месторасположение ферзя не нужно просматривать каждую клетку.
У тебя есть номер клетки, а его легко превратить в номер горизонтали и вертикали.
например для ферзя е:

Код



  f_e_x = (e >> 3) & 7;// номер горизонтали (от 0 до 7)
  f_e_y = e & 7; // номер вертикали (от 0 до 7)

for(y= f_e_y; y<64;y+=8) {

    if(doska[y]!=9) doska[y]=1;} //заполняет единицами вертикаль на которой стоит ферзь е

для горизонтали можно и подругому: искатъ не номер горизонтали, а номер клетки, с которой начинается горизонталь.
например, чтоб для ферзя найти номер клетки, с которой начинается горизонталь на которой он рассположен, надо стереть последние 3 бита (остаток от деления на 8):

Код



f_e_nx:= е & 56;// номер первой клетки горизонтали (0,8,16,24,...)

for(x= f_e_nx; x<f_e_nx+8;x++) {
 if(doska[x]!=9) doska[x]=1;} //заполняет единицами горизонталь на которой стоит ферзь е

Для диагонали: мы уже нашли номер горизонтали и вертикали (f_e_x, f_e_y). Чтоб найти начало одной из диагоналей нужно из обоих переменных вычесть наименьшую из них. Как найти конец первой диагонали и полностью вторую диагональ я думаю понятно smile

P.S. мне кажется если для ферзей вместо группы переменных ты создашь массив будет легче организовать цикл заполнения битых полей.

P.S.S

Код



вместо 

if(doska[k]!=9) doska[k]=1;

а бы использовал 

 doska[k]|=1;

так как у 9 в любом случае последний бит равен 1. Но ето дело вкуса. smile

Добавлено @ 18:18

Цитата(Greeneyed @ 22.4.2006, 09:44

)

Вот только она выдаёт 5728 вариантом. По-моему многова-то. А ещё я в инете видел, что их всего 4860.

Только что проверил твой исходник. После обнуления счетчика ( int j=0; smile

) показал именно 4860 вариантов.
Значит в принципе у тебя всё правильно.

Автор: Greeneyed 27.4.2006, 17:05

Спасибо. Буду исправлять.

Автор: Greeneyed 25.5.2006, 20:37

Препод - нехороший человек!!!!!!!!!!!!! Сказал, чтоб я всё сделал через функции и, чтобы можно было задавать положение первого ферзя. Никак не могу придумать функцию полного перебора. Помогите пожалуйста.

Автор: mes 29.5.2006, 02:13

В таком виде пойдет?

Код



//---------------------------------------------------------------------------

#pragma hdrstop

//---------------------------------------------------------------------------
#include "stdio.h"
#include"conio.h"
#include "stdlib.h"
#pragma argsused

unsigned char F[5]; //Pozicii Ferzej
typedef unsigned char doska[8]; // 8 x 8 BITOV (dlja ekonomii vycheslenij :))

doska D,  // doska dlja proverki bityx polej
      D1; // doska dlja razmeshenija ferzej

void Clear (doska d) // ochishenie
{d[1]=d[2]=d[3]=d[4]=d[5]=d[6]=d[7]=d[8]=0;
}
void Print (doska d) //otobrazhenie doski na monitore
{  unsigned char i,j;

   for (i=8; i>0; i--) //obratnyj otschet dlja pravil'nogo izobrazhenija doski
   {
   for (j=0; j<8; j++)
       { printf ("%d ", (d[i]>>j)&1); } //pobitno otobrazhaet dosku
   printf ("\n");
   }
   printf ("\n");
}
void Mark (doska d, unsigned char f) //procedura opredelenija bityx polej
{unsigned char i,
               d1, d2,         // znachenija dlja diagonali
               px=1 <<(f & 7), // Znachenie (koordinata) po Horintali
               py=1+(f >> 3);  // Koordinata po Vertikali

 if (f<64) // Esli na doske to Metit'
 {
  d[py]|=255;   // Sled po Horizontali

  for (i=1; i<=8; i++)
  {d[i]|=px;}       //Sled po Vertikali

  d1=d2=px;
  for (i=py-1; i>=1; i--)
  {d1>>=1; d2<<=1; d[i]|=d2|d1; } //Sled po Diagonaljam vniz

  d1=d2=px;
  for (i=py+1; i<=8; i++)
  {d1>>=1; d2<<=1; d[i]|=d2|d1; } //Sled po Diagonaljam vverx
 }
}

int main(int argc, char* argv[])
{int u=0;
 unsigned char i;

   for (F[1]=0;      F[1]<60; F[1]++)
{  for (F[2]=F[1]+1; F[2]<61; F[2]++)
{  for (F[3]=F[2]+1; F[3]<62; F[3]++)
{  for (F[4]=F[3]+1; F[4]<63; F[4]++)
{  for (F[5]=F[4]+1; F[5]<64; F[5]++)
{
 Clear (D); // Chistim dosku
 Mark (D,F[1]);
 Mark (D,F[2]);
 Mark (D,F[3]);  // Metim bitye polja na doske D
 Mark (D,F[4]);
 Mark (D,F[5]);

// Proverjaem summu vsex polej :
 if (D[1]+D[2]+D[3]+D[4]+D[5]+D[6]+D[7]+D[8]==255*8)
 //Esli vse Bity Doski ustanovleny, to
 {u++; // Uvelichivaem schetchik
   Clear (D1); //ochishaem dosku Ferzej
   for (i=1; i<=5; i++)
   D1[1+(F[i]>>3)]|=(1<<(F[i] & 7)); //Rasstavljaem Ferzej
//  1+(F[i]>>3  - opredeljaet poziciju po vertikali
// 1<<(F[i] & 7) - opredeljaet mestonaxozhdenioe po gorizontali

   Print (D1); // otobrazhenie
   }

  }}}}}

printf ("%d",u);
getch();

        return 0;
}
//---------------------------------------------------------------------------

Решил подробнее остановится на этом фрагменте:

Код


               px=1 <<(f & 7), // Znachenie (koordinata) po Horintali
               py=1+(f >> 3);  // Koordinata po Vertikali

Допустим у нас ферзь стоит на 20-м  (E3)  поле:

ето 3 поле по вертикали :  1+(20>>3) = 3 (D[3])
и  5 поле по горизонтали:  1 <<(20 & 7)  = 16 или  двоичном: 0001 0000, (пятый [по номеру] бит).

  значит его положение на битовой доске  D[3]=16;

Надеюсь, всё понятно. Если нет, спрашивай ... smile

Автор: mes 29.5.2006, 02:40

Цитата(Greeneyed @ 25.5.2006, 20:37

)

чтобы можно было задавать положение первого ферзя.

Не доконца понял, что требуется. Требуется, чтоб можно было задать начальное поле ?

Код


void Proverka (unsigned char f1)
{...
    for (F[1]=f1;      F[1]<60; F[1]++)
....

или жестко зафиксировать позицию одного ферзя ?

В таком случае задаешь цикл для четырех ферзей и проверку на занятость поля 5м ферзем.

Автор: mes 29.5.2006, 12:55

Решил доработать код, вот что получилось :

Код



//---------------------------------------------------------------------------

#pragma hdrstop

//---------------------------------------------------------------------------
#include "stdio.h"
#include"conio.h"
#include "stdlib.h"
#pragma argsused

typedef unsigned char doska[8]; // 8 x 8 BITOV (dlja ekonomii vycheslenij :))
typedef unsigned char ferzi[5];

ferzi F; //Pozicii Ferzej


//------------------------------------------------------------------------------

void Clear (doska d) // ochishenie
{d[1]=d[2]=d[3]=d[4]=d[5]=d[6]=d[7]=d[8]=0;
}

//------------------------------------------------------------------------------

void Print (ferzi F) //otobrazhenie doski na monitore
{  unsigned char i,j;
   doska D;         // doska dlja rasstanovki Ferzej
   Clear (D);       // ochishaem dosku

   for (i=1; i<=5; i++)
   D[1+(F[i]>>3)]|=(1<<(F[i] & 7)); //Rasstavljaem 5 Ferzej

   for (i=8; i>0; i--) //obratnyj otschet dlja pravil'nogo izobrazhenija doski
   {
   for (j=0; j<8; j++)
       { printf ("%d ", (D[i]>>j)&1); } //pobitno otobrazhaet dosku
   printf ("\n");
   }
   printf ("\n");
}

//------------------------------------------------------------------------------

void Mark (doska d, unsigned char f) //procedura opredelenija bityx polej
{unsigned char i,
               d1, d2,         // znachenija dlja diagonali
               px=1 <<(f & 7), // Znachenie (koordinata) po Horintali
               py=1+(f >> 3);  // Koordinata po Vertikali

 if (f<64) // Esli na doske to Metit'
 {
  d[py]|=255;          // Sled po Horizontali

  for (i=1; i<=8; i++)
  {d[i]|=px;}          //Sled po Vertikali

  d1=d2=px;
  for (i=py-1; i>=1; i--)
  {d1>>=1; d2<<=1; d[i]|=d2|d1; } //Sled po Diagonaljam vniz

  d1=d2=px;
  for (i=py+1; i<=8; i++)
  {d1>>=1; d2<<=1; d[i]|=d2|d1; } //Sled po Diagonaljam vverx
 }
}

//------------------------------------------------------------------------------

bool Test (ferzi F)
{  doska d;      // doska dlja proverki bityx polej
 Clear (d);      // Chistim dosku
 Mark (d,F[1]);
 Mark (d,F[2]);
 Mark (d,F[3]);  // Metim bitye polja na doske D
 Mark (d,F[4]);
 Mark (d,F[5]);

// Proverjaem summu vsex polej :
 if (d[1]+d[2]+d[3]+d[4]+d[5]+d[6]+d[7]+d[8]==255*8)
  return true; // vse bity zapolneny
  return false; // kontrol'naja summa ne sovpala
 }

//------------------------------------------------------------------------------

int main(int argc, char* argv[])
{int u=0;
   for (F[1]=0;      F[1]<60; F[1]++)
{  for (F[2]=F[1]+1; F[2]<61; F[2]++)
{  for (F[3]=F[2]+1; F[3]<62; F[3]++)
{  for (F[4]=F[3]+1; F[4]<63; F[4]++)
{  for (F[5]=F[4]+1; F[5]<64; F[5]++)
{
if (Test (F))  //Proverjaem
   {              // Esli vernulos' true
    u++;       // Uvelichivaem schetchik
    Print (F); // Otobrazhaem
  }
}}}}}

 printf ("%d",u);
 getch();

        return 0;
}
//---------------------------------------------------------------------------