Poglavlje 8. Problem osam kraljica

Problem osam kraljica, kao i problem pokreta viteza, jedan je od najpoznatijih matematičkih problema na svijetu. šahovska tabla. Ako je problem viteza proučavao Leonhard Euler, problem kraljice privukao je pažnju još jednog velikog matematičara - Karla Gausa.

Na koliko načina se osam dama može postaviti na šahovsku ploču tako da ne prijete jedna drugoj, odnosno da dvije ne budu na istoj vertikali, horizontali ili dijagonali?

Pronalaženje jednog ili drugog rasporeda matica koji zadovoljava uslove problema nije tako teško (četiri rješenja prikazana su na slici 43). Mnogo je teže izračunati ukupan broj postojećih aranžmana; u stvari, ovo je problem osam kraljica. Jasno je da je, kao i u slučaju topova, nemoguće postaviti više od osam dama na šahovsku tablu koje se međusobno ne napadaju. I, shodno tome, na n×n tablu je nemoguće postaviti više od n dama na potreban način (u opšti pogled problem će biti razmotren u nastavku).

Rice. 43. Osam dama ne prijete dvije jedna drugoj na šahovskoj tabli

Zanimljivo je da mnogi autori problem osam kraljica i njegovo rješenje greškom pripisuju samom Gausu. Zapravo, njemački šahist M. Bezzel je prvi to formulisao 1848. godine. Dr F. Nauk (slijep od rođenja) pronašao je 60 rješenja i objavio ih u listu “Illustrierte Zeitung” od 1. juna 1850. Tek nakon toga Gauss se zainteresovao za problem i pronašao 72 rješenja, o čemu je izvijestio u pismu njegov prijatelj astronom Šumaher od 2. septembra 1850. Cijeli set odluka, koji se sastoji od 92 stava, primio je isti F. Sciences (citirao ih je u pomenutim novinama od 21. septembra 1850.). Ovu hronologiju je uspostavio poznati njemački istraživač matematičke zabave W. Arens, koji je u svojim knjigama posvetio dosta prostora problemu koji se razmatra.

Dokaz da 92 rješenja iscrpljuju sve mogućnosti dobio je tek 1874. engleski matematičar D. Glasher (koristeći teoriju determinanti).

U principu, postavljanjem osam dama na tablu na svaki mogući način, na kraju ćemo pronaći sve aranžmane koji nam odgovaraju. Međutim, ovaj put je predug i dosadan. Možemo se ograničiti samo na rješenja odgovarajućeg problema topa i među njima odabrati ona u kojima nijedan par topova nije na istoj dijagonali. Ali čak i u ovom slučaju potraga je prilično velika (kao što znamo, biće potrebno više od 40.000 pokušaja). Dakle, kada se problem rješava „ručno” (a to je upravo ono što se radilo u prošlom vijeku), prisilno nabrajanje aranžmana mora biti dobro osmišljeno. Postoji mnogo poznatih načina da se organizuje manje-više razumna potraga za željenim rasporedom matica (metode Permentier, La Noe, Gunter, Glasher, Laquiere, itd.). Ove metode su opisane u brojnoj literaturi o zabavna matematika(uglavnom u prošlom vijeku i početkom ovog). U naše doba kompjutera, problem ove vrste ne bi mogao izazvati tako veliko interesovanje. Na kraju krajeva, dovoljno je napraviti jednostavan kompjuterski program - i u roku od nekoliko minuta nakon njegovog uvođenja u mašinu, sve 92 potrebne pozicije će biti odštampane.

Od svakog rješenja za problem dame može se dobiti niz drugih rotirajući dasku oko centra za 90, 180 i 270° u smjeru kazaljke na satu (rotacija za 360° se vraća u početnu poziciju). Iz ovog rasporeda matica, novi se može dobiti i preslikavanjem ploče u odnosu na jednu od isprekidanih linija na sl. 43 (1. pozicija) . Na primjer, iz prvog rasporeda na ovoj slici, kada se daska zarotira za 90°, dobijamo treću, a kada se reflektira u odnosu na liniju koja razdvaja kraljevu i damu, dobijamo četvrtu. Koristeći druge rotacije i refleksije, može se dobiti još pet rješenja.

Dakle, kada se daska okrene i reflektuje, iz jednog rasporeda dama, generalno govoreći, dobije se sedam novih. Dokazano je da su u općem slučaju na n×n dasci (za n > 1) za bilo koji raspored od n dama koje ne prijete jedna drugoj moguće samo tri situacije: a) s jednim odrazom daske novi raspored se dobija, a rotacije i druge refleksije ništa novo ne daju; b) novo rješenje se dobija rotacijom ploče za 90°, a refleksije daju još dva rasporeda; c) sve tri rotacije i četiri refleksije daske rezultiraju osam neusklađenih formacija (uključujući i onu originalnu).

