Kapitola 8. Problém osmi královen

Problém osmi královen, stejně jako problém pohybu rytířů, je jedním z nejznámějších matematických problémů na světě. šachovnice. Pokud se rytířským problémem zabýval Leonhard Euler, přitáhl problém královny pozornost dalšího velkého matematika - Karla Gausse.

Kolika způsoby lze umístit osm dam na šachovnici tak, aby se navzájem neohrožovaly, to znamená, že žádné dvě nebyly na stejné svislé, vodorovné nebo diagonále?

Nalezení toho či onoho uspořádání královen, které vyhovuje podmínkám úlohy, není tak obtížné (čtyři řešení jsou na obr. 43). Je mnohem obtížnější vypočítat celkový počet stávajících uspořádání; ve skutečnosti je to problém osmi královen. Je jasné, že stejně jako v případě věží není možné umístit na šachovnici více než osm dam, které na sebe neútočí. A v souladu s tím není možné na hrací desku n×n umístit více než n dam nezbytným způsobem (v obecný pohled problém bude diskutován níže).

Rýže. 43. Osm dam neohrožujících dvě navzájem na šachovnici

Je zvláštní, že mnozí autoři mylně připisují problém osmi královen a jeho řešení samotnému Gaussovi. Ve skutečnosti to byl v roce 1848 jako první německý šachista M. Bezzel. Dr. F. Nauk (slepý od narození) našel 60 řešení a publikoval je v novinách „Illustrierte Zeitung“ z 1. června 1850. Teprve poté se Gauss začal o problém zajímat a našel 72 řešení, o kterých informoval v dopise jeho přítele astronoma Schumachera z 2. září 1850. Úplný soubor rozhodnutí, sestávající z 92 stanovisek, obdržel stejný F. Sciences (citoval je ve zmíněných novinách z 21. září 1850). Tuto chronologii založil slavný německý badatel matematické zábavy W. Arens, který ve svých knihách věnoval zvažovanému problému mnoho prostoru.

Důkaz, že 92 řešení vyčerpává všechny možnosti, získal až v roce 1874 anglický matematik D. Glasher (s využitím teorie determinantů).

V zásadě platí, že umístěním osmi dam na šachovnici všemožným způsobem nakonec najdeme všechna uspořádání, která nám vyhovují. Tato cesta je však příliš dlouhá a nudná. Můžeme se omezit pouze na řešení příslušného problému věže a vybrat z nich ta, ve kterých žádná dvojice věží není na stejné diagonále. Ale i v tomto případě je hledání poměrně velké (jak víme, bude potřeba více než 40 000 pokusů). Při „ručním“ řešení problému (a přesně tak se to dělalo v minulém století) je tedy třeba dobře promyslet vynucený výčet opatření. Existuje mnoho známých způsobů, jak zorganizovat více či méně rozumné hledání požadovaného uspořádání královen (metody Permentier, La Noe, Gunter, Glasher, Laquiere atd.). Tyto metody jsou popsány v četné literatuře o zábavná matematika(hlavně v minulém století a na začátku tohoto). V naší době počítačů by problém tohoto druhu nemohl vzbudit takový zájem. Stačí totiž vytvořit jednoduchý počítačový program – a během pár minut po jeho zavedení do stroje se vytiskne všech 92 potřebných pozic.

Od každého řešení problému s dámou lze získat řadu dalších otočením desky kolem středu o 90, 180 a 270° ve směru hodinových ručiček (otočení o 360° se vrátí do výchozí pozice). Z tohoto uspořádání dam lze také získat novou zrcadlením desky vzhledem k jedné z tečkovaných čar na obr. 43 (1. pozice) . Například z prvního uspořádání na tomto obrázku, když se hrací deska otočí o 90°, dostaneme třetí, a když se odrazí vzhledem k linii oddělující krále a dámy, dostaneme čtvrté. Pomocí dalších rotací a odrazů lze získat dalších pět řešení.

Takže když se hrací deska otočí a odrazí, z jednoho uspořádání dam se obecně získá sedm nových. Bylo prokázáno, že v obecném případě na n×n šachovnici (pro n > 1) pro jakékoli uspořádání n dam, které se navzájem neohrožují, jsou možné pouze tři situace: a) s jedním odrazem šachovnice nový uspořádání je získáno, a rotace a jiné odrazy nejsou nic nového nedávají; b) nové řešení se získá otočením desky o 90° a odrazy dávají další dvě uspořádání; c) všechna tři otočení a čtyři odrazy šachovnice vedou k osmi nesprávným formacím (včetně té původní).

