Să ne dăm seama ce lucruri noi au fost descoperite în problema reginei. Să ne dăm seama ce este nou în problema reginei: 8 regine pe o tablă de șah

O mare provocare de puzzle este 8 regine pe o tablă de șah. Acest joc a fost inventat în 1848 de celebrul jucător de șah Basel Maxim. Dacă doriți să vă implicați în auto-dezvoltare și să plănuiți să începeți cu șahul, atunci această sarcină va fi un început excelent.

Ideea este de a pune 8 piese, sau mai bine zis matci, astfel incat nici una dintre ele sa nu fie atacata. Merită să ne amintim că regina se poate mișca în orice direcție și în orice număr de pătrate.

Opțiuni pentru rezolvarea problemei

Astăzi există 12 soluții, dar dacă aplicați regulile de simetrie, există până la 92 de opțiuni. Prima soluție la acest puzzle a fost publicată doi ani mai târziu de Franz Nacke. După el, un număr mare de oameni de știință și amatori au încercat să-și găsească propria soluție cum să așezi 8 regine pe o tablă de șah. De exemplu, matematicianul și fizicianul celebru Gauss a găsit 72 de opțiuni pentru plasarea pieselor pe o tablă de șah. Acest număr de opțiuni s-a datorat unei abordări interesante - omul de știință a rotit tabla alternativ cu 90, apoi 180 și 270 de grade. Astfel, obținerea de noi combinații.

Pune 8 regine pe tabla de șah Nu este ușor, dar toată lumea poate găsi cel puțin o soluție corectă aproape imediat. Una dintre cele mai cunoscute soluții este următoarea aranjare a pieselor: h5, f1, d8, b4, g7, e3, c6, a2. Încă trei soluții posibile pot fi observate dacă desfaceți tabla de șah, similar cu soluția lui Gauss.

În timp ce căutați o soluție la acest puzzle, veți putea să exersați gândirea creativă, să vă antrenați atenția și memoria și să vă dezvoltați capacitatea de gândire logică. Aceste abilități vă vor fi utile și vă vor ajuta să găsiți soluții non-triviale la probleme în viitor, fără a utiliza algoritmi standard. Utilizarea raționamentului și a structurilor logice caracteristice în găsirea unei soluții poate deveni trăsătura ta distinctivă tocmai prin rezolvarea unor astfel de puzzle-uri.

Capitolul 8. Problema opt regine

Problema opt regine, ca și problema mutarii cavalerului, este una dintre cele mai faimoase probleme matematice de pe tabla de șah. Dacă problema cavalerilor a fost studiată de Leonhard Euler, problema reginei a atras atenția unui alt mare matematician - Karl Gauss.

În câte moduri pot fi așezate opt regine pe o tablă de șah, astfel încât să nu se amenințe una pe cealaltă, adică să nu fie două pe aceeași verticală, orizontală sau diagonală?

Găsirea unuia sau altui aranjament de matci care să satisfacă condițiile problemei nu este atât de dificilă (patru soluții sunt prezentate în Fig. 43). Este mult mai dificil de calculat numărul total de aranjamente existente; de fapt, aceasta este problema celor opt regine. Este clar că, la fel ca și în cazul turnurilor, este imposibil să plasați mai mult de opt dame pe tabla de șah care nu se atacă între ele. Și, în consecință, pe o tablă n×n este imposibil să plasați mai mult de n dame în modul cerut (în general, problema va fi luată în considerare mai jos).

Orez. 43. Opt regine nu se amenință cu două una pe alta pe tabla de șah

Este curios că mulți autori îi atribuie în mod eronat problema celor opt regine și soluția ei lui Gauss însuși. De fapt, jucătorul de șah german M. Bezzel a fost cel care l-a formulat pentru prima dată în 1848. Dr. F. Nauk (orb de la naștere) a găsit 60 de soluții și le-a publicat în ziarul „Illustrierte Zeitung” din 1 iunie 1850. Abia după aceasta Gauss s-a interesat de problemă și a găsit 72 de soluții, pe care le-a raportat într-o scrisoare către prietenul său astronom Schumacher datat 2 septembrie 1850. Setul complet de decizii, constând din 92 de posturi, a fost primit de același F. Științe (le citat în ziarul menționat din 21 septembrie 1850). Această cronologie a fost stabilită de celebrul cercetător german al divertismentului matematic W. Arens, care a dedicat mult spațiu problemei luate în considerare în cărțile sale.