U slučaju a) originalno rješenje se naziva dvostruko simetrično, u slučaju b) - simetrično, au slučaju c) - jednostavno. Za običnu ploču svako rješenje je jednostavno ili simetrično, a dvostruko simetričnih rješenja nema. Algebarsko tumačenje rješenja svake klase može se naći u Okunevu.

Skup (skup) rasporeda od osam dama naziva se osnovnim ako se, prvo, ne transformišu jedna u drugu tokom rotacija i odraza daske, a drugo, bilo koji drugi raspored se dobije iz nekog osnovnog pomoću ovih transformacija. Poznato je da svaki skup osnovnih rješenja problema sadrži tačno 12 pozicija (aranžmana osam matica). Evo jednog od ovih setova:

Preostalih 80 pozicija dobijeno je od ovih dvanaest kao rezultat rotacije i refleksije ploče. Prvih 11 aranžmana je jednostavnih, a samo posljednji je simetričan. Dakle, na tabli ima ukupno 11×8 + 1×4 = 92 rasporeda po osam dama koji se međusobno ne ugrožavaju.

S obzirom na glavne aranžmane, možete otkriti neke njihove zanimljive karakteristike. Na primjer, lako je uočiti vanjsku simetriju posljednjeg rasporeda (2. pozicija na sl. 43). Ovo osnovno rješenje, jedino takve vrste, karakterizira i činjenica da jedino ima središnji dio ploče (4x4 kvadrat) bez dama. Još jedno njegovo svojstvo je da dame ne zauzimaju glavnu dijagonalu table a1 - h8 (ovo svojstvo ima i prvo glavno rješenje).

Prvi raspored na sl. 43 je zanimljivo jer ovdje ne stoje tri dame na istoj pravoj liniji povučenoj kroz centre polja (to znači ne samo vertikale, horizontale i dijagonale daske * već i prave linije s drugim uglovima nagiba).

Bilo koje rješenje problema može se zapisati kao skup (t 1, t 2, ... t 8), koji je permutacija brojeva 1, 2, ..., 8. Ovdje je ti broj horizontale linija na kojoj stoji kraljica i-te vertikale. Pošto nema dve dame na istoj horizontalnoj liniji, onda su svi t x različiti, a pošto dame nisu na istoj dijagonali, onda za bilo koje i, j (i< j ≤ 8) имеем: |t j - t i | ≠ j - i.

Numerička notacija položaja matice je ponekad vrlo zgodna. Na primjer, da bi se pronašle formacije sa fiksnom pozicijom dame na a1, dovoljno je od svih 92 pozicije zapisane u numeričkom obliku izabrati one čija je prva koordinata jednaka 1. Ako je pozicija dame na d3 fiksna, tada trebate odabrati pozicije gdje je četvrta pozicija broj 3, itd.

Napišimo brojeve 1, 2, ..., 8 prvo rastućim redoslijedom, a zatim opadajućem. Nakon toga dodajemo brojeve svake od ove dvije permutacije s brojevima proizvoljne permutacije, na primjer (3, 7, 2, 8, 5, 1, 4, 6):

Rezultirajući zbrojevi čine dva skupa brojeva: (4, 9, 5, 12, 10, 7, 11, 14) i (11, 14, 8, 13, 9, 4, 6, 7). Pojavljuje se sljedeći problem.

Koje permutacije brojeva 1, 2,…, 8 rezultiraju u dva takva skupa kao rezultat naznačene operacije sabiranja, u svakom od kojih su svi brojevi različiti?

Problem osam kraljica zanimao je Gaussa upravo u vezi sa ovim čisto aritmetičkim problemom. Ispostavilo se da postoji korespondencija jedan-na-jedan između rješenja problema kraljice i rješenja opisanog aritmetičkog problema. Drugim riječima, svaki raspored od osam kraljica koji ne prijete jedna drugoj daje rješenje aritmetičkog problema - i obrnuto. Za odabranu permutaciju, oba skupa se sastoje od različitih brojeva, i to nije slučajno - odgovara prvoj poziciji na Sl. 43.

Lako je vidjeti da se s n rotacija ploče neka rješenja dobivaju od drugih koristeći jednostavne aritmetičke operacije na koordinatama kvadrata koje zauzimaju dame. Proučavanje ovih operacija nam omogućava da otkrijemo dodatna svojstva rješenja (od kojih neka daje Okunev).

Problem n kraljica. Stavite n dama na n×n šahovsku ploču tako da ne prijete jedna drugoj.

