VPF::Задача 12 коней - Форум программистов

Dov

Дата 28.2.2006, 00:43 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: нет
Всего: 88

B3, C3, C4, C6, C7, D6, E3, F2, F3, F5, F6, G6

Код


|*|*|*|*|*|*|*|*|
|*|*|k|*|*|*|*|*|
|*|*|k|k|*|k|k|*|
|*|*|*|*|*|k|*|*|
|*|*|k|*|*|*|*|*|
|*|k|k|*|k|k|*|*|
|*|*|*|*|*|k|*|*|
|*|*|*|*|*|*|*|*|

--------------------

Тут вечности запах томительный,
И свежие фрукты дешевые,
А климат у нас – изумительный,
И только соседи – #уевые.
Игорь Губерман.

mes

Дата 1.3.2006, 00:39 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: нет
Всего: 250

[QUOTE=Dov,27.2.2006, 23:42]

Цитата(esperant0 @ 27.2.2006, 21:24

)

задача не решаема это не сложно доказать.
для того чтобы закрыть четыре четверки, состоящии из четырех угловых клеток нужно 16 коней

Решение у этой задачи есть. Если расставить три коня так что они бьют все четыре угловые клетки, то из 3х возможных вариантов,два (зеркальных) являются решением. При заполнение трех оставшихся углов нужно учитывая правило поворота, расставить коней в те же позиции.
Сейчас нет времени для более подробного обяснения. smile

Попозже постараюсь более подробно.

--------------------

http://opendots.net

esperant0

Дата 1.3.2006, 02:32 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 714
Регистрация: 20.5.2005

Репутация: 4
Всего: 14

да промазал я. smile

--------------------

Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer

Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором а затем стерто и которое он - пользователь не мог видеть.

proger

Дата 1.3.2006, 08:56 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 400
Регистрация: 10.10.2004

Репутация: нет
Всего: 1

Dov,
Вот теперь прогу надо написать, которая так раставит!
Добавлено @ 08:58
Dov,
У тебя не все клетки под ударом!

mes

Дата 1.3.2006, 09:47 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: нет
Всего: 250

Цитата(proger @ 1.3.2006, 08:56

)

Dov,
У тебя не все клетки под ударом!

интересно какие?? smile

--------------------

http://opendots.net

mes

Дата 1.3.2006, 10:06 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: нет
Всего: 250

Алгоритм программы такой:
1. Раставляешь коней (любое кол-во) так, чтобы 4 угловые клетки
во всех 4-х углах были биты.
Получится следуещее:
Потом убираешь последователно в каждом углу одного "лишнего" ( того, при убирании которого, все клетки всего поля будут биты)

Код


|*|*|*|*|*|*|*|*|
|*|*|k|*|*|k|*|*|
|*|k|k|k|k|k|k|*|
|*|*|k|*|*|k|*|*|
|*|*|k|*|*|k|*|*|
|*|k|k|k|k|k|k|*|
|*|*|k|*|*|k|*|*|
|*|*|*|*|*|*|*|*|

В конце концов получится "рисунок" как у Dova
При таком алгоритме кол-во проверок минимально (в удачном случае находит решение после 8 хода, при неудачном с 20 хода)

--------------------

http://opendots.net

Dov

Дата 1.3.2006, 15:19 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: нет
Всего: 88

Цитата(proger @ 1.3.2006, 07:56

)

Dov,
У тебя не все клетки под ударом!

Конечно, не все. На некоторых 'лошади' стоят(8 штук). Если хочешь поставить их под бой тоже, прийдётся добавить ущё 2 коника.

Цитата(proger @ 1.3.2006, 07:56

)

Dov,
Вот теперь прогу надо написать, которая так раставит!

Ну, так дерзай, proger. Видишь, и ник у тебя подходящий. smile

--------------------

ДобренькийПапаша

Дата 1.3.2006, 19:31 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1278
Регистрация: 14.1.2006
Где: г.Москва

Репутация: нет
Всего: 7

Proger, я написал прогу, там на первой странице. Если немного не так, тогда подправь.

--------------------

Меня зовут Себастьян Парейра, торговец чёрным деревом.

Dov

Дата 1.3.2006, 22:40 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: нет
Всего: 88