V případě a) se původní řešení nazývá dvojitě symetrické, v případě b) - symetrické a v případě c) - jednoduché. Pro běžnou desku je každé řešení buď jednoduché, nebo symetrické a neexistují žádná dvojitě symetrická řešení. Algebraický výklad řešení každé třídy lze nalézt v Okunevovi.

Množina (množina) uspořádání osmi dam se nazývá základní, pokud se za prvé při rotacích a odrazech šachovnice do sebe netransformují a za druhé se z nějakého základního pomocí těchto transformací získá jakékoli jiné uspořádání. Je známo, že každá sada základních řešení problému obsahuje přesně 12 pozic (uspořádání osmi dam). Zde je jedna z těchto sad:

Zbývajících 80 pozic je získáno z těchto dvanácti jako výsledek rotací a odrazů desky. Prvních 11 uspořádání je jednoduchých a pouze poslední je symetrické. Na šachovnici je tedy celkem 11×8 + 1×4 = 92 uspořádání osmi dam, které se navzájem neohrožují.

Vzhledem k hlavním uspořádáním můžete objevit některé jejich zajímavé vlastnosti. Snadno si lze například všimnout vnější symetrie posledního uspořádání (2. pozice na obr. 43). Toto základní řešení, jediné svého druhu, se také vyznačuje tím, že pouze ono má středovou část desky (čtverec 4x4) bez dam. Další jeho vlastností je, že dámy nezabírají hlavní úhlopříčku desky a1 - h8 (tuto vlastnost má i první hlavní řešení).

První uspořádání na Obr. 43 je zvláštní, protože zde žádné tři dámy nestojí na stejné přímce protažené středy polí (to znamená nejen svislice, vodorovné roviny a úhlopříčky desky *, ale také přímky s jinými úhly sklonu).

Jakékoli řešení úlohy lze zapsat jako množinu (t 1, t 2, ... t 8), což je permutace čísel 1, 2, ..., 8. Zde ti je číslo vodorovné čára, na které stojí královna i-té vertikály. Protože žádné dvě královny nejsou na stejné vodorovné čáře, pak jsou všechny t x různé, a protože královny nejsou na stejné diagonále, pak pro libovolné i, j (i< j ≤ 8) имеем: |t j - t i | ≠ j - i.

Numerický zápis umístění královny je někdy velmi vhodný. Například pro nalezení formací s pevnou pozicí dámy na a1 stačí vybrat ze všech 92 pozic zapsaných v číselném tvaru ty, ve kterých je první souřadnice rovna 1. Pokud je pozice dámy na d3 pevná , pak byste měli vybrat pozice, ve kterých je čtvrtá pozice číslo 3 atd.

Čísla 1, 2, ..., 8 zapišme nejprve vzestupně a poté sestupně. Poté sečteme čísla každé z těchto dvou permutací s čísly libovolné permutace, například (3, 7, 2, 8, 5, 1, 4, 6):

Výsledné součty tvoří dvě sady čísel: (4, 9, 5, 12, 10, 7, 11, 14) a (11, 14, 8, 13, 9, 4, 6, 7). Vyvstává další problém.

Jaké permutace čísel 1, 2,…, 8 vedou v důsledku naznačené operace sčítání ke dvěma takovým množinám, z nichž každá jsou různá?

Problém osmi královen zajímal Gausse právě v souvislosti s tímto čistě aritmetickým problémem. Ukazuje se, že existuje vzájemná korespondence mezi řešeními problému královny a řešeními popsané aritmetické úlohy. Jinými slovy, každé uspořádání osmi královen, které se navzájem neohrožují, poskytuje řešení aritmetického problému – a naopak. Pro zvolenou permutaci se obě sady skládají z různých čísel, a to není náhodné - odpovídá to první pozici na Obr. 43.

Je snadné vidět, že při n rotacích hrací desky se některá řešení získají od jiných pomocí jednoduchých aritmetických operací na souřadnicích polí obsazených dámami. Studium těchto operací nám umožňuje objevit další vlastnosti řešení (z nichž některé jsou uvedeny Okunevem).