Na ploči 1x1, jedna dama je postavljena na jedno polje i rješenje postoji. Na tabli 2x2, jedna dama, bez obzira gdje stoji, prijeti svim poljima ploče, a drugu damu nema gdje postaviti. U bilo kom rasporedu od tri dame na 3x3 dasci, najmanje dvije prijete jedna drugoj. Dakle, za n jednako 2 ili 3, problem nema rješenja.

Što se tiče slučajeva n > 3, poznato je da je na bilo kojoj n×n ploči moguće ovako rasporediti n dama. da ne prijete jedni drugima. Mnogi članci posvećeni su dokazu ove daleko od očigledne činjenice, uključujući i ozbiljne matematičke publikacije.

Na tabli 4x4 postoji samo jedan osnovni raspored, i to dvostruko simetričan (a2, b4, c1, d3), odnosno postoje dva rješenja ukupno. Na tabli 5x5 postoje dvije glavne formacije: 1) a2, b4, c1, d3, e5; 2) a2, b5, c3, d1, e4; Ukupno ima deset pozicija za pretragu. Zanimljivo je da možete izabrati njih pet, koji će, kada se naslagaju jedan na drugi, ispuniti sva polja na tabli 5x5 sa 25 dama. U opštem slučaju, sličan namet je moguć samo za one koji nisu djeljivi ni sa 2 ni sa 3. Iz ovoga, posebno, proizilazi da je za redovnu tablu nemoguće odabrati osam rješenja za koje dame popunjavaju cela tabla.

Generalizirajući gornje algebarsko svojstvo rješenja problema osam kraljica, dobijamo da je raspored (t 1, t 2, … t n) n kraljica na ploči n × n željeni ako je za bilo koje i, j (i< j < n): |t j - t i | ≠ j - i. Здесь по-прежнему t i - номер горизонтали, на которой стоит ферзь i-й вертикали, а набор t 1 , …, t n есть перестановка чисел 1, …, п. Таким образом, для решения задачи в общем случае достаточно найти перестановку чисел 1, …, n, удовлетворяющую указанному условию.

Sada ćemo opisati jednu moguću šemu za željeni raspored n kraljica na n×n tabli za svih n > 5. Dokaz da je naš uslov zadovoljen u rezultujućem rasporedu može se naći, na primjer, u Okunev ili Yaglomov.

Razmotrimo niz slučajeva uzastopno. Neka je n isprva parno, sa n = 6k ili n = 6k + 4. Pola svih dama postavljamo na prve n/2 vertikale pomjeranjem viteza, počevši od druge horizontale i svaki put pomjerajući 2 polja gore i 1 desno. Drugu polovinu ćemo postaviti na preostalih n/2 vertikala na isti način, ali počevši od prve horizontale. Za tablu 6x6 (n = 6k, k = 1) ovo daje sledeći raspored dama: a2, b4, c6, d1, e3, f5 (rešenje prikazano na slici 45 za n = 10 dobija se na drugačiji način ).

Kada je n = 6k + 2 prethodna tehnika više ne radi, a dame se moraju postaviti na "lukaviji" način. Složimo ih pomjeranjem viteza iz druge vertikale duž

(n/2 - 2)-a, počevši od treće horizontale, i dalje od

(n/2 + 3) vertikala duž (n - 1) počevši od šeste horizontale. Kao rezultat, šest vertikala i šest horizontala table će ostati slobodni, na kojima šest dama mora zauzimati polja sa sljedećim koordinatama: (1, n - 3), (n/2 - 1, 1); (n/2, n - 1), (n/2 + 1, 2), (n/2 + 2, n), (n, 4). Za n = 14 (n = 6k + 2, k = 2) dobijamo raspored na sl. 44. Inače, na običnoj tabli 8×8 (8 = 6k + 2, k = 1) postavljanje osam dama na ovaj način poklapa se sa istim divnim rješenjem na sl. 43 (2. pozicija), ali je ovdje jedva moguće uočiti obrazac u rasporedu matica.

Ostaje nam da razmotrimo problem za neparne vrijednosti n. Da bismo dobili rješenje u ovom slučaju, dovoljno je napomenuti da je u rasporedu koji smo predložili na „parnim“ pločama glavna dijagonala (idući od donjeg lijevog ugla prema gornjem desnom) ostala slobodna. Uzimajući u obzir ovu okolnost, željeni raspored n dama na n×n tabli (za neparno n) može se dobiti na sljedeći način. Na vertikale i horizontale ove table sa brojevima od 1 do (n - 1) postavićemo (n - 1) dame kao što je to učinjeno na tabli (n - 1)×(n - 1) (n - 1 je čak!), a zatim ćemo n-tu damu postaviti u gornji desni ugao table. Koristeći opisanu metodu, iz naznačenog rasporeda na tabli 4×4 možemo dobiti prvi raspored dama na tabli 5×5, a iz rasporeda dama na tabli 6×6 imamo sljedeće za n = 7 : a2, b4, c6, d1, e3, f5, g7 .