Цитата(ДобренькийПапаша @ 1.3.2006, 18:31

)

Proger, я написал прогу...

Цитата

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
БАРНАУЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ
РАССТАНОВКА ШАХМАТНЫХ ФИГУР
Составитель А.К. Сахаров

ДобренькийПапаша, плагиатом занимаешься, нехорошо. А может быть тебя зовут А.К.Сахаров из Барнаула?

--------------------

proger

Дата 2.3.2006, 08:16 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 400
Регистрация: 10.10.2004

Репутация: нет
Всего: 1

Dov, Спасибо за помощь!

proger

Дата 6.3.2006, 11:29 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 400
Регистрация: 10.10.2004

Репутация: нет
Всего: 1

mes, А прогу нАПИСАТЬ МОЖЕШЬ, А ТО У МЕНЯ НЕ ПОЛУЧАЕТСЯ!

Dov

Дата 8.3.2006, 01:39 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: нет
Всего: 88

proger, вот, тупо перевёл на С++ ту прогу, которая на паскале.
Видок у неё ещё тот, но зато работает. А красоту сам наведёш, если захочешь.

Код

#include <iostream.h>
#include <iomanip.h>
#include <string.h>

int w[4][16]={{ 1, 2, 3, 4, 9,10,11,12,17,18,19,20,25,26,27,28}, 
              { 8,16,24,32, 7,15,23,31, 6,14,22,30, 5,13,21,29}, 
              {64,63,62,61,56,55,54,53,48,47,46,45,40,39,38,37}, 
              {57,49,41,33,58,50,42,34,59,51,43,35,60,52,44,36}}; 
 
int  u[9] = {0, -2, -2,  2, 2, 1,  1, -1, -1};
int  v[9] = {0,  1, -1, -1, 1, 2, -2, -2,  2};
int  a[12] = {0};
int  a1[3] = {0};
int  c[8][8];
char c0[8][8]; 
int  i, j, t, m = 0, p = 0; 
   
void PRINT() 
{ 
    int k = 0;
   
    for(i = 0; i < 4; i++)//{ переписываем в массив A значения клеток с конями } 
    {  
        for(j = 0; j < 3; j++) 
        {
            a[k] = w[i][a1[j]]; 
            cout << setw(3) << a[k++];           
        } 
    }

    cout << " -(" << ++m << ")" << endl;

    for(j = 0; j < 8; j++)
        memset(c0[j], '.', sizeof(c0[j]));  //{ все c0[i,j]='.'} 

    for( k = 0; k < 12; k++)
    {
        i = (a[k] - 1) / 8; 
        j = (a[k] - 1) % 8; 
        c0[i][j] = 'X'; 
    }

    for(i = 0; i < 8; i++) 
    { 
        for( j = 0; j < 8; j++)
             cout << setw(3) << c0[i][j]; 
        cout << endl; 
    }

    cout << endl; 
}

//  { ставим (d=1) или снимаем (d=-1) 4 K-го коня } 
void KON(int k, int d)
{    
    for(int k1 = 0; k1 < 4; k1++)
    {    
        int ik = (w[k1][a1[k]] - 1) / 8; 
        int jk = (w[k1][a1[k]] - 1) % 8;
        
        for(int z = 0; z < 9; z++) 
        { 
            int i = ik + u[z];
            int j = jk + v[z];
            
            if(i >= 0 && i < 8 && j >= 0 && j < 8) 
            { 
                  c[i][j] += d; 
                  if(d == 1)
                      if(c[i][j] == 1)
                          p++;
                  if(d == -1)
                      if(c[i][j] == 0)
                          p--;               
            } 
        } 
    }
}

void CNK(int k, int L, int R) 
{ 
    for(int j = L; j < R; j++)
    { 
         a1[k] = j; 
         KON(k, 1); 
         if(k < 2)
             CNK(k + 1, j + 1, R + 1); 
         else if(p == 64)
             PRINT(); 
         KON(k, -1); 
    } 
}


void main()
{
    CNK(0, 1, 13); 
    cout << "*** END ***" << endl; 
    cin.get();
}

--------------------

mes

Дата 9.3.2006, 18:32 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: нет
Всего: 250

Цитата(proger @ 6.3.2006, 11:29

)