Problém n královen. Umístěte n dam na n×n šachovnici tak, aby se navzájem neohrožovaly.

Na desce 1x1 je jedna dáma umístěna na jedno pole a existuje řešení. Na desce 2x2 ohrožuje jedna královna, ať stojí kdekoli, všechna pole desky a druhou královnu není kam umístit. V jakémkoli uspořádání tří královen na desce 3x3 se nejméně dvě z nich navzájem ohrožují. Takže pro n rovné 2 nebo 3 nemá problém žádná řešení.

Pokud jde o případy n > 3, je známo, že na libovolné desce n×n je možné takto uspořádat n dam. aby se navzájem neohrožovali. Mnoho článků, včetně těch ve seriózních matematických publikacích, je věnováno dokazování tohoto zdaleka ne zřejmého faktu.

Na desce 4x4 je pouze jedno základní uspořádání, a to dvojnásobně symetrické (a2, b4, c1, d3), tedy celkem dvě řešení. Na desce 5x5 jsou dvě hlavní formace: 1) a2, b4, c1, d3, e5; 2) a2, b5, c3, dl, e4; Vyhledávacích pozic je celkem deset. Zajímavostí je, že si jich můžete vybrat pět, které po naskládání na sebe zaplní všechna políčka desky 5x5 s 25 dámami. Obecně platí, že podobné uložení je možné pouze u těch, které nejsou dělitelné ani 2, ani 3. Z toho zejména vyplývá, že pro běžnou desku nelze vybrat osm řešení, pro která královny vyplňují pole. celou desku.

Zobecněním výše uvedené algebraické vlastnosti řešení problému osmi dam získáme, že uspořádání (t 1, t 2, … t n) n dam na desce n × n je požadované, pokud pro jakékoli i, j (i< j < n): |t j - t i | ≠ j - i. Здесь по-прежнему t i - номер горизонтали, на которой стоит ферзь i-й вертикали, а набор t 1 , …, t n есть перестановка чисел 1, …, п. Таким образом, для решения задачи в общем случае достаточно найти перестановку чисел 1, …, n, удовлетворяющую указанному условию.

Nyní si popíšeme jedno možné schéma požadovaného uspořádání n dam na desce n×n pro všechna n > 5. Důkaz, že je naše podmínka ve výsledném uspořádání splněna, můžeme najít například u Okuneva nebo Yaglomova.

Uvažujme postupně řadu případů. Nechť je n nejprve sudé, přičemž n = 6k nebo n = 6k + 4. Polovinu všech dam umístíme na prvních n/2 svislic pohybem jezdce, počínaje druhou vodorovnou rovinou a pokaždé se posuneme o 2 pole nahoru a 1 doprava. Druhou polovinu položíme na zbývajících n/2 svislic stejným způsobem, ale začneme od první horizontály. Pro šachovnici 6x6 (n = 6k, k = 1) to dává následující uspořádání dám: a2, b4, c6, d1, e3, f5 (řešení uvedené na obr. 45 pro n = 10 získáme jinak).

Když n = 6k + 2, předchozí technika již nefunguje a královny musí být umístěny více „mazaným“ způsobem. Uspořádejme je tak, že přesuneme rytíře z druhé svislice podél

(n/2 - 2)-tý, počínaje třetí horizontálou a poté od

(n/2 + 3) svislice podél (n - 1) počínaje šestou vodorovnou rovinou. V důsledku toho zůstane volných šest svislic a šest vodorovných rovin herního plánu, na kterých musí šest dam obsadit pole s následujícími souřadnicemi: (1, n - 3), (n/2 - 1, 1); (n/2, n - 1), (n/2 + 1, 2), (n/2 + 2, n), (n, 4). Pro n = 14 (n = 6k + 2, k = 2) získáme uspořádání na Obr. 44. Mimochodem, na běžné desce 8×8 (8 = 6k + 2, k = 1) se umístění osmi dam tímto způsobem shoduje se stejným báječným řešením na Obr. 43 (2. pozice), ale jen stěží zde lze zaznamenat vzor v uspořádání dam.