Razmotrite omiljeni problem za razumijevanje algoritama, problem osam kraljica. Klasična definicija glasi: “postaviti 8 dama na šahovsku ploču tako da nijedna od njih ne pobijedi drugu.” Ok, problem je vrlo popularan u raznim intervjuima, a Wikipedia nam odmah daje rješenje u mom omiljenom Pythonu.

I to je sigurno ispravna odluka sa stanovišta obicna osoba, ali apsolutno besmisleno sa hakerske tačke gledišta, a ja ću vam reći zašto:

Analizirajmo algoritam: koristi se klasično pretraživanje unazad, područje rješenja predstavljamo u obliku grafa, čiji je svaki vrh pozicija dame u kojoj ona nije napadnuta i ne pobjeđuje dame koje su već postavljene na tabla, tj. samo trebamo sakupiti sve "grane" koje se sastoje od tačno osam vrhova. Kao metodu za traženje ovih „grana“, autor nam nudi klasični algoritam pretrage u širinu, tj. redoslijed prelaska grafa će izgledati ovako:

I čim algoritam proradi, dobićemo sva moguća rješenja.

U čemu je problem? U našem slučaju, za ploču 8x8 dobićemo 92 različita rješenja, ali zamislite da, kao što se često dešava u stvarnim problemima, ne znamo veličinu ploče. Ako je ploča 25x25, kao u Tai Shogi, tada će broj rješenja već biti 275,986,683,743,434.

Tabela koja pokazuje ovisnost broja rješenja o veličini ploče:

Šta će to značiti za naš scenario? A činjenica da će ići u veoma dugu potragu i pošto će sve odluke morati da drži u glavi, za samo 15 minuta Python će pojesti 300 megabajta memorije. Svako ko ima moćan procesor i veliku količinu RAM-a može provjeriti da li je ovaj proces uopće završen...

A sve što nam je trebalo da riješimo takav problem je da selektiramo ispravan algoritam obilazak grafa, što bi u našem slučaju bilo uobičajeno pretraživanje u dubinu, tada bi se obilazak grafa odvijao ovim redoslijedom:

I kod bi bio mnogo jednostavniji, pa čak i nakon 15 minuta skripta bi potrošila točno istu količinu memorije kao sekundu nakon pokretanja. A ovako bi izgledala njegova implementacija u Pythonu:

Def rc_queens(n_col, width, sol): if len(sol) == width: print sol else: za n_row u rasponu(width): if (safe_queen(n_row, n_col, sol)): rc_queens(n_col+1, width , sol+) def safe_queen(new_row, new_col, sol): za col u rasponu(len(sol)): if (sol == novi_red ili abs(col - new_col) == abs(sol - new_row)): vrati 0 return 1 ako __name__ == "__main__": za n u rasponu(8): rc_queens(1, 8, [n])
P.S. Ovo je samo hakersko viđenje problema, možda neko može ponuditi pogled na "teorijsku informatiku"?

"8 kraljica"– odlična slagalica za razvoj logičkog mišljenja. Ova online flash igra je jedinstvena moderna formulacija poznatog šahovskog problema, koju je izmislio šahist Max Basel 1848. godine.

Ljubitelji šaha vjerovatno su čuli za ovu najpopularniju matematičku igru ​​na šahovskoj tabli. Pronalaženje odgovora na pitanje kako rasporediti 8 matica u ovom problemu bit će korisno za sve koji žele razviti svoje intelektualne sposobnosti, pronaći rješenja za nestandardne probleme i promisliti poteze u potrazi za odgovorom.

Pravila. Problem sa 8 dama ima kao jedini uslov zadatak da se 8 figura - dama, (ili dama, ako želite) postavi na standardnu ​​šahovsku tablu (64 polja, 8x8), tako da nijedna od njih nije napadnuta od druge.

Sjećam se fraze iz Dumasove “Tri musketara”, koju je Richelieu objavio tokom partije šaha sa d’Artagnanom: “Ovo je kraljica, ona se kreće kako želi.” Ovaj citat, iako je u konkretnom slučaju bio dvosmislen, ipak je za one koji nisu upoznati sa pravilima šahovske igre. Pojasnimo da se dama pomiče na bilo koje polje okomito, vodoravno i dijagonalno, na bilo kojoj udaljenosti.