Dovada că 92 de soluții epuizează toate posibilitățile a fost obținută abia în 1874 de către matematicianul englez D. Glasher (folosind teoria determinanților).

În principiu, plasând opt dame pe tablă în toate modurile posibile, vom găsi până la urmă toate aranjamentele care ni se potrivesc. Totuși, această cale este prea lungă și plictisitoare. Ne putem limita doar la soluții la problema corespunzătoare a turnului și a alege dintre ele pe acelea în care nicio pereche de vile nu se află pe aceeași diagonală. Dar și în acest caz, căutarea este destul de mare (după cum știm, vor fi necesare peste 40.000 de încercări). Astfel, la rezolvarea „manual” a unei probleme (și exact asta s-a făcut în secolul trecut), enumerarea forțată a aranjamentelor trebuie bine gândită. Există multe modalități cunoscute de a organiza o căutare mai mult sau mai puțin rezonabilă a aranjamentului dorit de matci (metode Permentier, La Noe, Gunter, Glasher, Laquiere etc.). Aceste metode sunt descrise în numeroase literaturi despre matematica divertisment (în special în ultimul secol și începutul acestuia). În epoca noastră a computerelor, o problemă de acest gen nu putea trezi un interes atât de aprins. La urma urmei, este suficient să creați un program simplu de calculator - și în câteva minute de la introducerea acestuia în mașină, toate cele 92 de poziții necesare vor fi tipărite.

Din fiecare soluție la problema damei, un număr de altele pot fi obținute prin rotirea tablei în jurul centrului cu 90, 180 și 270° în sensul acelor de ceasornic (o rotație de 360° revine la poziția de pornire). Din acest aranjament de matci, se poate obține una nouă și prin oglindirea tablei în raport cu una dintre liniile punctate din Fig. 43 (poziția I) . De exemplu, din primul aranjament din această figură, când placa este rotită cu 90°, obținem a treia, iar atunci când este reflectată în raport cu linia care separă părțile rege și reginei, obținem a patra. Folosind alte rotații și reflexii, se pot obține încă cinci soluții.

Deci, atunci când tabla este rotită și reflectată, dintr-un aranjament de matci, în general, se obțin șapte noi. S-a dovedit că în cazul general pe o tablă n×n (pentru n > 1) pentru orice aranjament de n matci care nu se amenință reciproc, sunt posibile doar trei situații: a) cu o singură reflectare a tablei un nou se obține aranjament, iar rotațiile și alte reflexii nu sunt nimic nou nu dau; b) se obține o nouă soluție prin rotirea plăcii cu 90°, iar reflexiile dau încă două aranjamente; c) toate cele trei rotații și cele patru reflexii ale tablei au ca rezultat opt ​​formațiuni nepotrivite (inclusiv cea originală).

În cazul a) soluția inițială se numește dublu simetrică, în cazul b) - simetrică, iar în cazul c) - simplă. Pentru o placă obișnuită, fiecare soluție este fie simplă, fie simetrică și nu există soluții dublu simetrice. O interpretare algebrică a soluțiilor fiecărei clase poate fi găsită în Okunev.

Un set (mult) de aranjament de opt matci se numește de bază dacă, în primul rând, acestea nu se transformă una în alta în timpul rotațiilor și reflexiilor tablei și, în al doilea rând, orice alt aranjament se obține dintr-unul de bază folosind aceste transformări. Se știe că fiecare set de soluții de bază ale problemei conține exact 12 poziții (aranjamente de opt matci). Iată unul dintre aceste seturi:

