Преглед на кодот на Проблем со осум дами

{{Шаховски дијаграм|=
| tright
|
|=

 8 |  |  |  |  |  |  |  |ql|=
 7 |  |  |  |ql|  |  |  |  |=
 6 |ql|  |  |  |  |  |  |  |=
 5 |  |  |ql|  |  |  |  |  |=
 4 |  |  |  |  |  |ql|  |  |=
 3 |  |ql|  |  |  |  |  |  |=
 2 |  |  |  |  |  |  |ql|  |=
 1 |  |  |  |  |ql|  |  |  |=
    a  b  c  d  e  f  g  h
| Едно од можните решенија на проблемот
}}

'''Проблем со осум дами''' — [[шах]]овско-[[математичка]] загатка, која се состои во поставување на осум [[Дама (шах)|дами]] на една [[шаховска табла]], така што ниту една од дамите да не биде нападната и да не напаѓа друга дама според [[Шаховски правила|шаховските правила]]. Бојата на фигурите е безначајна и се претпоставува дека сите фигури меѓусебно се противници. Со други зборови, со проблемот се бара да нема две или повеќе дами по ист ред, линија или дијагонала на шаховската табла.

Проблемот може да се постави на шаховска табла со која било големина, па така n дами треба да се постават на табла со димензии n×n. На вообичаена шаховска табла, каде што n=8, проблемот има 92 различни решенија. Доколку се анемарат решенијата кои се разликуваат само со [[пресликување]] и [[ротација]], остануваат само 12 решенија.