Zbývá nám zvážit problém pro liché hodnoty n. Pro řešení v tomto případě stačí poznamenat, že v námi navrženém uspořádání na „sudých“ deskách zůstala hlavní diagonála (směřující z levého dolního rohu do pravého horního) volná. Vezmeme-li tuto okolnost v úvahu, požadované uspořádání n dam na desce n×n (pro liché n) lze získat následovně. Na vertikály a horizontály této desky s čísly od 1 do (n - 1) položíme (n - 1) dámu tak, jak se to dělá na desce (n - 1)×(n - 1) (n - 1 je sudá!), a poté položíme n-tou dámu do pravého horního rohu desky. Popsaným způsobem můžeme z naznačeného uspořádání na desce 4×4 získat první uspořádání dam na desce 5×5 a z uspořádání dam na desce 6×6 máme pro n = 7 : a2, b4, c6, d1, e3, f5, g7.

Zvažte oblíbený problém pro pochopení algoritmů, problém osmi královen. Klasická definice zní: „umístit 8 královen na šachovnici tak, aby žádná z nich neporazila tu druhou“. Ok, problém je velmi populární v různých rozhovorech a Wikipedie nám okamžitě nabízí řešení v mém oblíbeném Pythonu.

A to je jisté správné řešení z pohledu běžná osoba, ale z pohledu hackera naprosto nesmyslné a já vám řeknu proč:

Rozeberme si algoritmus: používá se klasické zpětné vyhledávání, oblast řešení znázorňujeme ve formě grafu, jehož každý vrchol je pozicí dámy, ve které není napadena a neporáží již umístěné dámy. deska, tzn. potřebujeme pouze shromáždit všechny „větve“ skládající se z přesně osmi vrcholů. Jako metodu pro vyhledávání těchto „větví“ nám autor nabízí klasický algoritmus prohledávání do šířky, tzn. pořadí procházení grafu bude vypadat takto:

A jakmile bude algoritmus fungovat, dostaneme všechna možná řešení.

Tak co je za problém? V našem případě pro desku 8x8 dostaneme 92 různých řešení, ale představte si, že, jak se často stává ve skutečných problémech, neznáme velikost desky. Pokud je deska 25x25, jako v Tai Shogi, pak počet řešení již bude 275 986 683 743 434.

Tabulka znázorňující závislost počtu řešení na velikosti desky:

Co to bude znamenat pro náš scénář? A to, že půjde do velmi dlouhého hledání, a protože bude muset mít všechna rozhodnutí v paměti, za pouhých 15 minut Python sežere 300 megabajtů paměti. Zda je tento proces vůbec dokončen, si může ověřit každý, kdo má výkonný procesor a velké množství paměti RAM...

A vše, co jsme potřebovali k vyřešení takového problému, bylo vybrat správný algoritmus procházení grafu, což by v našem případě bylo pravidelné prohledávání do hloubky, pak by procházení grafu probíhalo v tomto pořadí:

A kód by byl mnohem jednodušší a i po 15 minutách by skript spotřeboval přesně stejné množství paměti jako sekundu po spuštění. A takto by vypadala jeho implementace v Pythonu:

Def rc_queens(n_col, width, sol): if len(sol) == width: print sol else: for n_row in range(width): if (safe_queen(n_row, n_col, sol)): rc_queens(n_col+1, width , sol+) def safe_queen(new_row, new_col, sol): for col in range(len(sol)): if (sol == new_row or abs(col - new_col) == abs(sol - new_row)): return 0 return 1 if __name__ == "__main__": pro n v rozsahu(8): rc_queens(1, 8, [n])
P.S. To je jen hackerský pohled na problém, možná někdo může nabídnout pohled "teoretické informatiky"?

"8 královen"– vynikající puzzle úkol pro rozvoj logického myšlení. Tato online flash hra je unikátní moderní formulací slavného šachového problému, který vynalezl šachista Max Basel v roce 1848.

Milovníci šachů už o této nejoblíbenější matematické hře na šachovnici pravděpodobně slyšeli. Hledání odpovědi na otázku, jak umístit 8 královen do tohoto problému, bude užitečné pro každého, kdo chce rozvíjet své intelektuální schopnosti, nacházet řešení nestandardních problémů a promýšlet tahy při hledání odpovědi.

Pravidla. Problém 8 dam má jako jedinou podmínku za úkol položit 8 figurek - dam (nebo královen, chcete-li) na standardní šachovnici (64 polí, 8x8), aby žádná z nich nebyla napadena jinou.

