Osm královen puzzle - Eight queens puzzle
A | b | C | d | E | F | G | h | ||
8 | ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() | 8 | |||||||
7 | 7 | ||||||||
6 | 6 | ||||||||
5 | 5 | ||||||||
4 | 4 | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
A | b | C | d | E | F | G | h |
The osm královen puzzle je problém umístit osm šachy královny na 8 × 8 šachovnice aby se žádné dvě královny navzájem neohrožovaly; Řešení tedy vyžaduje, aby žádné dvě královny nesdílely stejný řádek, sloupec nebo úhlopříčku. Puzzle s osmi královnami je příkladem obecnějšího n královny problém umístění n neútočící královny na n×n šachovnice, pro které existují řešení pro všechna přirozená čísla n s výjimkou n = 2 a n = 3.[1]
Dějiny
Šachový skladatel Max Bezzel zveřejnil v roce 1848 puzzle s osmi královnami. Franz Nauck zveřejnil první řešení v roce 1850.[2] Nauck také rozšířil skládačku na n královny problém, s n královny na šachovnici n×n čtverce.
Od té doby mnoho matematici, počítaje v to Carl Friedrich Gauss, Pracovali jak na osmi královnách, tak na jejich zobecněné skládačce n- čte verzi. V roce 1874 Gunther navrhl použití metody determinanty najít řešení.[2] J.W.L. Glaisher vylepšil Guntherův přístup.
V roce 1972 Edsger Dijkstra použil tento problém k ilustraci síly toho, co nazval strukturované programování. Publikoval velmi podrobný popis a nejdříve do hloubky algoritmus zpětného sledování.2
Konstruování a počítání řešení
Problém s nalezením všech řešení problému s 8 královnami může být výpočetně docela nákladný, protože jich je 4 426 165 365 (tj. 64C8 ) možná uspořádání osmi královen na desce 8 × 8, ale pouze 92 řešení. Je možné použít klávesové zkratky, které snižují výpočetní požadavky nebo pravidla, kterým se vyhýbáme výpočetní techniky hrubou silou. Například uplatněním jednoduchého pravidla, které omezuje každou královnu na jeden sloupec (nebo řádek), ačkoli je stále považován za hrubou sílu, je možné snížit počet možností na 16 777 216 (tj. 88) možné kombinace. Generování obměny dále snižuje možnosti na pouhých 40 320 (tj. 8! ), které jsou poté zkontrolovány na diagonální útoky.
Řešení
Puzzle s osmi královnami má 92 odlišných řešení. Pokud se řešení, která se liší pouze podle symetrie operace otáčení a odrazu desky se počítají jako jedna, skládačka má 12 řešení. Tito se nazývají základní řešení; zástupci každého z nich jsou uvedeny níže.
Základní řešení má obvykle osm variant (včetně své původní podoby) získaných otočením o 90, 180 nebo 270 ° a následným odražením každé ze čtyř rotačních variant do zrcadla v pevné poloze. Pokud by však řešení bylo ekvivalentní jeho vlastní rotaci o 90 ° (jako je tomu u jednoho řešení s pěti královnami na desce 5 × 5), bude mít toto základní řešení pouze dvě varianty (samo o sobě a jeho odraz). Pokud by řešení bylo ekvivalentní jeho vlastní rotaci o 180 ° (ale ne její 90 ° rotaci), bude mít čtyři varianty (samo a jeho odraz, jeho 90 ° rotace a jeho odraz). Li n > 1, není možné, aby řešení bylo ekvivalentní jeho vlastní reflexi, protože to by vyžadovalo, aby dvě královny byly proti sobě. Z 12 základních řešení problému s osmi královnami na desce 8 × 8 se právě jedno (řešení 12 níže) rovná jeho vlastní rotaci o 180 ° a žádné se nerovná její rotaci o 90 °; počet odlišných řešení je tedy 11 × 8 + 1 × 4 = 92.
Všechna základní řešení jsou uvedena níže:
Řešení 1
|
Řešení 2
|
Řešení 3
|
Řešení 4
|
Řešení 5
|
Řešení 6
|
Řešení 7
|
Řešení 8
|
Řešení 9
|
Řešení 10
|
Řešení 11
|
Řešení 12
|
Řešení 10 má další vlastnost, která žádné tři královny nejsou v přímce.
Existence řešení
Tyto algoritmy hrubou silou pro počítání počtu řešení jsou výpočetně zvládnutelné n = 8, ale byl by neřešitelný pro problémy s n ≥ 20, jako 20! = 2,433 × 1018. Pokud je cílem najít jediné řešení, lze ukázat, že existují řešení pro všechny n ≥ 4 bez jakéhokoli vyhledávání.[3]Tato řešení vykazují stupňovité vzory, jak je uvedeno v následujících příkladech n = 8, 9 a 10:
Schodišťové řešení pro 8 královen
|
Schodišťové řešení pro 9 královen
|
Schodišťové řešení pro 10 královen
|
Výše uvedené příklady lze získat pomocí následujících vzorců.[3] Nechť (i, j) je čtverec ve sloupci i a řádek j na n × n šachovnice, k celé číslo.
Jeden přístup[3] je
- Pokud se zbytek dělí n o 6 není 2 nebo 3, pak je seznam jednoduše sudá čísla následovaná všemi lichými čísly ne většími než n.
- Jinak napište samostatné seznamy sudých a lichých čísel (2, 4, 6, 8 - 1, 3, 5, 7).
- Pokud je zbytek 2, vyměňte 1 a 3 v lichém seznamu a přesuňte 5 na konec (3, 1, 7, 5).
- Pokud je zbytek 3, přesuňte 2 na konec sudého seznamu a 1,3 na konec lichého seznamu (4, 6, 8, 2 – 5, 7, 1, 3).
- Připojte lichý seznam k sudému seznamu a umístěte královny do řádků daných těmito čísly zleva doprava (a2, b4, c6, d8, e3, f1, g7, h5).
Pro n = 8 výsledkem je zásadní řešení 1 výše. Následuje několik dalších příkladů.
- 14 královen (zbytek 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
- 15 královen (zbytek 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
- 20 královen (zbytek 2): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 9, 11, 13, 15, 17, 19, 5.
Počítání řešení
V následujících tabulkách je uveden počet řešení pro umístění n královny na n × n deska, obě základní (sekvence A002562 v OEIS ) a vše (sekvence A000170 v OEIS ).
n | základní | Všechno |
---|---|---|
1 | 1 | 1 |
2 | 0 | 0 |
3 | 0 | 0 |
4 | 1 | 2 |
5 | 2 | 10 |
6 | 1 | 4 |
7 | 6 | 40 |
8 | 12 | 92 |
9 | 46 | 352 |
10 | 92 | 724 |
11 | 341 | 2,680 |
12 | 1,787 | 14,200 |
13 | 9,233 | 73,712 |
14 | 45,752 | 365,596 |
15 | 285,053 | 2,279,184 |
16 | 1,846,955 | 14,772,512 |
17 | 11,977,939 | 95,815,104 |
18 | 83,263,591 | 666,090,624 |
19 | 621,012,754 | 4,968,057,848 |
20 | 4,878,666,808 | 39,029,188,884 |
21 | 39,333,324,973 | 314,666,222,712 |
22 | 336,376,244,042 | 2,691,008,701,644 |
23 | 3,029,242,658,210 | 24,233,937,684,440 |
24 | 28,439,272,956,934 | 227,514,171,973,736 |
25 | 275,986,683,743,434 | 2,207,893,435,808,352 |
26 | 2,789,712,466,510,289 | 22,317,699,616,364,044 |
27 | 29,363,495,934,315,694 | 234,907,967,154,122,528 |
Puzzle šesti královen má méně řešení než puzzle pěti královen.
Neexistuje žádný známý vzorec pro přesný počet řešení nebo dokonce pro jeho asymptotické chování. Deska 27 × 27 je deska nejvyššího řádu, která byla zcela vyjmenována.[4]
Související problémy
- Vyšší rozměry
- Najděte počet neútočících královen, které lze umístit do a d-dimenzionální šachy prostor velikosti n. Více než n královny lze umístit do některých vyšších dimenzí (nejmenším příkladem jsou čtyři neútočící královny v šachovém prostoru 3 × 3 × 3) a je ve skutečnosti známo, že k, kde jsou vyšší dimenze nk královny nestačí k útoku na všechna pole.[5][6]
- Používání jiných kousků než královen
- Na desku 8 × 8 lze umístit 32 rytíři nebo 14 biskupové, 16 králové nebo osm havrani, takže žádné dva kusy na sebe neútočí. Pohádkové šachové figurky byly také nahrazeny královnami. V případě rytířů je snadným řešením umístit jeden na každý čtverec dané barvy, protože se pohybují pouze k opačné barvě. Řešení je také snadné pro věže a krále. Osm věží lze umístit podél dlouhé úhlopříčky (mezi tisíce dalších řešení) a 16 králů se umístí na hrací plochu tak, že ji rozdělí na 2 na 2 čtverce a na každé pole umístí krále na ekvivalentní body.
- Šachové variace
- Lze požádat o související problémy šachové variace jako shogi. Například n+k problém dračích králů žádá o místo k šógi pěšci a n+k vzájemně neatakující dračí králové na n×n shogi deska.[7]
- V matematice lze permutační matici považovat geometricky za množinu n body ležící na čtvercích a n×n šachovnice, takže každý řádek nebo sloupec obsahuje pouze jeden bod. Objednávka tedyn permutační matice je řešením n-rooks puzzle.
- Nestandardní desky
- Pólya studoval n královny problém na a toroidní („ve tvaru koblihy“) a ukázal, že na řešení je řešení n×n nastoupit tehdy a jen pokud n není dělitelné 2 nebo 3.[8] V roce 2009 Pearson a Pearson algoritmicky naplnili trojrozměrné desky (n×n×n) s n2 královny, a navrhl, že jejich násobky mohou přinést řešení pro čtyřrozměrnou verzi skládačky.[9][je zapotřebí lepší zdroj ]
- Nadvláda
- Vzhledem k n×n deska, dominantní číslo je minimální počet královen (nebo jiných figurek) potřebných k útoku nebo obsazení každého pole. Pro n = 8 číslo dominance královny je 5.[10][11]
- Královny a další kousky
- Varianty zahrnují míchání královen s jinými kousky; například umisťování m královny a m rytíři na n×n tak, aby žádný kousek neútočil na jiného[12] nebo umístění královen a pěšců tak, aby na sebe nenapadly dvě královny.[13][je zapotřebí lepší zdroj ]
- V roce 1992 Demirörs, Rafraf a Tanik zveřejnili metodu převodu některých magických čtverců na n-řeší řešení a naopak.[14]
- V n×n matice, umístěte každou číslici 1 až n v n umístění v matici tak, aby žádné dvě instance stejné číslice nebyly ve stejném řádku nebo sloupci.
- Zvažte matici s jedním primárním sloupcem pro každý z n řady desky, jeden primární sloup pro každou z n soubory a jeden sekundární sloupec pro každý ze 4n - 6 netriviálních úhlopříček desky. Matice má n2 řádky: jeden pro každé možné umístění královny a každý řádek má ve sloupcích 1 odpovídající hodnosti, souboru a úhlopříčkám daného čtverce a 0 ve všech ostatních sloupcích. Pak n queens problem is ekvivalent to selecting a subset of the lines of this matrix such that every primary column has a 1 in exactly one of the selected lines and every secondary column has a 1 in at most one of the selected lines; toto je příklad zobecněného přesný obal problém, z toho sudoku je dalším příkladem.
- n- Dokončení královen
- Dokument z roku 2017[15] vyšetřoval problém „Vzhledem k n×n šachovnici, na které jsou již umístěny nějaké královny, můžete umístit královnu do každé zbývající řady tak, aby na sebe nenapadly žádné dvě královny? “a několik souvisejících problémů. Autoři tvrdili, že tyto problémy jsou NP-kompletní[16] a # P-kompletní.
Cvičení v návrhu algoritmu
Nalezení všech řešení skládačky osmi královen je dobrým příkladem jednoduchého, ale netriviálního problému. Z tohoto důvodu se často používá jako ukázkový problém pro různé programovací techniky, včetně netradičních přístupů, jako je programování omezení, logické programování nebo genetické algoritmy. Nejčastěji se používá jako příklad problému, který lze vyřešit pomocí a rekurzivní algoritmus, frázováním n queens problém indukčně, pokud jde o přidání jediné královny k jakémukoli řešení problému umisťování n-1 královen na n×n šachovnice. The indukce zdola s řešením „problému“ s umístěním 0 královen na šachovnici, což je prázdná šachovnice.
Tuto techniku lze použít způsobem, který je mnohem efektivnější než naivní vyhledávání hrubou silou algoritmus, který zohledňuje všech 648 = 248 = 281 474 976 710 656 možných slepých umístění osmi královen, a poté je filtruje, aby odstranila všechna umístění, která umisťují dvě královny buď na stejné pole (ponechává pouze 64! / 56! = 178 462 987 637 760 možných umístění), nebo na vzájemně útočící pozice. Tento velmi špatný algoritmus bude mimo jiné produkovat stejné výsledky znovu a znovu ve všech různých obměny úkolů osmi královen, stejně jako opakování stejných výpočtů znovu a znovu pro různé dílčí sady každého řešení. Lepší algoritmus hrubé síly umisťuje do každé řady jednu královnu, což vede pouze k 88 = 224 = 16 777 216 slepých umístění.
Je možné toho dosáhnout mnohem lépe. Osm vyřeší jeden algoritmus havrani skládáním generováním permutací čísel 1 až 8 (kterých je 8! = 40 320) a použije prvky každé permutace jako indexy k umístění královny na každý řádek. Poté odmítne ty desky s úhlopříčnými útočnými pozicemi. ustoupit hloubkové vyhledávání program, mírné zlepšení permutační metody, vytváří vyhledávací strom zvážením jedné řady desky po druhé, eliminací většiny pozic desky, které nejsou ve velmi rané fázi jejich konstrukce. Protože odmítá útoky rooků a diagonál i na neúplné desky, zkoumá pouze 15 720 možných umístění královen. Další vylepšení, které zkoumá pouze 5 508 možných umístění královen, je kombinovat metodu založenou na permutaci s metodou předčasného prořezávání: permutace se generují nejdříve do hloubky a prohledávací prostor se prořezává, pokud částečná permutace vytváří adiagonální útok.Omezení programování může být na tento problém také velmi efektivní.

Alternativou k vyčerpávajícímu vyhledávání je algoritmus „iterativní opravy“, který obvykle začíná u všech královen na desce, například u jedné královny na sloupec.[17] Poté spočítá počet konfliktů (útoků) a pomocí heuristiky určí, jak zlepšit umístění královen. 'minimální konflikty ' heuristický - přesunutí kousku s největším počtem konfliktů na čtverec ve stejném sloupci, kde je počet konfliktů nejmenší - je obzvláště efektivní: najde řešení problému 1 000 000 královen v průměru za méně než 50 kroků. To předpokládá, že počáteční konfigurace je „přiměřeně dobrá“ - pokud milion královen začne ve stejném řádku, bude to trvat alespoň 999 999 kroků, než ji opravit. „Poměrně dobrý“ výchozí bod lze najít například tak, že každou královnu umístíte do jejího vlastního řádku a sloupce tak, aby byla v konfliktu s nejmenším počtem královen, které jsou již na desce.
Na rozdíl od výše uvedeného vyhledávání zpětného sledování iterativní oprava nezaručuje řešení: jako všechny chamtivý postupy, může se zaseknout na místním optimu. (V takovém případě může být algoritmus restartován s jinou počáteční konfigurací.) Na druhou stranu může vyřešit velikost problému, který přesahuje hloubkové hledání o několik řádů.
Tato animace ilustruje ustoupit vyřešit problém. Královna je umístěna ve sloupci, o kterém je známo, že nezpůsobuje konflikt. Pokud sloupec nebyl nalezen, program se vrátí do posledního dobrého stavu a poté zkusí jiný sloupec.
Jako alternativu k zpětnému sledování lze řešení počítat rekurzivním výčtem platných dílčích řešení, jeden řádek po druhém. Namísto vytváření celých pozic desky jsou blokované úhlopříčky a sloupy sledovány bitovými operacemi. To neumožňuje obnovení jednotlivých řešení.[18][19]
Ukázkový program
Toto je a Pascal programovat Niklaus Wirth v roce 1976.[20] Najde jedno řešení problému s osmi královnami.
program osmikrálovna1(výstup); var i : celé číslo; q : booleovský; A : pole[ 1 .. 8] z booleovský; b : pole[ 2 .. 16] z booleovský; C : pole[ −7 .. 7] z booleovský; X : pole[ 1 .. 8] z celé číslo; postup Snaž se( i : celé číslo; var q : booleovský); var j : celé číslo; začít j := 0; opakovat j := j + 1; q := Nepravdivé; -li A[ j] a b[ i + j] a C[ i − j] pak začít X[ i ] := j; A[ j ] := Nepravdivé; b[ i + j] := Nepravdivé; C[ i − j] := Nepravdivé; -li i < 8 pak začít Snaž se( i + 1, q); -li ne q pak začít A[ j] := skutečný; b[ i + j] := skutečný; C[ i − j] := skutečný; konec konec jiný q := skutečný konec dokud q nebo (j = 8); konec; začítpro i := 1 na 8 dělat A[ i] := skutečný;pro i := 2 na 16 dělat b[ i] := skutečný;pro i := −7 na 7 dělat C[ i] := skutečný;Snaž se( 1, q);-li q pak pro i := 1 na 8 dělat psát si( X[ i]:4);writelnkonec.
Viz také
Reference
- ^ E. J. Hoffman a kol., „Konstrukce pro řešení problému m královen“. Matematický časopis, Sv. XX (1969), s. 66–72. [1]
- ^ A b W. W. Rouse Ball (1960) "The Eight Queens Problem", in Matematické rekreace a eseje„Macmillan, New York, s. 165–171.
- ^ A b C Bo Bernhardsson (1991). "Explicitní řešení problému N-královen pro všechny N". SIGART Bull. 2 (2): 7. doi:10.1145/122319.122322.
- ^ Projekt Q27
- ^ J. Barr a S. Rao (2006), The n-Queens Problem in Higher Dimensions, Elemente der Mathematik, sv. 61 (4), str. 133–137.
- ^ Martin S.Pearson. „Královny na šachovnici - za druhou dimenzí“ (php). Citováno 27. ledna 2020.
- ^ Chatham, Doug (1. prosince 2018). „Úvahy o problému n + k dračích králů“. Rekreační matematický časopis. 5 (10): 39–55. doi:10,2478 / rmm-2018-0007.
- ^ G. Pólya, Uber die "doppelt-periodischen" Losungen des n-Damen-Problems, George Pólya: Collected papers Vol. IV, G-C. Rota, ed., MIT Press, Cambridge, London, 1984, str. 237–247
- ^ [2]
- ^ Burger, A. P .; Cockayne, E. J .; Mynhardt, C. M. (1997), „Nadvláda a nesčetnost v grafu královen“, Diskrétní matematika, 163 (1–3): 47–66, doi:10.1016 / 0012-365X (95) 00327-S, hdl:1828/2670, PAN 1428557
- ^ Weakley, William D. (2018), „Královny po celém světě za dvacet pět let“, Gera, Ralucca; Haynes, Teresa W.; Hedetniemi, Stephen T. (eds.), Teorie grafů: Oblíbené dohady a otevřené problémy - 2, Problem Books in Mathematics, Cham: Springer, str. 43–54, doi:10.1007/978-3-319-97686-0_5, PAN 3889146
- ^ „Problém s královnami a rytíři“. Archivovány od originál dne 16. října 2005. Citováno 20. září 2005.
- ^ Problém s devíti královnami
- ^ O. Demirörs, N. Rafraf a M.M. Tanik. Získání řešení n-královen z magických čtverců a konstrukce magických čtverců z řešení n-královen. Journal of Recreational Mathematics, 24: 272–280, 1992
- ^ Gent, Ian P .; Jefferson, Christopher; Slavík, Peter (srpen 2017). "Složitost n- Dokončení královen “. Journal of Artificial Intelligence Research. 59: 815–848. doi:10.1613 / jair.5512. ISSN 1076-9757. Citováno 7. září 2017.
- ^ „Puzzle 8 královen“. www.claymath.org. Hliněný matematický institut. 2. září 2017.
- ^ Polynomiální časový algoritmus pro problém N-královny Rok Sosic a Jun Gu, 1990. Popisuje dobu běhu až 500 000 královen, což bylo maximum, které mohli spustit kvůli paměťovým omezením.
- ^ Qiu, Zongyan (únor 2002). Msgstr "Bitové vektorové kódování problému n-královny". Oznámení ACM SIGPLAN. 37 (2): 68–70. doi:10.1145/568600.568613.
- ^ Richards, Martin (1997). Backtracking Algorithms in MCPL using Bit Patterns and Recursion (PDF) (Technická zpráva). Počítačová laboratoř University of Cambridge. UCAM-CL-TR-433.
- ^ Wirth, 1976, str. 145
Další čtení
- Bell, Jordan; Stevens, Brett (2009). "Průzkum známých výsledků a oblastí výzkumu pro n- čte ". Diskrétní matematika. 309 (1): 1–31. doi:10.1016 / j.disc.2007.12.043.
- Watkins, John J. (2004). Obecně: Matematika šachových problémů. Princeton: Princeton University Press. ISBN 978-0-691-11503-0.
- O.-J. Dahl, E. W. Dijkstra, C. A. R. Hoare Strukturované programování, Academic Press, Londýn, 1972 ISBN 0-12-200550-3 viz str. 72–82, kde Dijkstra řeší problém 8 královen.
- Allison, L .; Yee, C.N .; McGaughey, M. (1988). „Trojrozměrné problémy s NxN-královnami“. Katedra informatiky, Monash University, Austrálie.
- Nudelman, S. (1995). „Problém modulárních N-královen ve vyšších dimenzích“. Diskrétní matematika. 146 (1–3): 159–167. doi:10.1016 / 0012-365X (94) 00161-5.
- Engelhardt, M. (srpen 2010). „Der Stammbaum der Lösungen des Damenproblems (v němčině znamená Rodokmen grafů řešení problému s 8 královnami)“. Spektrum der Wissenschaft: 68–71.
- K problému modulární N-královny ve vyšších dimenzích „Ricardo Gomez, Juan Jose Montellano a Ricardo Strausz (2004), Instituto de Matematicas, Area de la Investigacion Cientifica, Circuito Exterior, Ciudad Universitaria, Mexiko.
- Wirth, Niklausi (1976), "Algoritmy + datové struktury = programy", Série Prentice-Hall v automatickém výpočtu, Prentice-Hall, Bibcode:1976adsp.book ..... W, ISBN 978-0-13-022418-7
externí odkazy
- Weisstein, Eric W. „Queens Problem“. MathWorld.
- královny-CPM na GitHub Osm královen v Turbo Pascalu za CP / M
- eight-queens.py na GitHub Eight Queens Puzzle one line solution in Python
- Řešení ve více než 100 různých programovacích jazycích (na Rosettský kód )