Ukupno originalna rješenja 12. Ukupan broj mogućih (uzimajući u obzir primjenu operacije simetrije) opcija je 92. Franz Nack je prvi objavio odgovor na ovaj problem 1850. godine. Od tada su mnogi naučnici rješavali i istraživali ovaj problem, nudeći vlastita rješenja. Tako je slavni njemački matematičar, mehaničar i fizičar Karl Gauss jako volio ovu slagalicu i pronašao je 72 moguće opcije rasporeda. Kreativno je pristupio procesu pronalaženja odgovora – različite kombinacije od 8 dama postignute su zanimljivom tehnikom... rotiranjem table za 90, 180 odnosno 270 stepeni. Ovo je netrivijalno rješenje ove zagonetke.

Zadatak je prilično kompliciran, ali barem jedna opcija kako pravilno postaviti matice može se pronaći prilično brzo i naziva se eksplicitnom. Najpopularniji ispravna lokacija postiže se sledećim rasporedom dama: a2, b4, c6, d8, e3, f1, g7, h5. Dijagram ovog rasporeda je prikazan na prvoj slici, preostala tri načina postavljanja dama pronađena su rotacijom šahovske ploče.

Pokušajte sami pronaći druge kombinacije. Sretno!

Vještine koje se mogu obučiti

Prilikom traženja odgovora na problem, treniraju se sljedeće vještine:

• – sposobnost pronalaženja nestandardna rješenja intelektualni zadaci, ne djeluju na osnovu izmišljenog algoritma, adaptivno tražeći odgovor;
• – vrsta mentalne aktivnosti i selektivni smjer percepcije, bez kojih je koncentracija na objektu nemoguća;
• logičko mišljenje je vrsta misaonog procesa u kojem se znanje postiže upotrebom koncepata i logičkih konstrukcija u zaključivanju.

Volite li slične zagonetke, igrice, zagonetke i testove? Dobijte pristup svim interaktivnim materijalima na web stranici kako biste se efikasnije razvijali.

NASTAVNI RAD

"Rješenje problema 8 kraljica"

Harkov 2007

Svrha rada: razviti program koji bi jasno pokazao mogućnosti postavljanja dama na šahovsku ploču, zadovoljavajući pravila zadatka.

Metoda istraživanja: proučavanje literature, kreiranje i otklanjanje grešaka programa na računaru, provjera rješenja.

Program postavljanja matice može se koristiti u praksi u obrazovne svrhe. Može se koristiti i za učenje matematički model dodeljen zadatak. Uostalom, problem je posebno zanimljiv kada se veličina šahovske ploče povećava.

Zadatak zvuči ovako:

“Na koji način se osam dama može postaviti na tablu da ne prijete jedna drugoj, tj. nema dva koja stoje na istoj vertikali, horizontali i dijagonali i koliko takvih načina?"

Problem osam kraljica

Očigledno je nemoguće postaviti više od osam mirnih dama (kao i topova) na regularnu tablu. Lako je pronaći neki raspored od osam matica koje ne prijete jedna drugoj (na slici su prikazana četiri potrebna rasporeda). Mnogo je teže izbrojati ukupan broj aranžmana i izvesti ih, što je, zapravo, zadatak.

Zanimljivo je da su mnogi autori greškom pripisali ovaj problem i njegovo rješenje samom K. Gaussu. Zapravo, prvi ga je 1848. godine postavio njemački šahista M. Bezzel. Dr F. Science pronašao je 60 rješenja i objavio ih u listu “Illustrierte Zeitung” od 1. juna 1850. Tek nakon toga Gauss se zainteresovao za problem i pronašao 72 rješenja, o čemu je izvijestio u pismu svom prijatelju astronomu. Schumacher od 2. septembra 1850. Kompletan isti set rješenja, koji se sastoji od 92 pozicije, primio je isti F. Sciences. On ih je naveo u pomenutim novinama od 21. septembra 1850. Ovu hronologiju je uspostavio poznati njemački istraživač matematičke zabave W. Arens.

Strogi dokaz da 92 rješenja iscrpljuju sve mogućnosti dobio je tek 1874. engleski matematičar D. Glasher (koristeći teoriju determinanti). Gledajući unaprijed, napominjemo da postoji samo dvanaest značajnih rješenja (koja se ne poklapaju sa refleksijama i rotacijama ploče).

Postoji mnogo poznatih načina da se organizira efikasna potraga za lokacijom osam mirnih matica (metode Permentier, La Noe, Gunther, Glasher, Laquiere, itd.). Ove metode su opisane u brojnoj literaturi o zabavnoj matematici. U našem kompjuterskom dobu, problem ove vrste ne bi izazvao tako veliko interesovanje. Uostalom, dovoljno je napraviti jednostavan program, a u roku od nekoliko minuta nakon što ga unesete u mašinu, ispisaće se svih 92 potrebne pozicije.