1)	a4, b1, c5, d8, e6, f3, g7, h2;
2)	a4, b2, c5, d8, e6, f1, g3, h7;
3)	a4, b2, c7, d3, e6, f8, g1, b5;
4)	a4, b2, c7, d3, e6, f8, g5, h1;
5)	a3, b5, c2, d8, e6, f4, g7, h1;
6)	a3, b7, c2, d8, e5, f1, g4, h6;
7)	a4, b7, c3, d8, e2, f5, g1. h6;
8)	a6, b4, c2, d8, e5, f7, g1. h3;
9)	a4, b8, c1, d5, e7, f2. g6, h3;
10)	a4, b2, c7, d5. e1. f8. g6, h3;
11)	Poziția 1 în fig. 43;
12)	Poziția a 2-a în fig. 43.

Restul de 80 de poziții sunt obținute din aceste doisprezece ca urmare a rotațiilor și reflexiilor tablei. Primele 11 aranjamente sunt simple, iar doar ultima este simetrică. Astfel, există un total de 11×8 + 1×4 = 92 de aranjamente de opt dame pe tablă care nu se amenință reciproc.

Având în vedere principalele aranjamente, puteți descoperi anumite caracteristici interesante ale acestora. De exemplu, este ușor de observat simetria externă a ultimului aranjament (poziția a 2-a în Fig. 43). Aceasta solutie de baza, unica de acest gen, se caracterizeaza si prin faptul ca doar are partea centrala a tablei (patrat 4x4) fara matci. O altă proprietate a acesteia este că matcile nu ocupă diagonala principală a tablei a1 - h8 (prima soluție principală are și această proprietate).

Primul aranjament din fig. 43 este curios pentru că aici nu stau trei matci pe aceeași linie dreaptă trasată prin centrele câmpurilor (asta înseamnă nu doar verticalele, orizontalele și diagonalele tablei * ci și linii drepte cu alte unghiuri de înclinare).

Orice soluție a problemei poate fi scrisă ca o mulțime (t 1, t 2, ... t 8), care este o permutare a numerelor 1, 2, ..., 8. Aici ti este numărul orizontalei. linia pe care stă regina celei de-a i-a verticale. Deoarece nu există două regine pe aceeași linie orizontală, atunci toate t x sunt diferite și, deoarece reginele nu sunt pe aceeași diagonală, atunci pentru orice i, j (i< j ≤ 8) имеем: |t j - t i | ≠ j - i.

Notarea numerică a plasărilor de matcă este uneori foarte convenabilă. De exemplu, pentru a găsi formațiuni cu o poziție fixă ​​a reginei pe a1, este suficient să le selectați din toate cele 92 de poziții scrise în formă numerică pe cele a căror primă coordonată este egală cu 1. Dacă poziția reginei pe d3 este fixă, atunci ar trebui să selectați poziții în care a patra poziție este numărul 3 etc.

Să scriem mai întâi numerele 1, 2, ..., 8 în ordine crescătoare și apoi în ordine descrescătoare. După aceasta, adăugăm numerele fiecăreia dintre aceste două permutări cu numerele unei permutări arbitrare, de exemplu (3, 7, 2, 8, 5, 1, 4, 6):

+	1,	2,	3,	4,	5,	6,	7,	8		+	8,	7,	6,	5,	4,	3,	2,	1
	3,	7,	2,	8,	5,	1,	4,	6			3,	7,	2,	8,	5,	1,	4,	6
	4,	9,	5,	12,	10,	7,	11,	14			11,	14,	8,	13,	9,	4,	6,	7

Sumele rezultate formează două seturi de numere: (4, 9, 5, 12, 10, 7, 11, 14) și (11, 14, 8, 13, 9, 4, 6, 7). Următoarea problemă apare.

Ce permutări ale numerelor 1, 2,…, 8 au ca rezultat două astfel de mulțimi ca urmare a operației de adunare indicate, în fiecare dintre care toate numerele sunt diferite?

Problema celor opt regine l-a interesat pe Gauss tocmai în legătură cu această problemă pur aritmetică. Se dovedește că există o corespondență unu-la-unu între soluțiile problemei matcă și soluțiile problemei aritmetice descrise. Cu alte cuvinte, fiecare aranjament de opt matci care nu se amenință reciproc oferă o soluție la o problemă aritmetică - și invers. Pentru permutarea aleasă, ambele seturi constau din numere diferite, iar acest lucru nu este întâmplător - corespunde primei poziții din Fig. 43.