Pamatuji si větu z Dumasových „Tři mušketýři“, kterou vydal Richelieu během šachové partie s d’Artagnanem: „Toto je královna, pohybuje se, jak se jí zachce.“ Tento citát, i když byl v konkrétním případě nejednoznačný, je stále pro ty, kteří nejsou obeznámeni s pravidly šachové hry. Ujasněme si, že dáma se pohybuje na libovolné pole vertikálně, horizontálně a diagonálně, na jakoukoli vzdálenost.

Celkový originální řešení 12. Celkový počet možných (s přihlédnutím k aplikaci operace symetrie) možností je 92. Odpověď na tento problém publikoval v roce 1850 jako první Franz Nack. Od té doby mnoho vědců tento problém vyřešilo a zkoumalo a nabídlo vlastní řešení. Slavnému německému matematikovi, mechanikovi a fyzikovi Karlu Gaussovi se tedy tato hádanka velmi zalíbila a našel 72 možností možného uspořádání. Kreativně přistoupil k procesu hledání odpovědi – různých kombinací 8 dam bylo dosaženo zajímavou technikou... otočením desky o 90, 180 a 270 stupňů. Toto je netriviální řešení této hádanky.

Úkol je poměrně komplikovaný, ale alespoň jedna možnost, jak správně umístit královny, se dá najít celkem rychle a nazývá se explicitní. Nejoblíbenější správné umístění je dosaženo následujícím uspořádáním dam: a2, b4, c6, d8, e3, f1, g7, h5. Schéma tohoto uspořádání je na prvním obrázku, zbývající tři způsoby umístění dam byly nalezeny otáčením šachovnice.

Zkuste sami najít jiné kombinace. Hodně štěstí!

Trénovatelné dovednosti

Při hledání odpovědi na problém se trénují následující dovednosti:

• - schopnost najít nestandardní řešení intelektuální úkoly, nejednají na základě vymyšleného algoritmu, adaptivně hledají odpověď;
• – typ duševní činnosti a selektivní směr vnímání, bez kterého není možné soustředit se na předmět;
• logické myšlení je typ myšlenkového procesu, ve kterém se znalostí dosahuje prostřednictvím aplikace pojmů a logických konstruktů v uvažování.

Máte rádi podobné hádanky, hry, hlavolamy a testy? Získejte přístup ke všem interaktivním materiálům na webu, abyste se mohli vyvíjet efektivněji.

KURZOVÁ PRÁCE

„Řešení problému 8 královen“

Charkov 2007

Účel práce: vyvinout program, který by jasně demonstroval možnosti umístění dam na šachovnici, splňující pravidla problému.

Metoda výzkumu: studium literatury, tvorba a ladění programů na počítači, kontrola řešení.

Program umístění královny lze v praxi využít pro vzdělávací účely. Dá se využít i ke studiu matematický model zadaný úkol. Ostatně problém je zajímavý zejména tehdy, když se zvětší velikost šachovnice.

Úkol zní takto:

„Jakými způsoby lze na šachovnici umístit osm dam, aby se navzájem neohrožovaly, tzn. žádné dvě nestály na stejné vertikální, horizontální a diagonální a kolik takových cest?

Problém osmi královen

Je zřejmé, že není možné umístit více než osm pokojných královen (stejně jako věže) na běžnou desku. Je snadné najít nějaké uspořádání osmi královen, které se navzájem neohrožují (obrázek ukazuje čtyři požadovaná uspořádání). Je mnohem obtížnější spočítat celkový počet uspořádání a odvodit je, což je vlastně úkol.

Je zvláštní, že mnozí autoři tento problém a jeho řešení mylně připisovali samotnému K. Gaussovi. Ve skutečnosti ji poprvé nastudoval v roce 1848 německý šachista M. Bezzel. Dr. F. Science našel 60 řešení a publikoval je v novinách „Illustrierte Zeitung“ z 1. června 1850. Teprve poté se Gauss začal o problém zajímat a našel 72 řešení, o kterých informoval v dopise svému příteli astronomovi. Schumacher z 2. září 1850. Kompletní stejný soubor řešení, sestávající z 92 pozic, obdržel stejný F. Sciences. Citoval je ve zmíněných novinách z 21. září 1850. Tuto chronologii stanovil slavný německý badatel matematické zábavy W. Arens.