Iz svakog rješenja za problem dama može se dobiti niz drugih rotiranjem ploče za 90, 180 i 270°, kao i preslikavanjem u odnosu na linije koje dijele ploču na pola. Na primjer, iz rasporeda prikazanog na sl. i, kada se ploča okrene za 90° u smjeru kazaljke na satu, dobijamo raspored na sl. c, a kada se daska reflektuje u odnosu na liniju koja razdvaja krila kralja i dama - na sl. d. Koristeći druge rotacije i refleksije ploče, može se dobiti još pet rješenja.

Dakle, naznačene operacije sa šahovskom tablom omogućavaju da se iz jednog rasporeda mirnih dama dobije, uopšteno govoreći, sedam novih. Dokazano je da su u opštem slučaju na nhn dasci (za n > 1) za bilo koji raspored n mirnih matica moguće tri situacije:

1) jednim odrazom daske nastaje novi raspored matica, ali se rotacijama i drugim odrazima ne dobijaju nova rješenja;

2) novo rešenje nastaje kada se tabla rotira za 90°, a njeni odrazi daju još dva rasporeda;

3) tri rotacije table i četiri refleksije dovode do sedam različitih rasporeda (a ako računamo originalni, onda imamo ukupno osam pozicija).

U slučaju 1) originalno rješenje se naziva dvostruko simetrično, u slučaju 2) – simetrično, au slučaju 3) – jednostavno. Za običnu ploču, svako rješenje je jednostavno ili simetrično, a ne postoje dvostruko simetrična rješenja.

Skup rasporeda od osam mirnih kraljica naziva se osnovnim ako se, prvo, ti rasporedi ne transformišu jedan u drugi tokom rotacija i odraza daske, i drugo, bilo koji drugi raspored se dobije iz nekog osnovnog pomoću ovih transformacija daske. Dokazano je da svaki osnovni skup rješenja problema sadrži tačno 12 aranžmana. Evo jednog takvog seta:

1) vidi sl. A;

2) vidi sl. b;

3) a4, b1, c5, d8, e6, f3, g7, h2;

4) a4, b2, c5, d8, e6, f1, g3, h7;

5) a4, b2, c7, d3, e6, f8, g1, h5;

6) a4, b2, c7, d3, e6, f8, g5, h1;

7) a3, b5, c2, d8, e6, f4, g7, h1;

8) a4, b1, c5, d8, e2, f7, g3, h6;

9) a4, b7, c3, d8, e2, f5, g1, h6;

10) a6, b4, c2, d8, e5, f7, g1, h3;

11) a4, b8, c1, d5, e7, f2, g6, h3;

12) a4, b2, c7, d5, e1, f8, g6, h3.

Preostalih 80 formacija dobijeno je od ovih dvanaest pomoću rotacija i refleksije daske. Glavni raspored na sl. b je simetričan, ostalih jedanaest osnovnih rasporeda je jednostavnih. Dakle, ukupno na tabli imamo 11·8+1·4=92 rasporeda osam dama koje se međusobno ne ugrožavaju.

Napomenimo nekoliko zanimljiva svojstva postavljanje mirnih matica. Simetrični raspored na sl. b, kako bi trebalo da bude, ima vanjsku simetriju. Odlikuje ga i činjenica da središnji dio table (4x4 kvadrat) ne zauzimaju dame. Obe glavne dijagonale table su takođe slobodne ovde (osmi glavni aranžman takođe ima ovo svojstvo). U prvom rasporedu (sl. a), nema tri dame na istoj pravoj liniji povučenoj kroz centre polja (to znači ne samo vertikale, horizontale i dijagonale daske, već i prave linije sa drugim uglovima nagiba ).

Bilo koje rješenje problema osam kraljica može se zapisati kao skup (t1, t2, j, t8), koji je permutacija brojeva 1, 2, j, 8. Ovdje je ti broj vodoravne linije na kojoj je kraljica i-te vertikalne tribine. Kako dame ne stoje na istoj horizontalnoj liniji, onda su svi brojevi ti različiti, a pošto dame ne stoje na istoj dijagonali, onda za bilo koje i, j (i< j Ј 8) имеем: |tj-ti| № j-i.

Zapišimo brojeve 1, 2, j, 8 prvo rastućim redoslijedom, a zatim opadajućem. Nakon toga, dodajemo brojeve svake od ove dvije permutacije sa brojevima proizvoljne permutacije od osam brojeva, na primjer ovo - (3, 7, 2, 8, 5, 1, 4, 6): 1, 2, 3, 4, 5, 6, 7, 8

