Алгоритм подсчета кол-ва расстановок 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 является разреженным, за счет чего данный алгоритм можно оптимизировать.

Автор: Жрец

Источник