Задача о 19 ферзях. Надо раставить 9 чёрных и 10 белых ферзей так что бы чёрные не били белых а белые соотвествено чёрных, автор В. Франген, 1980 г.. Всего извесно 3 решения на доске 8 на 8, требуется написать программу которая находит все варианты. Так же можно найти решения на больших досках N*N. Кому интересно могут попробовать создать прогу. Правда по утверждения одного академика что чисто переборный алгоритм не реален, типа при 1000'000'000 расстановок в сек. не найдёт и через 25000 лет, но по ходу этот акадэмик лопух (с). Задачу эту нашёл в ж. "Наука и Жизнь" №10 1986 г. стр. 108.
Intro переьорное решение требует только самые базовые знания Паскаля или си, вместо этой галиматьи мог бы сразу написать код. А миллиард это 5 минут работы современной персоналки.
Возникло подозрение, что если 20 то ферзей поместить на доску, то некоторые одноцветные будут прятаться за другими? Так можно и 30 штук спытать...
Вариантов расстановки 9 чёрных ферзей на 64-клеточной доске всего 64!/(55!*9!)=2,7540584512e+10. В каждом из них надо проверить наличие хотя бы 10 небитых клеток.
Это интересно! То есть по сути задача не про 20 ферзей, а про 9 ферзей, как их расставить, чтобы 10 клеток были небитыми. Потом в них можно поставить 10 белых и усе...
Booster Не верно, если клетку никто из ферзей не бьет, то и поставленный в нее ферзь никого бить не будет. Доказывается методом "от противного".
Booster фигня имхо, если черный ферзь не бьет белого, то и белый не бьет черного. Не божет быть другого.
Код (Text): b000bb00 bb000b00 bb000000 0b000000 000000ww 00w000ww 00ww000w 00ww0000 При тупом полном переборе первый вариант вылазит уже через несколько секунд, а остальные можете сами поискать =)))
Задачка заинтересовала вас однако, ну ладно вот код на делфи. Код (Text): program Project1; // Задача о 19 ферзях. Надо раставить 9 чёрных и 10 белых ферзей // так что бы чёрные не били белых а белые соотвествено чёрных // Эта программа находит все возможнные варианты сразу исключая перевёрнутые и зеркальные. // Ver 1.1 ;-) {$APPTYPE CONSOLE} uses SysUtils, Windows; const NX: array [1..8] of integer=(-1,0,1,-1,1,-1, 0, 1); NY: array [1..8] of integer=( 1,1,1, 0,0,-1,-1,-1); FerBlack = 10; // Кол чёрных ферзей. FerWhite = 9;// Кол белых ферзей. KonKlet = 63-FerBlack; MaxVar=2000;// максимум растановок var M : array [0..7,0..FerBlack+1] of cardinal; M1,M2 : array [0..7] of cardinal; Bm : array [0..63,0..7] of cardinal; KB : array [0..255] of byte; Pole : array [0..7,0..7] of integer; PoleRes : array [1..MaxVar,0..7,0..7] of integer; Fg : array [0..3] of string; MXY : array [0..FerBlack+1] of integer; i,i1,X,Y,X1,Y1,Nz, XY, XY1, Ot, InitParam, A1 : integer; t, t1, Bt, Br, g, g1: cardinal; A : boolean; Tm1, Tm2, TmSec : Extended; Text : PChar; Str1 : string; Res : TextFile; {Ad, Ad1: pointer; W : THandle; TemplateName : PChar; Par : HWND; DialogFunc : TFarProc; } procedure Init; begin //Ad:=Addr(M1[0]); //Ad1:=Addr(KB[0]); Br:=0;g:=0; Fg[0]:=' ';Fg[1]:='ЫЫ';Fg[2]:='qp';Fg[3]:='db'; for i:=0 to 7 do M[i,1]:=0; for XY:=0 to 63 do begin for i:=0 to 7 do Bm[XY,i]:=0;//Bm[XY,1]:=0; X:=XY div 8;Y:=XY mod 8; for Nz:=1 to 8 do begin X1:=X;Y1:=Y; while not((X1>7) or (X1<0) or (Y1>7) or (Y1<0)) do begin t:=X1;// div 4; t1:=Y1;//+(X1 mod 4)*8; Bt:=1 shl t1; Bm[XY,t]:=Bm[XY,t] or Bt; X1:=X1+NX[Nz]; Y1:=Y1+NY[Nz]; end; //Bm[X*8+Y,t]:=Bm1; end; end; for i:=0 to 255 do begin t1:=i;KB[i]:=0; for i1:=1 to 8 do begin t:=t1 mod 2; t1:=t1 div 2; KB[i]:=KB[i]+(1-t); end; end; end; Procedure Prover; var XY, X1, Y1, k, k1 : integer; NewV : boolean; Label L1; begin XY:=0;//M2[0]:=M1[0]; M2[1]:=M1[1]; for i:=0 to 7 do M2[i]:=M1[i]; for Y:=0 to 7 do begin for X:=0 to 7 do begin t:=XY mod 8; t1:=M2[t] mod 2; M2[t]:=M2[t] div 2; //X1:=XY div 8;Y1:=XY mod 8; Pole[X,Y]:=0; if t1=0 then Pole[X,Y]:=2; inc(XY); end; end; for i:=1 to FerBlack do begin X:=MXY[i] div 8;Y:=MXY[i] mod 8; Pole[X,Y]:=1; end; if g>0 then begin for g1:=1 to g do begin for i:=1 to 7 do begin for Y:=0 to 7 do for X:=0 to 7 do begin case i of 1: begin X1:=Y; Y1:=7-X; end; 2: begin X1:=7-X; Y1:=7-Y; end; 3: begin X1:=7-Y; Y1:=X; end; 4: begin X1:=7-X; Y1:=Y; end; 5: begin X1:=Y; Y1:=X; end; 6: begin X1:=X; Y1:=7-Y; end; 7: begin X1:=7-Y; Y1:=7-X; end; end; if PoleRes[g1,X,Y]<>Pole[X1,Y1] then goto L1; end; //найден зеркальный вариант!!! Exit; L1: // Следущий переворот. end; end; end; inc(g);k1:=1; if g>MaxVar then begin MessageBoxA(0, 'Слишком много вариантов','Ошибка',MB_OK); halt; end; writeln; writeln('Naideno ',g); writeln(' A B C D E F G H'); writeln(Res); writeln(Res,'Найден вариант - ',g); writeln(Res,' A B C D E F G H'); for Y:=7 downto 0 do begin write(Y+1,' '); write(Res,Y+1,' '); for X:=0 to 7 do begin k:=Pole[X,Y]; if k>0 then begin write(Fg[k+1]); write(Res, Fg[k+1]); end else begin write(Fg[k1 mod 2]); write(Res, Fg[k1 mod 2]); end; PoleRes[g,X,Y]:=k; inc(k1); end; writeln; writeln(Res);inc(k1); end; writeln; Tm2:=Time; TmSec:=(Tm2-Tm1)*24*60*60; writeln; writeln(TmSec:6:4,' Sec'); writeln(Res); end; Procedure Nayti(XY,N : Integer); var B1, XY1, M1a : Integer; //B : byte; Label L3; begin for XY1:=XY to KonKlet+N do begin if (Br mod $10000)=0 then write('*'); Inc(Br); MXY[N]:=XY1; B1:=0; for i:=0 to 7 do begin M1a:=M[i,N-1] or Bm[XY1,i]; B1:=B1+KB[M1a]; M1[i]:=M1a; end; if B1>=FerWhite then begin for i:=0 to 7 do M[i,N]:=M1[i]; if N=FerBlack then begin Prover; exit; end; Nayti(XY1+1,N+1); end; end; end; //M1[0]:=M[0,N-1] or Bm[XY,0]; //M1[1]:=M[1,N-1] or Bm[XY,1]; //X:=XY div 8;Y:=XY mod 8; //Pole[X,Y,N]:=1; {KB[0]:=KB[0]; Asm PUSH EAX PUSH EBX PUSH ECX PUSH EDX MOV EDX, 0 //количество бит = 1 MOV ECX, 8 //счётчик MOV EBX, Ad //указатель на масcив М1 L1: MOV EAX, DWORD PTR [EBX] AND EAX, $000000FF //A:=M[Ad] ptr byte ADD EAX, Ad1 MOV AL, BYTE PTR [EAX] //A:=KB[Ad1] AND EAX, $000000FF ADD EDX, EAX INC EBX DEC ECX JNZ L1 MOV B1, EDX POP EDX POP ECX POP EBX POP EAX end; } //M[0,N]:=M1[0];M[1,N]:=M1[1]; //****************************************** begin // Задача о 19 ферзях. Надо раставить 9 чёрных и 10 белых ферзей // так что бы чёрные не били белых а белые соотвественно чёрных. // Эта программа находит все возможнные варианты сразу исключая перевёрнутые и зеркальные. AssignFile(Res,'Resultat.txt'); Rewrite(Res); Text:='Задача о 19 ферзях. Надо раставить 9 чёрных и 10 белых ферзей так '+#10+ 'что бы чёрные не били белых а белые соотвественно чёрных.'+#10+ 'Эта программа находит все возможнные варианты, сразу исключая перевёрнутые и зеркальные.'+#10+ 'Продолжить расчёт?'; write(Text); write(Res, Text); Ot:=MessageBoxA(0,Text,'Задача о 19 ферзях.', MB_YesNo); if Ot=ID_No then exit; Init; Tm1:=Time; Nayti(0,1); Tm2:=Time; TmSec:=(Tm2-Tm1)*24*60*60; writeln; writeln(TmSec:6:4,' Sec'); writeln('Kol variantov - ',Br); writeln('Skorost ',(Br/TmSec):8:0,' variantov/sek'); writeln(DateToStr(Date),' ',TimeToStr(Time)); writeln(Res,'Время ',TmSec:6:4,' сек'); writeln(Res,'Скорость ',(Br/TmSec):8:0,' вариантов/сек'); writeln(Res,'Количество провереных растановок ферзей - ',Br); writeln(Res,DateToStr(Date),' г. ',TimeToStr(Time)); Str1:='Больше решений нет! Время поиска '+FloatToStr(TmSec)+' сек'; MessageBoxA(0, PChar(Str1),'Конец',MB_OK); Close(Res); end. Прога довольно шустрая получилась можно менять количество ферзей, товарищи которые догадались расматривать только черные ферзи совершено правы, резко уменьшается количество переборов. Прога результат сохраняет в файле Resultat.txt, работает шустро 1.5-2.5 сек. Там ещё есть код асм это моя неудачная попытка написать часть функции найти на асме, в прочим она и так достаточно быстро работает, так же прога сама отсекает зеркальные и перевёрнутые варианты. Эту прогу давно написал на зло тому академику.
Intro Чёт по быдлокодерски. Можно сделать соответствие позиций и полей, которые оно бьёт. Когда ставим фигуру, то вычитаем соответствующие поля. Поля можно уместить в 64 битах и применять маски.
Да тут есть команда POPCNT подсчёт количества бит тока как я понимаю это SSE4 по ходу. А у меня на данный момент атлон ХР 2200 был семпрон 2500 (64) но здох. Там всё просто, поле битовое, логически сложивается на маску M1a:=M[i,N-1] or Bm[XY1,i] в маске все варианты битых полей всех позиций ферзя, а потом подсчитавается количество бит B1:=B1+KB[M1a];, это делается по байтно по этому цикл 8 раз, алгоритм рекурсивный, может несколько замороченый но работает же. Если использовать SSE4 с POPCNT то прогу можно резко ускорить, лог. сложил и подсчитал биты которые за пустые т.е. не битые клетки отвечают и далее по рекурсии. Можно сразу в SSE лог сложить 64бит а потом по байтно под считать кол. бит но мне так проще было сделать хотя там ниже видно что я пытался на асемблере так сделать но чота не получилось может надо всю задачу решать на асме но у меня чота плохо сним получается, хотя раньше на Интел8080 проги мог составлять.
>Задачка заинтересовала вас однако, ну ладно вот код на делфи. Ну вы батенька сначала лопушком прикинулись, потом SSE4 вам подавай... Подколоть хотели? Задачу то решил Ваш покорный слуга, а остальные решения легко получаются из этой картинки вручную.
Вот версия 1.3 этой проги коректно расчитывает если ферзей меньше 19, хотя могут быть вылеты если меньше 17 ферзей из-за переполнения массива где хранятся найденые варианты, макс 5000, а так же могут не правельно пустые клетки находится если их больше 2-х, но это врятли. И ещё быстрей работать стала, на атлон ХР 2200 за 0.530-0.560 сек находит в варианте 19 ф. 9+10.