Důkladný důkaz, že 92 řešení vyčerpává všechny možnosti, získal až v roce 1874 anglický matematik D. Glasher (s využitím teorie determinantů). Při pohledu do budoucna si všimneme, že existuje pouze dvanáct významných řešení (která se neshodují s odrazy a rotacemi desky).

Existuje mnoho známých způsobů, jak zorganizovat efektivní pátrání po umístění osmi mírumilovných královen (metody Permentier, La Noe, Gunther, Glasher, Laquiere atd.). Tyto metody jsou popsány v četné literatuře o zábavné matematice. V naší počítačové době by problém tohoto druhu nevzbudil takový zájem. Stačí totiž vytvořit jednoduchý program a během pár minut po jeho zadání do stroje se vytiskne všech 92 potřebných pozic.

Od každého řešení úlohy s dámou lze získat řadu dalších otočením desky o 90, 180 a 270° a také jejím zrcadlením vzhledem k čarám rozdělujícím desku na polovinu. Například z uspořádání znázorněného na Obr. a při otočení desky o 90° ve směru hodinových ručiček dostaneme uspořádání na Obr. c, a když se deska odráží vzhledem k čáře oddělující křídla krále a dámy - na Obr. d. Pomocí dalších rotací a odrazů desky lze získat dalších pět řešení.

Naznačené operace se šachovnicí tedy umožňují získat, obecně řečeno, sedm nových z jednoho uspořádání mírumilovných dam. Bylo prokázáno, že v obecném případě na desce nхn (pro n > 1) pro jakékoli uspořádání n pokojných dam jsou možné tři situace:

1) s jedním odrazem šachovnice vznikne nové uspořádání dam, ale s rotacemi a jinými odrazy se nezíská nová řešení;

2) nové řešení vzniká při otočení desky o 90° a její odrazy dávají další dvě uspořádání;

3) tři otočení desky a čtyři odrazy vedou k sedmi různým uspořádáním (a pokud počítáme to původní, tak máme celkem osm pozic).

V případě 1) se původní řešení nazývá dvojitě symetrické, v případě 2) symetrické a v případě 3) jednoduché. Pro běžnou desku je každé řešení buď jednoduché, nebo symetrické a neexistují žádná dvojitě symetrická řešení.

Sada osmi pokojných dam se nazývá základní, pokud se za prvé tato uspořádání během rotací a odrazů na šachovnici navzájem netransformují, a za druhé se z nějakého základního pomocí těchto transformací šachovnice získá jakékoli jiné uspořádání. Je dokázáno, že každá základní sada řešení problému obsahuje právě 12 uspořádání. Zde je jedna taková sada:

1) viz obr. A;

2) viz obr. b;

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

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

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

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

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

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

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

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

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

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

Zbývajících 80 formací se získá z těchto dvanácti pomocí rotací a odrazů desky. Hlavní uspořádání na Obr. b je symetrický, ostatních jedenáct základních uspořádání je jednoduchých. Celkem tedy na šachovnici máme 11·8+1·4=92 uspořádání osmi dam, které se navzájem neohrožují.

Všimněme si několika zajímavé vlastnosti umístění mírumilovných královen. Symetrické uspořádání na Obr. b, jak má být, má vnější symetrii. Vyznačuje se také tím, že střední část desky (4x4 čtverec) není obsazena královnami. Obě hlavní diagonály desky jsou zde také volné (tuto vlastnost má i osmé hlavní uspořádání). V prvním uspořádání (obr. a) nejsou žádné tři dámy na stejné přímce protažené středy polí (to znamená nejen svislice, horizontály a úhlopříčky desky, ale také přímky s jinými úhly sklonu ).

Jakékoli řešení problému osmi královen lze zapsat jako množinu (t1, t2, ј, t8), což je permutace čísel 1, 2, ј, 8. Zde ti je číslo vodorovné čáry, na které se královna i-té vertikální stojí. Protože dámy nestojí na stejné vodorovné čáře, pak jsou všechna čísla ti různá, a protože dámy nestojí na stejné diagonále, pak pro libovolné i, j (i< j Ј 8) имеем: |tj-ti| № j-i.

