Problem N kraljica

Kratak uvod

Više informacija o problemu možete pročitati na engleskoj Wikipediji ili u završnom radu [Duni13] na hrvatskom jeziku.

Je li moguće rasporediti osam šahovskih kraljica na šahovsku ploču tako da se kraljice međusobno ne napadaju?

Kraljice napadaju figure koje stoje u istom retku, stupcu ili na dijagonalama. Ispod je jedan od mogućih rasporeda za šahovsku ploču dimenzija 15 × 15. Ni jedna kraljica ne napada drugu. Pitam se kakva je reprezentacija ovog rasporeda u glavi šahovskog grandmajstora?

Rekurzivno pobrojavanje rasporeda N kraljica u Pythonu

Ne zanima me program koji prolazi kroz sve rasporede i broji one koji zadovoljavaju ograničenja.

Ako nam je dan djelomičan raspored, postoji li brz način za otkriti koji su retci, stupci i dijagonale pod napadom?

Ispada da postoji brza provjera. Kraljica na mjestu (i,j) leži na četiri pravca. Vertikalni, horizontalni, y = x + c i y =  − x + c. Uvrštavanjem i i j u x and y dobiju se četiri broja koje možemo iskoristiti za pristupanje elementima niza:

• j = c₁,
• i = c₂,
• i + j = c₃,
• i − j = c₄ .

Program 0

N = int(input())
Y, D1, D2 = [0]*N, [0]*N*2, [0]*N*2
CNT = 0
def place(i: int = 0):
    global CNT
    if i >= N:
        CNT += 1
        return
    for j in range(N):
        if Y[j] + D1[i+j] + D2[i-j]:
            continue
        Y[j]=D1[i+j]=D2[i-j]=1
        place(i+1)
        Y[j]=D1[i+j]=D2[i-j]=0

place()
print(CNT)

Kod iznad ispisuje točne brojeve koji su izlistani u enciklopediji brojevnih nizova OEIS. Izračun broja svih mogućih rasporeda kraljica za N veći od 15 je presporo za moj ukus. Zgodno je to što program uvijek gleda jedan raspored. Nakon pokušaja postavljanja ostatka kraljica – place(i+1), nizovi se mogu resetirati i sljedeći stupac j se može isprobati za novi raspored.

Primijeti da Python niz radi s negativnim indeksom (i-j je negativan broj u mnogo slučajeva).

Ispisivanje svih rasporeda je isto moguće:

Program 0 s ispisivanjem

N = int(input())
Y, D1, D2 = [0]*N, [0]*N*2, [0]*N*2
CNT = 0
S = [['0']*N for _ in range(N)]
def place(i: int = 0):
    if i >= N: 
        global CNT
        CNT += 1
        print('\n'.join(''.join(s) for s in S),
              end='\n\n')
        return
    for j in range(N):
        if Y[j] or D1[i+j] or D2[i-j]: continue
        Y[j]=D1[i+j]=D2[i-j]=1
        S[i][j]='1'
        place(i+1)
        S[i][j]='0'
        Y[j]=D1[i+j]=D2[i-j]=0

place()
print(CNT)

Rekurzivno pobrojavanje rasporeda N kraljica u C++-u

Python je spor. Isti algoritam u C++-u bi mi trebao dati veće brojeve u kraćem vremenu. U vrhovnom poretku stvari (hahaha 🤣), konstantan faktor je zanemariv.

Program 1

#include <bits/stdc++.h>
using namespace std;
int N;
array<int, 40> Y, D1, D2;
int CNT= 0;
main() {
  cin >> N;

  function<void(int)> place= [&](int i) {
    if(i >= N) ++CNT;
    else
      for(int j= 0; j < N; ++j) {
	if(Y[j] + D1[i + j] + D2[i - j + N]) continue;
	Y[j]= D1[i + j]= D2[i - j + N]= 1;
	place(i + 1);
	Y[j]= D1[i + j]= D2[i - j + N]= 0;
      }
  };

  place(0);
  cout << CNT << endl;
}

Program iznad za N = 15 treba ~ 5% vremena Python programa (3.1s / 64.2s). Napisan je prijevodom Python programa, liniju po liniju. Na žalost, negativni index nije podržan stoga je “+ N” stavljen na odgovarajuća mjesta.

Rekurzivno pobrojavanje s bitovima u C++-u

Trenutni svjetski rekord za izračun broja svih mogućih rasporeda je postavljen za N = 27. [PrEn17] Trebalo bi biti moguće koristiti nešto drugo umjesto niza O(N) elemenata jer uopće se ne nadam da mogu postaviti novi rekord s mojim osobnim računalom. U tom slučaju, nule i jedinice stanu u jedan 64-bitni cjelobrojni broj (postoji ~ N × 2 dijagonala)

Umjesto izravnog korištenja bitova Y, D1 i D2, moguće je primijeniti bit trikove za efikasniji kod:

• X & -X daje najmanji postavljeni bit i dozvoljava prelazak preko slobodnih stupaca,
• rotr(D1, c1) dozvoljava označavanje dijagonale za sljedeći redak rotiranjem bitova udesno,
• rotl(D2, c2) dozvoljava označavanje suprotne dijagonale za sljedeći redak rotiranjem bitova ulijevo.