Este ușor de observat că la n rotații ale tablei, unele soluții se obțin din altele folosind operații aritmetice simple pe coordonatele pătratelor ocupate de matci. Studiul acestor operații ne permite să descoperim proprietăți suplimentare ale soluțiilor (dintre care unele sunt date de Okunev).

Problema n regine. Puneți n dame pe o tablă de șah n×n astfel încât să nu se amenințe reciproc.

Pe o tablă 1x1, o regină este plasată pe un singur pătrat și există o soluție. Pe o tablă 2x2, o regină, indiferent unde stă, amenință toate pătratele tablei și nu există unde să plaseze o a doua regină. În orice aranjament de trei regine pe o tablă 3x3, cel puțin două dintre ele se amenință reciproc. Deci, pentru n egal cu 2 sau 3, problema nu are soluții.

În ceea ce privește cazurile n > 3, se știe că pe orice tablă n×n este posibil să se aranjeze astfel n dame. ca să nu se amenințe unul pe altul. Multe articole, inclusiv cele din publicații matematice serioase, sunt dedicate dovedirii acestui fapt departe de a fi evident.

Pe o placă 4x4 există un singur aranjament de bază și este dublu simetric (a2, b4, c1, d3), adică există două soluții în total. Pe o tablă 5x5 există două formațiuni principale: 1) a2, b4, c1, d3, e5; 2) a2, b5, c3, d1, e4; Există un total de zece poziții de căutare. Interesant este că puteți alege cinci dintre ele, care, atunci când sunt stivuite una peste alta, vor umple toate pătratele unei table de 5x5 cu 25 de dame. În cazul general, o impunere similară este posibilă numai pentru acelea și care nu sunt divizibile nici cu 2, nici cu 3. Din aceasta, în special, rezultă că pentru o tablă obișnuită este imposibil să se selecteze opt soluții pentru care matcile umplu placa intreaga.

Generalizând proprietatea algebrică de mai sus a soluțiilor la problema celor opt regine, obținem că aranjamentul (t 1, t 2, … t n) n regine pe tabla n × n este cea dorită dacă pentru orice i, j (i< j < n): |t j - t i | ≠ j - i. Здесь по-прежнему t i - номер горизонтали, на которой стоит ферзь i-й вертикали, а набор t 1 , …, t n есть перестановка чисел 1, …, п. Таким образом, для решения задачи в общем случае достаточно найти перестановку чисел 1, …, n, удовлетворяющую указанному условию.

Acum vom descrie o schemă posibilă pentru aranjarea dorită a n regine pe o tablă n×n pentru toate n > 5. Dovada că condiția noastră este satisfăcută în aranjamentul rezultat poate fi găsită, de exemplu, la Okunev sau Yaglomov.

Să luăm în considerare o serie de cazuri secvenţial. Fie n par la început, cu n = 6k sau n = 6k + 4. Așezăm jumătate din toate reginele pe primele n/2 verticale mutând cavalerul, începând de la a doua orizontală și de fiecare dată mutând 2 pătrate în sus și 1. La dreapta. Vom plasa a doua jumatate pe cele n/2 verticale ramase in acelasi mod, dar incepand de la prima orizontala. Pentru o tabla de 6x6 (n = 6k, k = 1) se obtine urmatoarea aranjare a matcilor: a2, b4, c6, d1, e3, f5 (solutia prezentata in Fig. 45 pentru n = 10 se obtine intr-un mod diferit). ).

Când n = 6k + 2 tehnica anterioară nu mai funcționează, iar matcile trebuie plasate într-un mod mai „sprețuitor”. Să le aranjam deplasând cavalerul de pe a doua verticală

(n/2 - 2)-lea, începând de la a treia orizontală și apoi de la