== Историја ==
За првпат, проблемот со дамите бил формулиран од страна на германскиот шаховски мајстор, [[Макс Бецел]]. Во 1848 година, во списанието „[[Deutsche Schachzeitung]]“ бил побаран одговор на бројот на можни решенија на проблемот. Прв кој го дал точниот број на решенија, кој изнесува 92, бил Франц Наук, кој во 1850 година, својот одговор го објавил во списанието „[[Illustrirte Zeitung]]“. Понеговата појава, многу видни математичари се заинтересирале за проблемот, вклучуваји го и [[Карл Фридрих Гаус]].<ref>{{Наведена мрежна страница |url=http://theory.cs.uvic.ca/amof/e_queeI.htm |title=Information on the n Queens problem |accessdate=2010-11-19 |archive-date=2007-12-14 |archive-url=https://web.archive.org/web/20071214155015/http://theory.cs.uvic.ca/amof/e_queeI.htm |url-status=dead }}</ref> Во 1874 година, англискиот математичар, [[Џејмс Витбрид Ле Глејшер]], докажал дека нема повеќе решенија на проблемот.<ref>Evgeni J. Gik: ''Schach und Mathematik''. Verlag Deutsch Harri GmbH, ISBN 3-87144-987-3.</ref> Со тоа, почетнозададениот проблем бил целосно решен.

Наук бил првиот којшто проблемот го проширил со n дами на табла со димензии n x n.

Во 1991 година, Бернардсон, работејќи на SIGART Bulletin, Vol. 2, No. 7 во [[Асоцијација на сметачки машини|Асоцијацијата на сметачки машини]], пронашол единствено решение на проблемот со n дами на која било посакувана големина на шаховската табла.

Во 1992 година, Демирерс, Ратраф и Таник ја пронашле врската меѓу [[Магичен квадрат|магичните квадрати]] и проблемот со дамите.

Проблемот се појавува и во компјутерските игри: ''[[The 7th Guest]]'' и ''[[The Whispered World]]''. Во популарниот насов за [[Nintendo DS]], ''[[Професор Лејтон и љубопитното село]]'', од играчот се бара решение на проблемот во различен облик.

== Начин на решавање ==
Проблемот претставува одличен пример за едноставно зададен проблем со нетривијални решенија. Првиот ред од програмерските техники е доволен за да се пронајдат сите решенија. Класичен начин за решавање на проблемот е со примена на [[Рекурзија|рекурзивно]] [[прелистување со повторување]]. Ова има особено едноставна примена со употребата на [[логичко програмирање]]. Друга можност претставуваат [[Генетски алгоритам|генетските алгоритми]].

Овие обиди се значително поефикасни од алгоритамот со метод на [[целосна обработка]], којшто за било која вредност на променливата n, ги обработува сите можни позиции кои може да настанат со пставување на осумте дами, така што ниту една од нив да не напаѓа и да не е нападната од друга дама. Со овој алгоритам, бројот на исти решенија се смета повеќепати, кога постојат [[Пермутација|пермутации]] на дамите на исти полиња.

Ефикасниот алгоритам со методот на целосна обработка сместува по една дама во секој ред, притоа намалувајќи ја коплексноста на можните позиции, кој изнесува 8<sup>8</sup> = 2<sup>24</sup>.

=== Рекурзивно прелистување со повторување ===
[[Податотека:Eight-queens-animation.gif|мини|десно|230п|Анимација на работата на алгоритмот со рекурзивно прелистување со повторување]]
Проблемот има нетривијални решенија и може да се реши со рекурзивен [[алгоритам]], во којшто проблемот со n дами е претставен така што важи додавањето на нова дама на секое решение на проблемот за n-1 дама. На крајот на краиштата, секој проблем со дами започнува со проблем со 0 дами, што всушност претставува празна шаховска табла.

Шаховска табла со димензии n×n станува рекурзивна на помали табли со постојано намалување на бројот на редови: n×(n−1), n×(n−2). Програмот, директно го користи правилото дека две дами не може да се најдат во ист ред. Освен тоа, се користи и тврдењето дека решението на проблемот со n-1 дама на табла со димензии n×(n−1) мора да го содржи решението со n−2 дами на табла со димензии n×(n−2).{{ref label|Б|б|б}}

Значи, алгоритамот ги пронаоѓа сите решенија, употребувајќи ги решенијата на проблемот со помалку дами на помала табла. За да се осигури дека решенијата на помалите табли се без конфликти, овој алгоритам заштедува проверување на многу позиции. За вообичаена големина на шаховската табла, се проверуваат само 15.720 позиции.

=== Едноставно решение ===
{{Шаховски дијаграм|=
| tright
|
|=

 8 |  |  |  |ql|  |  |  |  |=
 7 |  |  |  |  |  |ql|  |  |=
 6 |  |  |  |  |  |  |  |ql|=
 5 |  |ql|  |  |  |  |  |  |=
 4 |  |  |  |  |  |  |ql|  |=
 3 |ql|  |  |  |  |  |  |  |=
 2 |  |  |ql|  |  |  |  |  |=
 1 |  |  |  |  |ql|  |  |  |=
    a  b  c  d  e  f  g  h
| Решение на проблемот со примена на Бернардсоновиот алгоритам
}}
Посебно решение на проблемот за која било големина на таблата, нуди алгоритмот развиен од страна на Бо Бернардсон.<ref>Bo Bernhardsson: ''Explicit solutions to the N-queens problem for all N'', ACM SIGART Bulletin 2/2, 1991.</ref>

Така, за [[парен број]] како вердност на променливата n, се започнува со поставување на дама во полето од втората колона и најгорниот ред. Следната дама се поставува во полето од колоната, која е две колони десно од претходната, и еден ред подолу. Постапката се повторува, сè додека не се пополнат половина од колоните. Колоните од долниот дел на таблата се пополнуваат на ист начин, со симетрично [[пресликување]] на оние од горниот дел.

Сепак, ова не води до решението, па решението произлегува од поставувањето дама во n/2. колона од најгорниот ред. Поставувањето на останатите дами продолжува на начинот предложен од Бернардсон, но мора да се напомене дека со достигнување на работ на таблата, следната дама се поставува во полето од колоната лево и два реда подолу. Со тоа се пополнети половина од колоните на таблата, а остатокот се пополнува на ист начин, со симетрично пресликување.

За [[непарен број]] како вредност на n, до решението се доаѓа со примена на истите правила, со таа разлика што поставувањето на првата дема се прави во средната колона од најгорниот ред, а при пресликувањето се започнава со поставување на дама во n-1. колона. Последната дама се поставува во аголот од таблата, кои го образуваат слободниот ред и слободната колона.

=== Други методи ===
Освен наведените, проблемот може да се реши со [[програмирање со ограничувања]] и примена на итеративен поправен алгоритам.

Програмирањето со ограничувања се употребува за решавање на задачи со поставување на ограничувања, меѓу кои се вбројува и проблемот со осум дами, кој на овој начин може да биде целосно формулиран, а неговите решенија може брзо и лесно да се пронајдат и за многу големи димензии на шаховската табла.

Со итеративниот поправен алгоритам, најпвин се започнува со која било позиција со поставеност на дамите на таблата. Потоа, се пресметува бројот на конфликти и со преместување на дамите се прави обид, нивниот број да се намали. Ефикасноста е во преместувањето на дамата со најмногу конфликти вертикално во позицијата, во која се појавува помал број на конфликти. Со овој метод, може да се реши проблем со 1.000.000 дами, произлезен од „разумна“ позиција. Така големите табли не овозможуваат решавање на проблемот со единствен создаден алгоритам, бидејќи се претпоставува појавата на тривијани решенија. Воопшто еден ваков итеративен алгоритам не може со сигурност да го пронајде решението.

== Број на решенија ==
=== Класичен проблем ===
Проблемот со осумте дами, зададен на вообичаената шаховска табла има 92 различни решенија. Но, доколку се изврши [[пресликување]] и [[ротација]] на позицијата на шаховската табла, остануваат само 12 различни решенија, при што различните бои на полињата не се земаат предвид. Од овој намален број решенија, со 4 пресликувања по редовите, линиите и дијагоналите, и 4 ротации, може да се претпостави вкупен број од 8×12=96 решенија. Но со ротација од 180°, едно од решенијата се појавува 4 пати, од што произлегува вкупниот број од 92 решенија.

{{Hidden
 |title = Приказ на дванаесетте решенија на проблемот
 |content = 
<table>
<tr>
<td>
{{Шаховски дијаграм|=
| tright
|
|=

8  |__|__|__|ql|__|__|__|__|=
7  |__|__|__|__|__|__|ql|__|=
6  |__|__|ql|__|__|__|__|__|=
5  |__|__|__|__|__|__|__|ql|=
4  |__|ql|__|__|__|__|__|__|=
3  |__|__|__|__|ql|__|__|__|=
2  |ql|__|__|__|__|__|__|__|=
1  |__|__|__|__|__|ql|__|__|=
|Решение бр. 1
}}
</td>
<td>
{{Шаховски дијаграм|=
| tright
|
|= q1

8  |__|__|__|__|ql|__|__|__|=
7  |__|ql|__|__|__|__|__|__|=
6  |__|__|__|ql|__|__|__|__|=
5  |__|__|__|__|__|__|ql|__|=
4  |__|__|ql|__|__|__|__|__|=
3  |__|__|__|__|__|__|__|ql|=
2  |__|__|__|__|__|ql|__|__|=
1  |ql|__|__|__|__|__|__|__|=
|Решение бр. 2
}}
</td>
<td>
{{Шаховски дијаграм|=
| tright
|
|=

8  |__|__|__|ql|__|__|__|__|=
7  |__|ql|__|__|__|__|__|__|=
6  |__|__|__|__|__|__|ql|__|=
5  |__|__|ql|__|__|__|__|__|=
4  |__|__|__|__|__|ql|__|__|=
3  |__|__|__|__|__|__|__|ql|=
2  |__|__|__|__|ql|__|__|__|=
1  |ql|__|__|__|__|__|__|__|=
|Решение бр. 3
}}
</td>
</tr>
<tr>
<td>
{{Шаховски дијаграм|=
| tright
|
|=

8  |__|__|__|ql|__|__|__|__|=
7  |__|__|__|__|__|ql|__|__|=
6  |__|__|__|__|__|__|__|ql|=
5  |__|__|ql|__|__|__|__|__|=
4  |ql|__|__|__|__|__|__|__|=
3  |__|__|__|__|__|__|ql|__|=
2  |__|__|__|__|ql|__|__|__|=
1  |__|ql|__|__|__|__|__|__|=
|Решение бр. 4
}}
</td>
<td>
{{Шаховски дијаграм|=
| tright
|
|=

8  |__|__|ql|__|__|__|__|__|=
7  |__|__|__|__|__|ql|__|__|=
6  |__|__|__|__|__|__|__|ql|=
5  |ql|__|__|__|__|__|__|__|=
4  |__|__|__|ql|__|__|__|__|=
3  |__|__|__|__|__|__|ql|__|=
2  |__|__|__|__|ql|__|__|__|=
1  |__|ql|__|__|__|__|__|__|=
|Решение бр. 5
}}
</td>
<td>
{{Шаховски дијаграм|=
| tright
|
|=

8  |__|__|__|__|ql|__|__|__|=
7  |__|__|ql|__|__|__|__|__|=
6  |__|__|__|__|__|__|__|ql|=
5  |__|__|__|ql|__|__|__|__|=
4  |__|__|__|__|__|__|ql|__|=
3  |ql|__|__|__|__|__|__|__|=
2  |__|__|__|__|__|ql|__|__|=
1  |__|ql|__|__|__|__|__|__|=
|Решение бр. 6
}}
</td>
</tr>
<tr>
<td>
{{Шаховски дијаграм|=
| tright
|
|=

8  |__|__|__|__|ql|__|__|__|=
7  |__|__|__|__|__|__|ql|__|=
6  |__|__|__|ql|__|__|__|__|=
5  |ql|__|__|__|__|__|__|__|=
4  |__|__|ql|__|__|__|__|__|=
3  |__|__|__|__|__|__|__|ql|=
2  |__|__|__|__|__|ql|__|__|=
1  |__|ql|__|__|__|__|__|__|=
|Решение бр. 7
}}
</td>
<td>
{{Шаховски дијаграм|=
| tright
|
|=

8  |__|__|__|ql|__|__|__|__|=
7  |ql|__|__|__|__|__|__|__|=
6  |__|__|__|__|ql|__|__|__|=
5  |__|__|__|__|__|__|__|ql|=
4  |__|__|__|__|__|ql|__|__|=
3  |__|__|ql|__|__|__|__|__|=
2  |__|__|__|__|__|__|ql|__|=
1  |__|ql|__|__|__|__|__|__|=
|Решение бр. 8
}}
</td>
<td>
{{Шаховски дијаграм|=
| tright
|
|=

8  |__|__|ql|__|__|__|__|__|=
7  |__|__|__|__|__|ql|__|__|=
6  |__|__|__|ql|__|__|__|__|=
5  |ql|__|__|__|__|__|__|__|=
4  |__|__|__|__|__|__|__|ql|=
3  |__|__|__|__|ql|__|__|__|=
2  |__|__|__|__|__|__|ql|__|=
1  |__|ql|__|__|__|__|__|__|=
|Решение бр. 9
}}
</td>
</tr>
<tr>
<td>
{{Шаховски дијаграм|=
| tright
|
|=

8  |__|__|__|__|__|ql|__|__|=
7  |__|ql|__|__|__|__|__|__|=
6  |__|__|__|__|__|__|ql|__|=
5  |ql|__|__|__|__|__|__|__|=
4  |__|__|__|ql|__|__|__|__|=
3  |__|__|__|__|__|__|__|ql|=
2  |__|__|__|__|ql|__|__|__|=
1  |__|__|ql|__|__|__|__|__|=
|Решение бр. 10
}}
</td>
<td>
{{Шаховски дијаграм|=
| tright
|
|=

8  |__|__|__|ql|__|__|__|__|=
7  |__|__|__|__|__|__|ql|__|=
6  |ql|__|__|__|__|__|__|__|=
5  |__|__|__|__|__|__|__|ql|=
4  |__|__|__|__|ql|__|__|__|=
3  |__|ql|__|__|__|__|__|__|=
2  |__|__|__|__|__|ql|__|__|=
1  |__|__|ql|__|__|__|__|__|=
|Решение бр. 11
}}
</td>
<td>
{{Шаховски дијаграм|=
| tright
|
|=

8  |__|__|__|__|__|ql|__|__|=
7  |__|__|__|ql|__|__|__|__|=
6  |__|__|__|__|__|__|ql|__|=
5  |ql|__|__|__|__|__|__|__|=
4  |__|__|__|__|__|__|__|ql|=
3  |__|ql|__|__|__|__|__|__|=
2  |__|__|__|__|ql|__|__|__|=
1  |__|__|ql|__|__|__|__|__|=
|Решение бр. 12
}}
</td>
</tr>
</table>
 |frame-style = border: 1px solid Blue 
 |title-style = color: black; background-color: lavender; font-weight: bold 
 |content-style = color: black; background-color: ghostwhite; text-align: left 
 |hidden = 1
}}

=== Број на решенија до n=26 ===
Во продолжение се претставени табели со бројот на единствени решенија, како и вкупниот број на решенија на проблемот, зададен со различен број на дами на различна големина на шаховската табла.

{| class="prettytable"
|- align="right"
! ''n''
| 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16 || 17 || 18
|- align="right"
! единствени
| 1 || 0 || 0 || 1 || 2 || 1 || 6 || 12 || 46 || 92 || 341 || 1.787 || 9.233 || 45.752 || 285.053 || 1.846.955 || 11.977.939 || 83.263.591
|- align="right"
! вкупно
| 1 || 0 || 0 || 2 || 10 || 4 || 40 || 92 || 352 || 724 || 2.680 || 14.200 || 73.712 || 365.596 || 2.279.184 || 14.772.512 || 95.815.104 || 666.090.624
|}

{| class="prettytable"
|- align="right"
! ''n''
| 19 || 20 || 21 || 22 || 23 || 24
|- align="right"
! единствени
| 621.012.754 || 4.878.666.808 || 39.333.324.973 || 336.376.244.042 || 3.029.242.658.210 || 28.439.272.956.934
|- align="right"
! вкупно
| 4.968.057.848 || 39.029.188.884 || 314.666.222.712 || 2.691.008.701.644 || 24.233.937.684.440 || 227.514.171.973.736
|}

{| class="prettytable"
|- align="right"
! ''n''
| 25 (светски рекорд во 2005) || 26 (светски рекорд во 2009)
|- align="right"
! единствени
| 275.986.683.743.434 || 2.789.712.466.510.289
|- align="right"
! вкупно
| 2.207.893.435.808.352 || 22.317.699.616.364.044
|}

Уште претходно познатиот, но недокажан број на решенија за n=12 бил потврден како точен во 1969 година, со компјутерските анализи на Торбјорн Линделоф и Бернд Шварцкопф. Линделоф го пресметал и бројот на точните решанија за n=13 и n=14.<ref>Karl Fabel: ''Das n-Damen-Problem'', Die Schwalbe, Heft 1, октомври 1969, стр. 20.</ref> Во 1970 година, Линделоф го премсетал бројот и за n=15, со забелешка дека за поголемите шаховски табли потребни се компјутери кои поседуваат од 50 до 100 пати поголем капацитет од тогашните.<ref>Karl Fabel: ''Das n-Damen-Problem'', Die Schwalbe, Heft 5, септември 1970 стр. 146.</ref>

Бројот на решенија за n=26 беше пресметан на 11 јули 2009 година, со проектот Queens@TUD<ref>[http://queens.inf.tu-dresden.de The World Record by FPGAs!] {{Семарх|url=https://web.archive.org/web/20171110040233/http://queens.inf.tu-dresden.de/ |date=2017-11-10 }}, Queens@TUD, TU Dresden, Deutschland</ref> и примената на [[FPGA]] и на 30 август 2009, со проектот MC#<ref>{{Наведена мрежна страница |url=http://www.mcsharp.net/nqueens.html |title=Solving the N-Queens problem for N = 26 using MC# Programming System |accessdate=2010-11-19 |archive-date=2012-03-01 |archive-url=https://web.archive.org/web/20120301124806/http://www.mcsharp.net/nqueens.html |url-status=dead }}</ref> и примената на два руски суперсметачи, кои се наоѓаа на тогашниот список [[TOP500]].

Општо е потврдено дека бројот на решенија на проблемот во однос на зголемување на вредноста на променливата n, расте со нешто поголем раст од [[Експоненцијален раст|експоненцијалниот]]. Интересно е и што за n=2 и n=6, бројот на решенија е помал отколку за некои помали вредности на n.

=== Број на решенија за n>26 ===
Горна граница за вбројот на решенија на проблемот со n дами (D(n)) на шаховска табла со димензии n x n е<math>n!</math>. Ова е бројот на решенија за проблемот, во кој наместо дами се бара да се постават [[Топ (шах)|топови]]. Поставувањето на дами претставува [[подмножество]] на поставувањето на топови.

Асимптотскиот облик на D(n) не е познат. Претпоставка е дека може да се употреби формулата:
: <math>\lim_{n \to \infty} \frac{\log{D(n)}}{n \log{n}}=\beta>0 </math> ist.<ref name="Rivin">I. Rivin, I. Vardi, P. Zimmermann: ''The n-Queens Problem'', The American Mathematical Monthly, Band 101, 1994, стр. 629-639.</ref>

Од познатите броеви во низата се појавува претпоставката дека за големите вредности на n, важи:{{ref label|А|а|а}}<math>D(n)\approx n! \cdot c^n </math>, каде што <math>c\approx 0.39</math>.

== Сродни проблеми ==
=== Други фигури ===
Проблемот може да биде зададен и со останатите [[шаховски фигури]]. Како такви, познати се проблемите со 32 [[Коњ (шах)|коња]], 14 [[Ловец (шах)|ловци]], 16 [[Крал (шах)|крала]] и 8 [[Топ (шах)|топа]]. Потребно е да се забележи дека [[Коњски од|коњскиот од]] не претставува проблем од ист вид.

=== Проблем со n супердами ===
Невообичаено проширување на проблемот претставува проблемот со n супердами. Супердамата претставува дама, којашто може да се движи и како [[Коњ (шах)|коњ]]. Не е јасно, кој ги измислил супердамите, ниту пак кој го задал проблемот со n супердами. Во ''Mathematische Knobeleien'' од 1973 година, [[Мартин Гарднер]] споменува шаховска варијанта, која се игра со супердама. Гарднер, оваа фигура ја нарекол „махарадша“. Други пак, истата ја нарекуваат „амазонка“. Проблемот се состои во барање на одговор на бројот на начини на коишто n супердами може да се постават на шаховска табла со димензии n×n.

Во табелата во продолжение се прикажани решенијата на проблемот за вредност на n до 25:{{ref label|В|в|в}}

{| class="wikitable"
|- class="hintergrundfarbe5"
! n !! Решенија !! n !! Решенија !! n !! Решенија !! n !! Решенија !! n !! Решенија
|- 
| 1 || 1 || 6  || 0  || 11 || 44    || 16 || 202900    || 21 || 3977841852
|- 
| 2 || 0 || 7  || 0  || 12 || 156   || 17 || 1330622   || 22 || 34092182276
|- 
| 3 || 0 || 8  || 0  || 13 || 1876  || 18 || 8924976   || 23 || 306819842212
|- 
| 4 || 0 || 9  || 0  || 14 || 5180  || 19 || 64492432  || 24 || 2883202816808
|- 
| 5 || 0 || 10 || 4  || 15 || 32516 || 20 || 495864256 || 25 || 28144109776812
|}

Од 2001 година, постои и едноставно решение за проблемот со n супердами, за кое е најзаслужен Франк Швелингер.

=== Други видови на табла ===
[[Ѓерѓ Поја]] го набљудувал проблемот со осум дами на [[Тоурсоиден шах|торусоидна шаховска табла]] и докажал дека тогаш постои најмалку едно решение, кога вредноста на n не е [[Деливсот|делива]] ниту со 2, ниту со 3.<ref>George Polya:: ''Uber die doppelt-periodischen Losungen des n-Damen-Problems'', Collected papers Vol. IV, G-C. Rota, ed., MIT Press, Cambridge, London, 1984, стр. 237-247.</ref> ВО 2009 година, бил создаден алгоритам за поставување на n<sup>2</sup> дами на шаховска табла со димензии n×n×n. Исто така е посочено дека преку зададениот проблем на овој начин е можно наоѓање на решенија и за четиридимензионална варијанта на проблемот.

=== Други задачи со дами ===
За шаховска табла со димензии n×n е одреден „доминантен број“, кој го претставува најмалиот број на дами, кои се потребни за да го нападнат секое поле на таблата. За вообичаена шаховска табла, со димензии 8×8, потребни се 5 дами.

Проблемот со девет дами се состои од поставување на девет дами и еден пешак на шаховска табла со вообичаена големина, така што ниту една дама да не напаѓа и да не биде нападната од друга дама. Овој проблем може да се постави на шаховска табла со која било големина и притоа со додавање на повеќе пешаци.

== Поврзано ==
* [[Шаховска композиција]]

== Белешки ==
* {{note label|А|а|а}} {{OEIS|id=A000170}}.
* {{note label|Б|б|б}} Со други зборови, кога ќе се отстрани еден ред од шаховска табла со димензии n×(n−1) на која е решен проблемот за n-1 дами, повторно се добива решение на проблемот, но со n−2 дами на табла со димензии n×(n−2).
* {{note label|В|в|в}} {{OEIS|id=A051223}}.

== Наводи ==
{{наводи|2}}

== Литература ==
* John J. Watkins: ''Across the Board: The Mathematics of Chess Problems''. Princeton University Press, Princeton 2004, ISBN 0-691-11503-6.
* Ole-Johan Dahl, E. W. Dijkstra, C. A. R. Hoare: ''Structured Programming'', Academic Press, London, 1972, ISBN 0-12-200550-3.
* S. Nudelman: ''The Modular N-Queens Problem in Higher Dimensions'', Discrete Mathematics, vol 146, iss. 1-3, 15 ноември 1995.
* J. Barr, S. Rao: ''The n-Queens Problem in Higher Dimensions'', Elemente der Mathematik, vol 61, 2006.

== Надворешни врски == 
* [http://www.jsomers.com/nqueen_demo/nqueens.html The N Queens Problem] {{Семарх|url=https://web.archive.org/web/20110606104530/http://www.jsomers.com/nqueen_demo/nqueens.html |date=2011-06-06 }}, Jeff Somers
* [http://www.durangobill.com/N_Queens.html The N-Queens Problem], Durango Bill
* [http://mathworld.wolfram.com/QueensProblem.html Queens Problem], MathWorld
* [http://www.mactech.com/articles/mactech/Vol.13/13.12/TheEightQueensProblem/ Solving The Eight Queens Problem]
* [http://www.stefan-baur.de/cs.algo.8queens.html Algorithmus und Lösungen] {{Семарх|url=https://web.archive.org/web/20120119163449/http://www.stefan-baur.de/cs.algo.8queens.html |date=2012-01-19 }}
* [http://www.arstechnica.de/computer/JavaScript/JS11_04.html Beliebige Brettgrößen in JavaScript], ArsTechnica.de
* [http://8damen.liebhard.net/ Lösung und Hintergrund]

[[Категорија:Шахот во 1848 година]]
[[Категорија:Шаховска композиција]]
[[Категорија:Математика во шахот]]
[[Категорија:Комбинаторика]]