Čísla 1, 2, ј, 8 zapišme nejprve vzestupně a poté sestupně. Poté sečteme čísla každé z těchto dvou permutací s čísly libovolné permutace osmi čísel, například toto - (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.

Výsledné součty tvoří dvě množiny: (4, 9, 5, 12, 10, 7, 11, 14) a (11, 14, 8, 13, 9, 4, 6, 7). Zvažme následující problém.

Jaké permutace čísel od 1 do 8 vedou v důsledku naznačené operace sčítání ke dvěma takovým množinám, z nichž všechny jsou různé?

Problém osmi královen upoutal Gaussovu pozornost právě v souvislosti s tímto čistě aritmetickým problémem. Ukazuje se, že existuje vzájemná shoda mezi řešeními těchto dvou problémů. Jinými slovy, každé uspořádání osmi královen, které se navzájem neohrožují, poskytuje řešení aritmetického problému a naopak. Pro zvolenou permutaci se obě množiny skládají z různých čísel, a to není náhodné - odpovídá to prvnímu hlavnímu uspořádání (viz obr. a).

Je snadné vidět, že když se hrací deska otočí a odrazí, některá řešení se získají od jiných pomocí jednoduchých aritmetických operací na souřadnicích polí obsazených dámami. Analýza těchto operací odhalí další vlastnosti řešení, které nebudeme rozebírat.

Problém n královen. Umístěte n dam na šachovnici nxn tak, aby se navzájem neohrožovaly.

Na desce 1x1 je jedna dáma umístěna na jedno pole a existuje řešení. Na desce 2x2 jedna královna, ať stojí kdekoli, útočí na tři další pole a druhou královnu není kam umístit. Na desku 3x3 se vejdou pouze dvě mírumilovné královny. Takže pro desky 2x2 a 3x3 problém nemá řešení. Tyto dva případy jsou výjimkou. Pro všechny n > 3 lze na hrací desku nxn umístit n x n dam, které se navzájem neohrožují.

Na desce 4ґ4 je jedno hlavní uspořádání, a to dvojitě symetrické: a2, b4, c1, d3, tzn. Existují pouze dvě řešení. Na desce 5ґ5 jsou dvě hlavní formace: 1) a2, b4, c1, d3, e5; 2) a2, b5, c3, dl, e4. Celkový počet Existuje deset formací a z nich si můžete vybrat pět takových, že když se položí na sebe, 25 královen vyplní všechna pole desky 5x5.

Všimněte si, že v obecném případě může n uspořádání (řešení problému) zaplnit celou desku nxn, když jsou superponována pouze pro ta n, která nejsou násobky dvou a tří. Z toho zejména vyplývá, že pro běžnou desku nelze vybrat osm uspořádání pokrývajících všech 64 polí desky.

Zobecněním algebraické vlastnosti řešení úlohy osmi dam získáme, že uspořádání n dam (t1, t2, ј, tn) na hrací desce nґn je požadované, pokud pro jakékoli i, j (i< j Ј n) имеет место: |tj-ti| № j-i. Таким образом, задача об n ферзях сводится к чисто математической задаче о нахождении перестановки чисел 1, 2, ј, n, удовлетворяющей указанному условию. Известно много решений этой задачи, некоторые из них опубликованы в серьезных математических журналах. Один из методов расстановки n ферзей, не угрожающих друг другу на произвольной доске nґn (n і 5), можно найти в книге «Математика на шахматной доске».

Popis algoritmu a struktury programu:

Tento program implementuje rekurzivní metodu pro řešení problému 8 královen.

Máme funkci (int put_queen (int x)), která umístí další dámu na pole a zavolá se, aby umístila další, pokud nelze umístit další dámu, vrátí řízení funkci, ze které byla volána. , a to se zase snaží umístit svou královnu na jiné místo a znovu se rekurzivně volat. Když funkce umístí poslední dámu, zobrazí se uživateli výsledek umístění.

Úplně na začátku zavoláme funkci s parametrem x rovným nule (číslování začíná od 0), což znamená, že musí umístit první dámu. Když tato funkce vrátí řízení hlavní funkci, znamená to, že byly nalezeny všechny možnosti.

Pro uložení pozice dam se používá pole 8 prvků typu integer (int queens). Pořadí prvku v tomto poli znamená číslo královny a jeho x-ovou souřadnici, tedy sloupec, a jeho hodnotu - y-ovou souřadnici neboli řádek. Použijeme vlastnost, že na jednom sloupci nemůže být více královen.

