Pull to refresh

Алгоритм подсчета кол-ва расстановок n ферзей со сложностью меньше чем O(n!)

Пронумеруем строки и столбцы доски размером nxn номерами от 0 до n-1. Номер клетки будет иметь вид (i,j), где i – номер строки, j – номер столбца. Координаты ферзей будут иметь вид (i,p(i)).

Пускай у нас уже расставлены k ферзей в строках от 0 до k-1.

Тогда ферзь с координатами (i,p(i)), где i<k, может бить клетки в строке k с координатами (k,p(i)), (k,p(i)-(k-i)) и (k,p(i)+(k-i)), при этом нас интересуют только клетки с номерами столбцов от 0 до n-1.

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

SV(k)=Sum(i=0..k-1,2^p(i))
SD1(k)=Sum(i=0..k-1,2^p(i) shr (k-i))
Если p(i)-(k-i)<0, то 2^p(i) shr (k-i)=0.
SD2(k)=Sum(i=0..k-1,2^p(i) shl (k-i)) and (2^n-1)
Если p(i)+(k-i)>=n, то 2^p(i) shl (k-i) будет отброшено при помощи and (2^n-1).
S(k)=SV(k) or SD1(k) or SD2(k)

где ^ – возведение в степень, or – побитовое или, and – побитовое и, shl – сдвиг влево, shr – сдвиг вправо.

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

Если записать рекуррентно, то получится

SV(0)=0
SD1(0)=0
SD2(0)=0
SV(k+1)=SV(k) or 2^p(k)
SD1(k+1)=(SD1(k) or 2^p(k)) shr 1
SD2(k+1)=((SD2(k) or 2^p(k)) shl 1) and (2^n-1)

Обратим внимание, что в SD1(k) старший бит всегда равен 0, а в SD2(k) младший бит всегда равен 0, что позволяет при желании дополнительно оптимизировать алгоритм.
Поставить ферзя в клетку (k,p(k)) можно в том и только в том случае, если выполняется условие S(k) and 2^p(k)=0.

На основании этого можно написать такую реализацию оптимизированного перебора:

const
  N = 8;
  Mask = (1 shl N) - 1;

var
  Q: Comp;

procedure Proc(K: Integer; SV, SD1, SD2: Cardinal);
var
  B, S: Cardinal;
  I: Integer;
begin
  if K < N then begin
    S := SV or SD1 or SD2;
    if S = Mask then Exit;
    B := 1;
    for I := 0 to N - 1 do begin
      if S and B = 0 then
        Proc(K + 1, SV or B, (SD1 or B) shr 1, ((SD2 or B) shl 1) and Mask);
      B := B shl 1;
    end;
  end
  else Q := Q + 1;
end;

begin
  Q := 0;
  Proc(0, 0, 0, 0);
  Writeln('Q(', N, ')=', Q:1:0);
  Readln;
end.

Теперь обратим внимание, что для определения того, в какие клетки строки k можно поставить ферзя, достаточно знать SV(k), SD1(k) и SD2(k), в таком случае знать p(0),…,p(k-1) не обязательно. Это означает, что данную задачу можно решить методом динамического программирования, заполнив трехмерный массив, в котором в ячейке V[SV,SD1,SD2] будет храниться кол-во расстановок с соответствующими значениями SV, SD1 и SD2.

Вот программа для подсчета кол-ва расстановок ферзей при помощи динамического программирования:

const
  N = 8;
  PN = 1 shl N;
  Mask = 1 shl N - 1;

var
  B, S: Cardinal;
  I, J, L, M: Cardinal;
  Q: Cardinal;
  V: array[0..PN - 1, 0..PN - 1, 0..PN - 1] of Cardinal;
begin
  FillChar(V, SizeOf(V), 0);
  V[0, 0, 0] := 1;
  for M := 0 to PN - 2 do for I := 0 to PN - 1 do for J := 0 to PN - 1 do
    if V[M, I, J] > 0 then begin
      S := M or I or J;
      if S = Mask then Continue;      
      B := 1;
      for L := 0 to N - 1 do begin
        if S and B = 0 then
          Inc(V[M or B, (I or B) shr 1, ((J or B) shl 1) and Mask], V[M, I, J]);
        B := B shl 1;
      end;
    end;
  Q := 0;
  for I := 0 to PN - 1 do for J := 0 to PN - 1 do
    Inc(Q, V[PN - 1, I, J]);
  Writeln('Q(', N, ')=', Q);
  Readln;
end.

Сложность данного алгоритма не более чем O(n*8^n).

Массив V является разреженным, за счет чего данный алгоритм можно оптимизировать.
Tags:
Hubs:
You can’t comment this publication because its author is not yet a full member of the community. You will be able to contact the author only after he or she has been invited by someone in the community. Until then, author’s username will be hidden by an alias.