(n/2 + 3)-a verticală de-a lungul (n - 1)-a, începând de la a șasea orizontală. Ca urmare, șase verticale și șase orizontale ale tablei vor rămâne libere, pe care șase regine trebuie să ocupe pătrate cu următoarele coordonate: (1, n - 3), (n/2 - 1, 1); (n/2, n - 1), (n/2 + 1, 2), (n/2 + 2, n), (n, 4). Pentru n = 14 (n = 6k + 2, k = 2) obținem aranjamentul din Fig. 44. Apropo, pe o tablă obișnuită de 8×8 (8 = 6k + 2, k = 1) plasarea a opt matci în acest mod coincide cu aceeași soluție minunată din Fig. 43 (poziţia a 2-a), dar cu greu se poate observa aici un model în aranjamentul matcilor.

Rămâne să luăm în considerare problema valorilor impare ale lui n. Pentru a obține o soluție în acest caz, este suficient să rețineți că în aranjamentul pe care l-am propus pe plăcile „pare”, diagonala principală (mergând din colțul din stânga jos spre dreapta sus) a rămas liberă. Ținând cont de această împrejurare, aranjarea dorită a n regine pe o tablă n×n (pentru n impar) poate fi obținută după cum urmează. Pe verticalele și orizontale ale acestei table cu numere de la 1 la (n - 1) vom plasa (n - 1) dame așa cum se face pe tabla (n - 1)×(n - 1) (n - 1 este chiar!), iar apoi vom plasa a n-a regină în colțul din dreapta sus al tablei. Folosind metoda descrisă, putem obține primul aranjament de matci pe o tablă 5×5 din aranjamentul indicat pe o tablă 4×4, iar din aranjarea matcilor pe o tablă 6×6 avem următoarele pentru n = 7 : a2, b4, c6, d1, e3, f5, g7 .

Orez. 44. Problema despre n matci

Să începem căutarea unui panou cu dimensiunea 4:

Solve(createEmptyBoard(4));

Primesc această matrice înapoi:

Da, asta e soluția. Să încercăm să căutăm o soluție pentru o placă cu dimensiunea 2, funcția ar trebui să returneze false deoarece nu există o soluție pentru această placă:

Solve(createEmptyBoard(2));

// > fals

Da, programul funcționează așa cum ar trebui. Acum să vedem de ce sunt capabile hardware-ul și algoritmul nostru. Să construim un mic test de performanță:

// Test de performanță, // @param (Natural) startSizeOfBoard Mărimea inițială a plăcii // @param (Natural) endSizeOfBoard Dimensiunea finală a plăcii // @return (true) Testul de referință a funcției încheiate(startSizeOfBoard, maxSizeOfBoard)( if(startSizeOfBoard>maxSizeOfBoard)S ( returnează adevărat; )else( console.log("Calculează pentru o placă cu dimensiune:", startSizeOfBoard); var startTime = Date.now(); var solution = solve(createEmptyBoard(startSizeOfBoard)); var endTime = Date.now ( ); console.log("Soluție:", solution.toString());

Primul parametru al acestui test trebuie să fie trecut de dimensiunea inițială a plăcii de interes, iar dimensiunea finală a plăcii trebuie trecută la al doilea parametru. Testul va căuta o soluție pentru plăcile ale căror dimensiuni sunt între dimensiunea inițială transmisă și cea finală. Mărimea de început și de sfârșit sunt incluse în acest interval. De asemenea, va număra timpul în milisecunde pe care l-a petrecut în această căutare.

Iată rezultatele mele pentru plăcile de la 1 la 9 pe un computer MacBook Air (1,8 gigaherți „Intel core i5”, 4 gigaocteți de RAM):

Prin crearea unor astfel de teste și construirea de grafice pe baza datelor lor, putem afla o mulțime de lucruri interesante despre problemă și algoritm. De exemplu, de ce este nevoie de 442 de milisecunde pentru a găsi o soluție pentru o placă cu dimensiunea n=6, dar doar 5 pentru o placă cu dimensiunea n=7? Să ne uităm la soluțiile găsite:

Da, soluția pentru o placă cu dimensiunea n=7 se află chiar în prima ramură a copacului, deoarece regina stă chiar în primul pătrat. Dar cu o placă cu dimensiunea n=6, am avut ghinion și algoritmul a trebuit să dezvăluie mai multe ramuri ale copacului. Se pare că, pe măsură ce dimensiunea plăcii crește, viteza de căutare în algoritmul nostru nu va crește liniar, dar ce s-ar întâmpla dacă sarcina ar fi să găsim toate soluțiile posibile? Gândește-te la asta.