První verze hádanky z roku 1850, kdy jsou na hrací ploše předinstalovány dvě královny a hráč musí umístit zbývající královny (viz dvě řešení problému pod řezem)

Problém N dam je umístit N dam na desku N×N tak, aby žádná královna nebyla napadena jinou, s několika královnami předinstalovanými na desce. To znamená, že nakonec by žádné dvě královny neměly být na stejné čáře nebo diagonále. Problém byl poprvé formulován v roce 1848 a v roce 1850 byla vynalezena verze hlavolamu, ve které je předem na plán umístěn určitý počet královen a zbytek musí hráč umístit, pokud je to možné.

Vědci z University of St Andrews (Skotsko) zveřejnili článek, který ukazuje, že problém N queens není pouze #P-úplný problém, ale také NP-úplný problém. Clay Mathematical Institute (USA) je navíc připraven zaplatit milion dolarů každému, kdo dokáže optimalizovat řešení tohoto problému jako problému, aby dokázal P=NP.

Jak je známo, v teorii složitosti je #P třída problémů, jejichž řešením je počet úspěšných, tedy končících v přijímání stavů, výpočetních cest pro určitý nedeterministický Turingův stroj pracující v polynomiálním čase. Výpočtové problémy třídy #P (problémy počítání) jsou spojeny s odpovídajícími problémy řešitelnosti (rozhodovacími problémy) třídy NP.

Vědci poznamenávají, že tento problém může být nejjednodušší mezi NP-úplnými problémy, aby vysvětlil podstatu těchto problémů každému, kdo zná pravidla šachu. Tento úkol je obecně velmi zajímavý příběh. Svého času to přitáhlo pozornost Gausse, který při řešení udělal i malou chybu (na desce 8x8 nahlásil 76 řešení, ale pak sám přiznal, že čtyři z nich byla špatná, takže zbylo jen 72 a později Gauss vytvořil všech 92 řešení pro desku 8x8).

Zobecnění problému na desku N×N přitáhlo pozornost mnoha matematiků. Za poslední půlstoletí bylo publikováno několik desítek vědeckých prací věnovaných tomuto problému. Nejméně šest z nich bylo ve službě Google Scholar citováno více než 400krát: Golomb & Baumert, 1965; Bitner & Reingold, 1975; Mackworth & Freuder, 1985; Minton, Johnston, Philips a Laird, 1992; Selman, Levesque & Mitchell, 1992; Crawford, Ginsberg, Luks a Roy, 1996.

Složitost problému N královen je často špatně posuzována. Dokonce i v široce citovaných článcích je často nazýván NP-těžký problém, ale bude tomu tak pouze v případě, že P=NP. Ve skutečnosti je výpočetní verzí problému, tedy určení počtu řešení pro N královen, sekvence A000170 z Online Encyclopedia of Integer Sequences. Tato sekvence je nyní známá pro maximum n=27, kde počet řešení přesahuje 2,34×1017. Nic jiného není známo efektivní řešení problémy než obyčejná hrubá síla. Pro n=27 v roce 2016 bylo tedy použito rozsáhlé paralelní vyhledávání na FPGA.

Zároveň, pokud počítač začne vypočítávat možné pozice dam na desce 1000×1000 buněk, pak bude tímto úkolem navždy zatížen. Podle vědců, pokud někdo najde opravdu rychle a účinná metodařešení, bude z něj moci těžit mnohem více než jeden milion dolarů od Clay Mathematics Institute. „Pokud napíšete program, který dokáže vyřešit problém opravdu rychle, můžete jej upravit tak, aby vyřešil mnoho důležitých problémů, kterým čelíme každý den,“ říká profesor informatiky Ian Gent, jeden z autorů. vědecká práce. - Mezi nimi jsou triviální problémy, jako je najít nejvíce velká skupina vaši přátelé na Facebooku, kteří se navzájem neznají, nebo velmi důležité úkoly, jako je prolomení kódů, které udržují všechny naše online transakce v bezpečí.“

Ale to jsou čistě teoretické spekulace. V praxi se zatím nikdo nepřiblížil k rychlému a efektivnímu řešení problému N královen. Pokud prokážete, že existuje efektivnější způsob, jak vyřešit problém, než jednoduše vyzkoušet všechny možnosti, získáte milion dolarů.