Теоретический материал

Задача о расстановке королей

Дана шахматная доска n×m и число k. Нужно посчитать количество способов размещения на этой доске k королей так, чтобы они не били друг друга.

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

Заметим, что снова dij $ \in$ {0, 1}. Отличие этой задачи от предыдущих заключается в следующем. Количество "настоящих" профилей сильно отличается от 2n: если в позиции j есть король, то в позициях j - 1 и j + 1 его заведомо нет. То есть, в двоичной записи профиля не должно встречатся двух подряд идущих единиц. Пусть f (n) -- количество возможных профилей длины n.

Напишем для f (n) рекуррентную формулу. Количество профилей, у которых на n-м месте стоит 1, равно f (n - 2), так как на (n - 1)-м не может стоять 0, на остальные ячейки ограничений нет. Если же на n-м месте стоит 0, то количество будет равно f (n - 1). Тогда f (n) = f (n - 1) + f (n - 2); f (1) = 2, f (2) = 3. Получили, что f (n) -- (n+2)-е число Фибоначчи. Известно, что f (n) < (1, 62)n + 2. При n = 10 имеем f (n) = 144 против количества битовых карт 1 024, уменьшение более чем в 7 раз!

Использовать это наблюдение можно по-разному.

  1. Будем рассматривать только настоящие профили (при вычислении D и A), используя рекурсию: 
    procedure go(len, profile : integer);
begin
    // profile - текущий профиль
    // len = (длина profile) + 1
    
    if (len > n) then begin
        // как только profile получился длины n, выходим
        writeln(profile, ' - настоящий профиль');
        exit;
    end;

    go(len + 1, profile*2);
    // приписать ноль мы всегда можем

    if (profile mod 2 = 0) then 
                 go(len + 1, profile*2 + 1);
    // приписать единицу можно только если рядом ноль
end;

procedure print_all_true_profiles;
begin
  go(1, 0); //запускать надо именно с такими параметрами
end;

  2. Занумеруем все настоящие профили так, чтобы быстро получать по номеру профиль. Тогда чтобы перебрать все настоящие профили, нужно будет пустить цикл по номеру с 1 до их количества f (n), и каждый раз находить профиль по текущему номеру. Например, можно брать номера в лексикографически упорядоченном списке профилей (чтобы сказать, какой из двух профилей больше лексикографически, достаточно сравнить их как числа).

  3. Пусть p -- настоящий ненулевой профиль. Если заменить в нем произвольную единичку (в двоичной записи) на нолик, то получится тоже настоящий профиль. Другими словами, если убрать короля, то ничего плохого не будет. Аналогично, если в p заменить 0 на 1, чтобы не возникло двух подряд идущих единиц, результатом будет настоящий профиль.

    На этом основан еще один способ получения всех настоящих профилей: "поиском в ширину". Из настоящих профилей, в котоых ровно i королей, получаем всевозможные настоящие профили из i + 1 королей. 

    var use : array[0..(1 shl n) - 1] of byte; 
   // use[p] = 1, если p - в очереди
   q : array[1..(1 shl n)] of integer; // очередь
   r : integer; // итоговое количество настоящих профилей

procedure determine_all_true_profiles;
var i, l, x, y : integer;
begin
    l := 0;
    r := 1;
    for i := 1 to (1 shl n) - 1 do use[i] := 0;
    use[0] := 1;
    q[1] := 0;
    while (l < r) do begin
        l := l + 1;
        x := q[l];
        // теперь попробуем подобавлять единички
        for i := 0 to n - 1 do
            if (bit(x,i) = 0) and (bit(x, i - 1) = 0) 
                       and (bit(x, i + 1) = 0) then begin
                y := x + (1 shl i);
                if (use[y] = 0) then begin
                    r := r + 1;
                    q[r] := y;
                end;
            end;
    end;
end;

    После завершения работы процедуры в очереди q будут содержаться все настоящие профили.

В итоге при использовании нашего наблюдения получаем асимптотику O(m(f (n))2)