mes, А прогу нАПИСАТЬ МОЖЕШЬ, А ТО У МЕНЯ НЕ ПОЛУЧАЕТСЯ!

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

Чтоб проверять только те позиции, которые имеет смысл, я разбил задачу на две части.
Первая: Как известно конь не может бить угловые клетки в разных углах. Таких клеток 16. (4*4)
Вопрос: Могут ли бить 12 коней ети 16 клеток?

Каждая клетка может бить "бита" не более чем с девяти позиций: (8 битых +1 когда клетка занята конём)
Конь может бить две соседние клетки, только если они рассположены по диагонали

Код




program konA;

{$APPTYPE CONSOLE}
uses
  SysUtils,
  windows;

TYPE Tkletka = record v: 'A'..'H';
                      h: '1'..'8';
                      end;
     TKonPos = array[0..8] of byte;

const UgolKletka: array[0..3] of array [0..3] of Tkletka =
  (((v:'A';h:'1'),(v:'A';h:'2'),
    (v:'B';h:'1'),(v:'B';h:'2')),

   ((v:'H';h:'1'),(v:'H';h:'2'),
    (v:'G';h:'1'),(v:'G';h:'2')),

   ((v:'A';h:'8'),(v:'A';h:'7'),
    (v:'B';h:'8'),(v:'B';h:'7')),

   ((v:'H';h:'8'),(v:'H';h:'7'),
    (v:'G';h:'8'),(v:'G';h:'7')));

var Kon: array [0..5] of record pos:TKonPos end;
   Reslt: record kol:byte;
          Kon: array [0..3] of record pos:TKonPos end;
          end;

  i,j:integer;
  n:byte;

function KletkaToByte (nkletka:Tkletka):byte;
begin
Result := (byte(nkletka.v)-byte('A')) shl 3 +(byte(nkletka.h)-byte('1'));
end;

{Проверка горизонтали и вертикали: если на доске, то определяет порядковый номер;}
function NaDoske(v,h:byte; var Nummer:byte):boolean;
 begin
  if (v<8) and (h<8)
  then begin
        Nummer := (v shl 3)+h;
        Result:=True;
      end
      else  Result :=False;
   end;

function Kletka (v,h:Char):Tkletka;
begin
Result.v:=v;
Result.h:=h;
end;

function ByteToKletka(num:byte):Tkletka;
begin
Result.v:=char(byte('A')+((num shr 3) and 7));
Result.h:=char(byte('1')+ (num and 7));
end;

{Преоброзавание в строку "легальных" позиций}
Function KonPosToStr (KonPos:TKonPos):string;
var i:integer;
    s:string;
    kl:Tkletka;
begin
s:='';
For i:=0 to 8 do
 if KonPos[i]<64 then begin kl:=ByteTokletka(KonPos[i]);
  s:=s+' '+kl.v+':'+kl.h+';';
end;
Result:=S;
end;

 {Перебор возможных вариантов конём}
Procedure FindBitoePole (Kletka:Tkletka; out KonPos:TKonPos);
 v,v1,h,h1: byte;
 n:byte;
begin
 v:= (byte(kletka.v)-byte('A')); 
 h:= (byte(kletka.h)-byte('1'));

n:=0;

   if    not(NaDoske (byte(v-2),byte(h-1),KonPos[n]))  
   then  KonPos[n]:=$FF; Inc(n);

   if    not(NaDoske(byte(v-2),byte(h+1),KonPos[n]))
   then  KonPos[n]:=$FF; Inc(n);

   if    not(NaDoske(byte(v-1),byte(h-2),KonPos[n]))
   then  KonPos[n]:=$FF; Inc(n);

   if    not(NaDoske(byte(v-1),byte(h+2),KonPos[n]))
   then  KonPos[n]:=$FF; Inc(n);

   if    not(NaDoske(byte(v+2),byte(h-1),KonPos[n]))
   then  KonPos[n]:=$FF; Inc(n);

   if    not(NaDoske(byte(v+2),byte(h+1),KonPos[n]))
   then  KonPos[n]:=$FF; Inc(n);

   if    not(NaDoske(byte(v+1),byte(h-2),KonPos[n]))
   then  KonPos[n]:=$FF; Inc(n);

   if    not(NaDoske(byte(v+1),byte(h+2),KonPos[n]))
   then  KonPos[n]:=$FF; Inc(n);

   NaDoske (v,h,KonPos[n]);
   end;