Aceste soluții conțin și un alt model interesant: soluția unei plăci cu 6 celule este, parcă, încorporată în soluția unei plăci cu 7 celule. Cu alte cuvinte, dacă eliminăm primul rând și prima coloană din soluția pentru o placă cu 7 elemente, obținem o soluție pentru o placă cu 6 elemente. E amuzant, am observat asta doar când făceam vizualizarea.

Concluzie

După cum putem vedea din testele de performanță, algoritmul nostru nu este cel mai rapid din lume și nu vă permite să obțineți un răspuns cu o pocnire a degetelor. Dar ceea ce nu i se poate lua este că demonstrează perfect puterea copacilor și recursiunea.

Cu ajutorul arborilor, am organizat o structură simplă și eficientă pentru stocarea datelor noastre, iar recursiunea ne-a ajutat să organizăm convenabil procesarea acestora. Ceea ce îmi place la acest cuplu este faptul că unul se potrivește foarte frumos pe celălalt. Parcă ar fi același lucru, doar prezentat dintr-o perspectivă diferită.

Vom vorbi despre metodele de accelerare a căutărilor în arbore în următoarele articole.

Acum câteva luni am apărut cu o analiză a problemei clasice de a plasa matci pe o tablă de șah (vezi detalii și istoric mai jos). Problema este incredibil de cunoscută și a fost deja examinată la microscop, așa că a fost surprinzător că a apărut ceva cu adevărat nou.

(aici este numărul maxim de matci, iar în locul crucii se poate pune una albă, iar în locul unui punct negru - dar nu ambele deodată; luate din articol)

Modele și complexitatea problemei

A sosit momentul să discutăm efectiv: cum să rezolvi toate acestea și cât de repede se poate face?

Căutare liniară pentru problema clasică

Cel mai interesant punct este că chiar și experții se încurcă uneori și cred că rezolvarea N-reginelor necesită o căutare combinatorie și cred că complexitatea problemei este mai mare decât P. Am scris odată despre ce sunt P și NP pe Habré: și . Cu toate acestea, problema este rezolvată fără să treci peste bord opțiuni! Adică, pentru o tablă de orice dimensiune poți oricând să aranjezi mătcile una în spatele celeilalte scări:

De aici concluzia că pentru N = 1 și N > 3 există întotdeauna o soluție (vezi algo), iar pentru N = 2 sau N = 3
întotdeauna nu (urmează trivial de pe tablă). Aceasta înseamnă că problema de solubilitate pentru N regine (unde trebuie să spuneți dacă există sau nu o soluție) se rezolvă trivial în timp constant (bine, constructiv în timp liniar - aranjați/verificați).

Este timpul să verificați din nou ceea ce ați citit, citim titlul tipic „problema N regine a fost recunoscută ca o problemă NP-completă” - ți-au strălucit ochii?

Cum să numărăm numărul de soluții în practică

Aici începe distracția: numărul de soluții la problema plasării matcii are chiar propriul nume - „secvența A000170”. Acolo se termină vestea bună. Complexitatea problemei: mai mare decât NP și P#, în practică aceasta înseamnă că soluția optimă este descărcarea datelor secvenței într-un dicționar și returnarea numărului dorit. Deoarece pentru N=27 a fost deja calculat pe un cluster paralel pentru câte săptămâni.

Soluţie: scrieți un semn și n cu n, returnați a(n)
n a(n)
1: 1
2: 0
3: 0
4: 2
5: 10
6: 4
7: 40
8: 92
9: 352
10: 724
…
21: 314666222712
22: 2691008701644
23: 24233937684440
24: 227514171973736
25: 2207893435808352
26 22317699616364044
27: 234907967154122528

Cu toate acestea, dacă aveți un fel de problemă dificilă și trebuie totuși să numărați soluțiile (și numărul acestora este necunoscut și nimeni nu le-a numărat înainte), atunci cea mai bună opțiune de prototip este discutată mai jos.

Complementul lui N și programarea setului de răspunsuri