3, 7, 2, 8, 5, 1, 4, 6

4,9, 8, 7, 6, 5, 4, 3, 2, 1

3, 7, 2, 8, 5, 1, 4, 6

11,14,8,13,9,4, 6, 7.

Rezultirajući zbroji čine dva skupa: (4, 9, 5, 12, 10, 7, 11, 14) i (11, 14, 8, 13, 9, 4, 6, 7). Hajde da razmotrimo sledeći problem.

Koje permutacije brojeva od 1 do 8 rezultiraju dva takva skupa, u svakom od kojih su svi elementi različiti, kao rezultat naznačene operacije sabiranja?

Problem osam kraljica privukao je Gaussovu pažnju upravo u vezi sa ovim čisto aritmetičkim problemom. Ispostavilo se da postoji korespondencija jedan-na-jedan između rješenja ova dva problema. Drugim riječima, svaki raspored od osam matica koje ne prijete jedna drugoj daje rješenje aritmetičkog problema, i obrnuto. Za odabranu permutaciju, oba skupa se sastoje od različitih brojeva, i to nije slučajno – odgovara prvom glavnom rasporedu (vidi sliku a).

Lako je vidjeti da kada se ploča rotira i reflektira, neka rješenja se dobijaju od drugih koristeći jednostavne aritmetičke operacije na koordinatama polja koje zauzimaju kraljice. Analiza ovih operacija otkriva dodatna svojstva rješenja o kojima nećemo raspravljati.

Problem n kraljica. Stavite n dama na nxn šahovsku ploču tako da ne prijete jedna drugoj.

Na ploči 1x1, jedna dama je postavljena na jedno polje i rješenje postoji. Na tabli 2x2, jedna dama, bez obzira gdje stoji, napada tri druga polja, a drugu damu nema gdje postaviti. Samo dvije mirne dame mogu stati na dasku 3x3. Dakle, za ploče 2x2 i 3x3 problem nema rješenja. Ova dva slučaja su izuzeci. Za svih n > 3, n x n dama se mogu postaviti na nxn tablu koje ne prijete jedna drugoj.

Na tabli 4´4 nalazi se jedan glavni raspored, i to dvostruko simetričan: a2, b4, c1, d3, tj. Postoje samo dva rješenja. Postoje dvije glavne formacije na tabli 5´5: 1) a2, b4, c1, d3, e5; 2) a2, b5, c3, d1, e4. Ukupan broj Postoji deset formacija, a od njih možete izabrati pet takvih da, kada se nalože jedna na drugu, 25 dama popuni sva polja na tabli 5x5.

Imajte na umu da u opštem slučaju, n aranžmana (rješenja problema) mogu popuniti cijelu nxn ploču kada se nadograđuju samo za one n koji nisu višekratnici dva i tri. Iz ovoga, posebno, proizilazi da je za redovnu tablu nemoguće odabrati osam rasporeda koji pokrivaju sva 64 polja na tabli.

Uopštavajući algebarsko svojstvo rješenja problema osam kraljica, dobijamo da je raspored n kraljica (t1, t2, j, tn) na ploči n´n željeni ako za bilo koje i, j (i< j Ј n) имеет место: |tj-ti| № j-i. Таким образом, задача об n ферзях сводится к чисто математической задаче о нахождении перестановки чисел 1, 2, ј, n, удовлетворяющей указанному условию. Известно много решений этой задачи, некоторые из них опубликованы в серьезных математических журналах. Один из методов расстановки n ферзей, не угрожающих друг другу на произвольной доске nґn (n і 5), можно найти в книге «Математика на шахматной доске».

Opis algoritma i strukture programa:

Ovaj program implementira rekurzivnu metodu za rješavanje problema 8 kraljica.

Imamo funkciju (int put_queen (int x)), koja stavlja sljedeću kraljicu na polje i sama sebe poziva da postavi sljedeću, ako se sljedeća kraljica ne može postaviti, onda vraća kontrolu funkciji iz koje je pozvana , a to zauzvrat pokušava da postavi svoju kraljicu na drugo mjesto i ponovo rekurzivno dozove sebe. Kada funkcija postavi posljednju damu, rezultat postavljanja se prikazuje korisniku.

Na samom početku pozivamo funkciju s parametrom x jednakim nuli (numeracija počinje od 0), što znači da mora postaviti prvu kraljicu. Kada ova funkcija vrati kontrolu glavnoj funkciji, to znači da su sve opcije pronađene.