Preporučam čitatelju da pogleda [Rich97] koji primjenjuje trikove na baš ovaj problem, [Warr13] prolazi kroz razne bit trikove u detalje. Detaljna lista trikova je prisutna na ovom linku. Sjećam se da sam koristio trik za pobrojavanje podskupova veličine k u nekom trenutku.

Program 2

#include <bits/stdc++.h>
using namespace std;
using ull= unsigned long long;
ull N;
ull Y, D1, D2;
ull CNT= 0;
main() {
  cin >> N;
  ull ALL= ~(~0 << N);
  Y= D1= D2= ~0;
  Y&= ALL;
  function<void()> place= [&]() {
    if(Y == 0) ++CNT;
    else
      for(ull cols= Y & D1 & D2, c= cols & -cols; cols;
	  cols^= c, c= cols & -cols) {
	ull y= Y, d1= D1, d2= D2;
	Y^= c, D1^= c, D2^= c;
	D1= rotl(D1, 1), D2= rotr(D2, 1);
	place();
	Y= y, D1= d1, D2= d2;
      }
  };

  place();
  cout << CNT << endl;
}

Program iznad za N = 16 treba ~ 30% vremena izvršavanja prvog C++ programa (6.2s / 21.6s). Zgodno poboljšanje. Zanimljivo opažanje, brisanje int i iz argumenata funkcije place smanji vrijeme izvršavanja za jednu sekundu.

Razbijanje simetrije: Nemoj pobrojavati rješenja koja se mogu dobiti zrcaljenjem

Očigledno je da zrcaljenje rasporeda gdje je kraljica u prvoj polovici prvog retka daje nove jedinstvene rasporede. Za neparni N isto vrijedi osim u slučaju kad je kraljica u sredini prvog retka (kao što je slučaj na prvoj slici). U tom slučaju, zrcaljenje rasporeda gdje je kraljica u prvoj polovici drugog retka daje nove jedinstvene rasporede.

U prethodni program možemo uključiti ograničenje polovice retka i skratiti vrijeme izvođenja. Brojač CNT se na kraju mora pomnožiti s 2:

Program 3

#include <bits/stdc++.h>
using namespace std;
using ull= unsigned long long;
ull N;
ull Y, D1, D2;
ull CNT= 0;
ull ALL, MID;

template <bool R> ull init(ull x) { return R ? x & (ALL << (N / 2)) : x; }
template <bool R1= false, bool R2= false> void place() {
  for(ull c, cols= init<R1>(Y & D1 & D2); cols; cols^= c) {
    c= cols & -cols;
    ull y= Y, d1= D1, d2= D2;
    Y^= c, D1^= c, D2^= c;
    D1= rotl(D1, 1), D2= rotr(D2, 1);
    CNT+= Y == 0;
    R2 &&c == MID ? place<true>() : place();
    Y= y, D1= d1, D2= d2;
  }
}

main() {
  cin >> N;
  ALL= ~(~0 << N);
  Y= D1= D2= ~0;
  Y&= ALL;
  MID= 1 << (N / 2);
  N % 2 ? place<true, true>() : place<true>();
  cout << CNT + CNT << endl;
}

Premjestio sam funkciju place i dodao dva template argumenta. Prvi argument R1 označava ograničenje na polovicu prvog retka. Drugi R2 označava ograničenje na polovicu drugog retka ako je kraljica u sredini prvog retka. Za N = 17 ovaj program treba ~ 45% vremena izvršavanja prethodnog C++ programa (19.8s / 43.4s). Ako zamijenim template s običnim provjerama za neparan N i MID, onda se vrijeme izvršavanja poveća za ~ 3%. Micanjem c = cols & -cols iz iterativnog izraza for petlje u tijelo petlje smanji vrijeme izvršavanja za ~ 3%.

Zaključak i daljnja poboljšanja

Prvi sam put pobrojao sve rasporede za N 👸👸🏻👸🏼👸🏽👸🏾👸🏿 prije deset godina, u Scali. Kod je bio spor i zamršen. Nedavno sam se zaželio okušati ponovo i pokušati napisati program koji je jako jednostavan. Zbog toga koristim zareze (za više izraza u liniji), globalne varijable, čudovišnu promjenjivost i ne-ISO C++.

Dodatne simetrije poput rotacije dozvoljavaju smanjenje prostora pretraživanja. To je bio slučaj sa zrcaljenjem gdje se prostor pretraživanja smanjio oko dva puta. Trenutna pretraga ide redak po redak, od prvog do zadnjeg. Takav način pretrage ne može podržati izbjegavanje podstabla pretraživanja koji bi otkrili rotiran raspored.

Izgleda da je pobrojavanje niza A033148 jednostavnije za velike N. Možda je povezano s rješenjima gdje kraljice leže na liniji. Umjesto pobrojavanja, možda je isplativije tražiti najmanji broj kraljica koji napada sve nepopunjene kvadrate šahovske ploče.

Trenutni trend vremena izvršavanja u tablici naslućuje da bi za N = 27 trebalo čekati oko 300 godina za broj rasporeda. Zanimljivo je da broj rasporeda za N = 27 (234907967154122528) stane u 64-bitni cjelobrojni broj. Zbog toga nije potrebno promijeniti kod i koristiti _m128i.

Da bih stranicu učinio još manje zanimljivom za Google Pretraživač dodajem ispod mnoštvo emođija i tablica uz 20 rasporeda za ploču veličine 7 × 7 – izlaz programa 3 (da, HTML izlaz).

Bibliografija