Aici începe distracția: care este noul rezultat al articolului? Problema complementului N regine este NP-complet! (Este interesant că completitudinea NP a complementului pătratului latin era cunoscută încă din 1984.)

Ce înseamnă asta în practică? Cel mai simplu mod de a rezolva această problemă (sau brusc, dacă avem nevoie de o variantă a acesteia) este să folosim SAT. Cu toate acestea, îmi place mai mult următoarea analogie:

SAT este un asamblator pentru probleme combinatorii NP, iar Answer Set Programming (ASP) este C++ (ASP are și un suflet rusesc misterios: este uneori confuz și imprevizibil pentru cei neinițiați; apropo, teoria care stă la baza ASP-ului modern a fost inventată în 1988 de Mikhail Gelfond și Vladimir Lifshits, care au lucrat apoi la universitățile din Texas și, respectiv, Stanford).

Pentru a spune simplu: ASP este un limbaj de programare cu constrângeri declarative (constrângeri în literatura engleză) cu sintaxă Prolog. Adică notăm ce restricții trebuie să satisfacă soluția, iar sistemul reduce totul la varianta SAT și ne găsește o soluție.

Detaliile soluției nu sunt atât de importante aici, iar Answer Set Programming merită o postare separată (care a fost în schița mea de mult timp indecent): deci să ne uităm la punctele conceptuale

% rând de domeniu (1..n). coloana(1..n). % toate diferite 1 ( regina(X,Y): coloana(Y) ) 1:- rând(X). 1 ( regina(X,Y) : rând (X) ) 1:- coloană (Y). % elimină răspunsurile contradictorii:- regina(X1,Y1), regina(X2,Y2), X1< X2, Y1 == Y2. :- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 + X1 == Y2 + X2. :- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 - X1 == Y2 - X2.

Rândul 1 ( regina(X,Y): coloana(Y) ) 1:- rând(X). - se numește o regulă de alegere și determină ce este un spațiu de căutare valid.

Ultimele trei linii se numesc constrângeri de integritate: și definesc ce constrângeri trebuie să le satisfacă soluția: nu poate exista o regină în același rând, nu poate exista o regină în aceeași coloană (omisă din cauza simetriei) și nu poate exista o regină. pe aceeași diagonală.

Recomand Clingo ca sistem de experimentare.
Și pentru început, merită să urmăriți tutorialul lor și să le citiți blogul la www.hakank.org.

Desigur, dacă scrieți în ASP pentru prima dată, atunci primul model nu va fi incredibil de eficient și de rapid, dar cel mai probabil va fi mai rapid decât forța brută cu un return scris în grabă. Cu toate acestea, dacă înțelegeți principiile de bază ale sistemului, ASP poate deveni „regexp pentru probleme NP-complete”.

Să realizăm un experiment numeric simplu cu modelul nostru ASP. Am adăugat 5 matci perfide la model și am căutat o soluție pentru N de la 1 la 150 și iată ce a ieșit (a rulat pe un laptop obișnuit de acasă):

În total, modelul nostru ASP poate găsi soluții la problema complementului pentru N în aproximativ un minut<= 150 (в обычном случае). Это показывает, что система отлично подходит для прототипирования моделей сложных комбинаторных задач.

Concluzii

• Noul rezultat nu este legat de problema clasică a 8 matci, ci de adăugarea problemei generalizate a matcilor (ceea ce este interesant, dar în general logic);
• Complexitatea crește semnificativ, deoarece plasând cu viclenie matci pe tablă, puteți renunța la algoritmul care plasează daenele după un model fix;
• Este imposibil să numărăm efectiv numărul de soluții (bine, deloc; până când se întâmplă ceva groază și P devine egal cu NP etc.);
• Poate că acest rezultat va afecta munca sistemelor SAT moderne, deoarece unii experți consideră că această problemă este oarecum mai simplă decât problemele clasice NP-complete (dar aceasta este doar o opinie)
• Dacă dintr-o dată trebuie să rezolvați o problemă similară dintr-un anumit motiv, cel mai bine este să utilizați sisteme de programare ala Answer Set Programming, special concepute pentru acest scop