Za pohranjivanje položaja kraljica koristi se niz od 8 elemenata cjelobrojnog tipa (int queens). Redoslijed elementa u ovom nizu označava dam broj i njegovu x'koordinatu, odnosno kolonu, i njegovu vrijednost - y'koordinatu, odnosno red. Koristimo svojstvo da ne može biti nekoliko matica na jednom stupcu.

Prva verzija slagalice iz 1850. godine, kada su dvije dame unaprijed instalirane na ploči, a igrač mora postaviti preostale dame (pogledajte dva rješenja problema ispod reza)

Problem sa N damama je postaviti N dama na N×N tablu na takav način da nijedna dama ne bude napadnuta od strane druge, sa nekoliko dama unapred instaliranih na tabli. To jest, na kraju, dvije dame ne smiju biti na istoj liniji ili dijagonali. Problem je prvi put formulisan 1848. godine, a 1850. godine izmišljena je verzija slagalice u kojoj se određeni broj dama postavlja na tablu unaprijed, a igrač mora staviti ostale, ako je moguće.

Istraživači sa Univerziteta St Andrews (Škotska) objavili su rad koji pokazuje da problem N kraljica nije samo #P-potpun problem, već i NP-potpun problem. Štaviše, Clay Mathematical Institute (SAD) spreman je platiti milion dolara svakome ko može optimizirati rješenje ovog problema kao problema za dokazivanje P=NP.

Kao što je poznato, u teoriji složenosti, #P je klasa problema čije je rješenje broj uspješnih, odnosno završavajućih u prihvatajućim stanjima, računskih putanja za određenu nedeterminističku Turingovu mašinu koja radi u polinomskom vremenu. Računski problemi klase #P (problemi brojanja) povezani su sa odgovarajućim problemima rješivosti (problemi odlučivanja) klase NP.

Naučnici napominju da je ovaj problem možda najjednostavniji među NP-potpunim problemima koji objašnjava suštinu ovih problema svakome ko poznaje pravila šaha. Ovaj zadatak je općenito vrlo zanimljiva priča. Svojevremeno je to privuklo pažnju Gausa, koji je čak napravio malu grešku u rješavanju (na ploči 8x8 prijavio je 76 rješenja, ali je potom i sam priznao da su četiri pogrešna, tako da su ostala samo 72, a kasnije Gauss je uspostavio sva 92 rješenja za 8x8 ploču).

Generaliziranje problema na N×N ploču privuklo je pažnju mnogih matematičara. U proteklih pola veka objavljeno je nekoliko desetina naučnih radova posvećenih ovom problemu. Najmanje šest od njih je citirano više od 400 puta na Google Scholar-u: Golomb & Baumert, 1965; Bitner & Reingold, 1975; Mackworth & Freuder, 1985; Minton, Johnston, Philips, & Laird, 1992; Selman, Levesque & Mitchell, 1992; Crawford, Ginsberg, Luks, & Roy, 1996.

Složenost problema N kraljica često se pogrešno procjenjuje. Čak iu široko citiranim radovima, često se naziva NP-teškim problemom, ali to će biti samo ako je P=NP. U stvari, računska verzija problema, odnosno određivanje broja rješenja za N kraljica, je niz A000170 iz Online Enciklopedije cijelih nizova. Ovaj niz je sada poznat za maksimum n=27, gdje broj rješenja prelazi 2,34×10 17 . Ništa drugo nije poznato efikasno rešenje problema od obične grube sile. Tako je za n=27 u 2016. godini korišteno paralelno pretraživanje velikih razmjera na FPGA.

Istovremeno, ako kompjuter počne da nabraja moguće pozicije matica na tabli od 1000x1000 ćelija, tada će se zauvek opterećivati ​​ovim problemom. Prema naučnicima, ako neko pronađe zaista brz i efikasan način rješenje, od njega će moći dobiti mnogo više od milion dolara od Clay Mathematics Institute. „Ako napišete program koji može da reši problem zaista brzo, mogli biste ga prilagoditi da reši mnoge važne probleme sa kojima se svakodnevno susrećemo“, kaže profesor informatike Ian Gent, jedan od autora. naučni rad. - Među njima su trivijalni problemi poput pronalaženja najviše velika grupa vaši prijatelji na Facebooku koji se ne poznaju, ili vrlo važni zadaci poput razbijanja kodova koji čuvaju sve naše online transakcije bezbednim."

Ali ovo su čisto teorijske spekulacije. U praksi se još niko nije približio rješavanju problema N matica na brz i efikasan način. Dokazivanje da postoji efikasniji način za rješavanje problema od jednostavnog isprobavanja svih opcija dat će vam milion dolara.