function IsKonDljaDvux (KonPos1, KonPos2:TKonPos; out KonPos:TKonPos):byte;
var i,j:integer;
    n:byte;
    test:boolean;
begin
n:=0;
  for  i:=0 to 8 do
   begin
     test:=False;
        for j:=0 to 8 do
        if  (KonPos1[i] = KonPos2[j]) and ((KonPos1[i] or KonPos2[j])<64)
        then test:=True;

      if test then
      begin
         KonPos[i]:=KonPos1[i]; Inc (n)
         end
      else KonPos[i]:=$FF;
    end;
Result:=n;
end;




begin
  n:=1; {Номер текущего коня}
  for j:=0 to 3 do {Проверить четыре угла}
  begin
  writeln ('Ugol ',j+1);
  for i:=0 to 3 do
  FindBitoePole (UgolKletka[j][i], Kon[i].pos); {Определить поля, с которых клетка бита} 

  if   IsKonDljaDvux (Kon[0].pos, Kon[3].pos, kon[4].pos)>0 {Проверить диагональные клетки на совпадение}
  then writeln ('Kon ',n,':  ',KonPosToStr (kon[4].pos)) {Если совпадают, то распечатать только совпадающие позиции}
  else
   begin
       writeln ('Kon ',n,':  ',KonPosToStr (kon[0].pos)); Inc(n); {Иначе все возмозные}
       writeln ('Kon ',n,':  ',KonPosToStr (kon[3].pos));

  end;
  Inc(n);

  if  IsKonDljaDvux (Kon[1].pos, Kon[2].pos, kon[5].pos)>0 {Проверить другие диагональные клетки на совпадение}
  then writeln ('Kon ',n,':  ',KonPosToStr (kon[5].pos)) {Если совпадают, то распечатать только совпадающие позиции}
  else begin
       writeln ('Kon ',n,':  ',KonPosToStr (kon[1].pos)); Inc(n);{Иначе все возмозные}
       writeln ('Kon ',n,':  ',KonPosToStr (kon[2].pos));
  end;
  Inc(n);
       writeln ;
end;

MessageBox (0,'','',0); {поставил для паузы}

end.

// Код конечно  нуждается в доработке (написан на скорую руку). :)

По результату программы видно, что минимальное кол-во коней для перекрытия угловых клеток нужно 12 (нас это устраивает)
4 Коня имеют 5 позиций,
другие 4 - 3позиции,
и еше 4 Коня могут находится только в 1 положении, значит расставлять нужно только 8 коней.

На основе етих данных я создал, список позиций, и методом перебора проверил есть ли среди вариантов такие,
которые бы били бы все клетки.

Код




program konB;

{$APPTYPE CONSOLE}

uses windows,
  SysUtils;

TYPE Tkletka = record v: 'A'..'H';
                      h: '1'..'8';
                      end;
const Kon1 : Array [0..3] of array [0..4] of tkletka =

(((v:'A'; h:'4'),(v:'D'; h:'1'),(v:'D';h:'3'),(v:'C'; h:'4'),(v:'B'; h:'2')),
 ((v:'E'; h:'1'),(v:'E'; h:'3'),(v:'F';h:'4'),(v:'H'; h:'4'),(v:'G'; h:'2')),
 ((v:'A'; h:'5'),(v:'D'; h:'6'),(v:'D';h:'8'),(v:'C'; h:'5'),(v:'B'; h:'7')),
 ((v:'E'; h:'6'),(v:'E'; h:'8'),(v:'F';h:'5'),(v:'H'; h:'5'),(v:'G'; h:'7')));

     Kon2 : Array [0..3] of array [0..2] of tkletka =
 (((v:'C';h:'2'),(v:'B'; h:'3'),(v:'A'; h:'1')),
  ((v:'F';h:'2'),(v:'G'; h:'3'),(v:'H'; h:'1')),
  ((v:'C';h:'7'),(v:'B'; h:'6'),(v:'A'; h:'8')),
  ((v:'F';h:'7'),(v:'G'; h:'6'),(v:'H'; h:'8')));

         Kon3 : Array [0..3] of tkletka =
 ((v:'C';h:'3'),(v:'F'; h:'3'),(v:'C'; h:'6'),(v:'F';h:'6'));
var n,i,j,i1,i2,i3,i4,i5,i6,i7,i8:integer;
desk: array[0..63] of byte;

function NaDoske(v,h:byte; var Nummer:byte):boolean;
 begin
  if (v<8) and (h<8)
  then begin
        Nummer := (v shl 3)+h;
        Result:=True;
      end
      else Result :=False;
   end;

procedure MarkBitye (var Desk:array of byte; konPos:tkletka);
var
 v,v1,h,h1: byte;
 n:byte;
begin
 v:= (byte(KonPos.v)-byte('A'));
 h:= (byte(KonPos.h)-byte('1'));



   if    NaDoske (byte(v-2),byte(h-1),n)
   then  Desk[n]:= Desk[n] or 1;

   if    NaDoske(byte(v-2),byte(h+1),n)
   then  Desk[n]:= Desk[n] or 1;

   if    NaDoske(byte(v-1),byte(h-2),n)
   then  Desk[n]:= Desk[n] or 1;

   if    NaDoske(byte(v-1),byte(h+2),n)
   then  Desk[n]:= Desk[n] or 1;

   if    NaDoske(byte(v+2),byte(h-1),n)
   then  Desk[n]:= Desk[n] or 1;

   if    NaDoske(byte(v+2),byte(h+1),n)
   then  Desk[n]:= Desk[n] or 1;

   if    NaDoske(byte(v+1),byte(h-2),n)
   then  Desk[n]:= Desk[n] or 1;

   if    NaDoske(byte(v+1),byte(h+2),n)
   then  Desk[n]:= Desk[n] or 1;

   NaDoske (v,h,n);
   Desk[n]:= $FF; {$FF - место занятое конём
                               1- битое поле; 
                               or 1-  используется для того, чтоб не перемаркировать поле помеченное конём}
end;
function Pustye (var desk:array of byte):boolean;
var i:integer;
begin
Result:=false;
for i:=0 to 63 do if desk[i] = 0 then Result:=true;
end;


begin
 for i1:=0 to 4 do
 for i2:=0 to 4 do
 for i3:=0 to 4 do
 for i4:=0 to 4 do
 for i5:=0 to 2 do
 for i6:=0 to 2 do
 for i7:=0 to 2 do
 for i8:=0 to 2 do
 begin
 FillChar(desk,Sizeof(desk),0);

  MarkBitye(desk,Kon1[0,i1]);
  MarkBitye(desk,Kon1[1,i2]);
  MarkBitye(desk,Kon1[2,i3]);
  MarkBitye(desk,Kon1[3,i4]);

  MarkBitye(desk,Kon2[0,i5]);
  MarkBitye(desk,Kon2[1,i6]);
  MarkBitye(desk,Kon2[2,i7]);
  MarkBitye(desk,Kon2[3,i8]);

  MarkBitye(desk,Kon3[0]);
  MarkBitye(desk,Kon3[1]);
  MarkBitye(desk,Kon3[2]);
  MarkBitye(desk,Kon3[3]);

  if not(Pustye (desk)) then

  begin
    for i:=0 to 7 do
     begin
     writeln;
      for j:=0 to 7 do
      if desk[i*8+j]=1 then write('* ') else write ('K ');
     end;
  end;
 end;

В результате два варианта (зеркальных) где группа из трех коней, симметрична относительно поворота.
При проверке во второй части перебираются 50625 позиций.

Если учитывать симметрию относительно поворота, (т.е для одного угла) , то сократится приблизительно до 15 позиций.

Надеюсь тебе ето поможет. smile

P.S. Прошу прощение за малое кол-во комментариев и неформатированный код. smile

Это сообщение отредактировал(а) mes - 9.3.2006, 18:37

Присоединённый файл ( Кол-во скачиваний: 29 )

Koni.zip 46,76 Kb

--------------------

http://opendots.net

proger

Дата 11.3.2006, 14:14 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 400
Регистрация: 10.10.2004

Репутация: нет
Всего: 1

Спасибо!

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »