Проблем со осум дами

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

	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

Едно од можните решенија на проблемот

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

Историја

За првпат, проблемот со дамите бил формулиран од страна на германскиот шаховски мајстор, Макс Бецел. Во 1848 година, во списанието „Deutsche Schachzeitung“ бил побаран одговор на бројот на можни решенија на проблемот. Прв кој го дал точниот број на решенија, кој изнесува 92, бил Франц Наук, кој во 1850 година, својот одговор го објавил во списанието „Illustrirte Zeitung“. Понеговата појава, многу видни математичари се заинтересирале за проблемот, вклучуваји го и Карл Фридрих Гаус.^[1] Во 1874 година, англискиот математичар, Џејмс Витбрид Ле Глејшер, докажал дека нема повеќе решенија на проблемот.^[2] Со тоа, почетнозададениот проблем бил целосно решен.

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

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

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

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

Начин на решавање

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

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

Ефикасниот алгоритам со методот на целосна обработка сместува по една дама во секој ред, притоа намалувајќи ја коплексноста на можните позиции, кој изнесува 8⁸ = 2²⁴.

Рекурзивно прелистување со повторување

Анимација на работата на алгоритмот со рекурзивно прелистување со повторување

Проблемот има нетривијални решенија и може да се реши со рекурзивен алгоритам, во којшто проблемот со n дами е претставен така што важи додавањето на нова дама на секое решение на проблемот за n-1 дама. На крајот на краиштата, секој проблем со дами започнува со проблем со 0 дами, што всушност претставува празна шаховска табла.

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

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

Едноставно решение

	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

Решение на проблемот со примена на Бернардсоновиот алгоритам

Посебно решение на проблемот за која било големина на таблата, нуди алгоритмот развиен од страна на Бо Бернардсон.^[3]

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

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

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

Други методи

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

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

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

Број на решенија

Класичен проблем

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

{{{1}}}

	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

Решение бр. 1

	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

Решение бр. 2

	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

Решение бр. 3

	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

Решение бр. 4

	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

Решение бр. 5

	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

Решение бр. 6

	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

Решение бр. 7

	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

Решение бр. 8

	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

Решение бр. 9

	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

Решение бр. 10

	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

Решение бр. 11

	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

Решение бр. 12

Број на решенија до n=26

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

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
единствени	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
вкупно	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

n	19	20	21	22	23	24
единствени	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
вкупно	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

n	25 (светски рекорд во 2005)	26 (светски рекорд во 2009)
единствени	275.986.683.743.434	2.789.712.466.510.289
вкупно	2.207.893.435.808.352	22.317.699.616.364.044

Уште претходно познатиот, но недокажан број на решенија за n=12 бил потврден како точен во 1969 година, со компјутерските анализи на Торбјорн Линделоф и Бернд Шварцкопф. Линделоф го пресметал и бројот на точните решанија за n=13 и n=14.^[4] Во 1970 година, Линделоф го премсетал бројот и за n=15, со забелешка дека за поголемите шаховски табли потребни се компјутери кои поседуваат од 50 до 100 пати поголем капацитет од тогашните.^[5]

Бројот на решенија за n=26 беше пресметан на 11 јули 2009 година, со проектот Queens@TUD^[6] и примената на FPGA и на 30 август 2009, со проектот MC#^[7] и примената на два руски суперсметачи, кои се наоѓаа на тогашниот список TOP500.

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

Број на решенија за n>26

Горна граница за вбројот на решенија на проблемот со n дами (D(n)) на шаховска табла со димензии n x n е $n!$ . Ова е бројот на решенија за проблемот, во кој наместо дами се бара да се постават топови. Поставувањето на дами претставува подмножество на поставувањето на топови.

Асимптотскиот облик на D(n) не е познат. Претпоставка е дека може да се употреби формулата:

\lim _{n\to \infty }{\frac {\log {D(n)}}{n\log {n}}}=\beta >0

ist.^[8]

Од познатите броеви во низата се појавува претпоставката дека за големите вредности на n, важи:^[а] $D(n)\approx n!\cdot c^{n}$ , каде што $c\approx 0.39$ .

Сродни проблеми

Други фигури

Проблемот може да биде зададен и со останатите шаховски фигури. Како такви, познати се проблемите со 32 коња, 14 ловци, 16 крала и 8 топа. Потребно е да се забележи дека коњскиот од не претставува проблем од ист вид.

Проблем со n супердами

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

Во табелата во продолжение се прикажани решенијата на проблемот за вредност на n до 25:^[в]

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.^[9] ВО 2009 година, бил создаден алгоритам за поставување на n² дами на шаховска табла со димензии n×n×n. Исто така е посочено дека преку зададениот проблем на овој начин е можно наоѓање на решенија и за четиридимензионална варијанта на проблемот.

Други задачи со дами

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

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

Поврзано

Шаховска композиција

Белешки

^а (низа A000170 во OEIS).
^б Со други зборови, кога ќе се отстрани еден ред од шаховска табла со димензии n×(n−1) на која е решен проблемот за n-1 дами, повторно се добива решение на проблемот, но со n−2 дами на табла со димензии n×(n−2).
^в (низа A051223 во OEIS).

Наводи

↑ „Information on the n Queens problem“. Архивирано од изворникот на 2007-12-14. Посетено на 2010-11-19.
↑ Evgeni J. Gik: Schach und Mathematik. Verlag Deutsch Harri GmbH, ISBN 3-87144-987-3.
↑ Bo Bernhardsson: Explicit solutions to the N-queens problem for all N, ACM SIGART Bulletin 2/2, 1991.
↑ Karl Fabel: Das n-Damen-Problem, Die Schwalbe, Heft 1, октомври 1969, стр. 20.
↑ Karl Fabel: Das n-Damen-Problem, Die Schwalbe, Heft 5, септември 1970 стр. 146.
↑ The World Record by FPGAs! Архивирано на 10 ноември 2017 г., Queens@TUD, TU Dresden, Deutschland
↑ „Solving the N-Queens problem for N = 26 using MC# Programming System“. Архивирано од изворникот на 2012-03-01. Посетено на 2010-11-19.
↑ I. Rivin, I. Vardi, P. Zimmermann: The n-Queens Problem, The American Mathematical Monthly, Band 101, 1994, стр. 629-639.
↑ 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.

Литература

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.

Надворешни врски

The N Queens Problem Архивирано на 6 јуни 2011 г., Jeff Somers
The N-Queens Problem, Durango Bill
Queens Problem, MathWorld
Solving The Eight Queens Problem
Algorithmus und Lösungen Архивирано на 19 јануари 2012 г.
Beliebige Brettgrößen in JavaScript, ArsTechnica.de
Lösung und Hintergrund

[1] „Information on the n Queens problem“. Архивирано од изворникот на 2007-12-14. Посетено на 2010-11-19.

[2] Evgeni J. Gik: Schach und Mathematik. Verlag Deutsch Harri GmbH, ISBN 3-87144-987-3.

[3] Bo Bernhardsson: Explicit solutions to the N-queens problem for all N, ACM SIGART Bulletin 2/2, 1991.

[4] Karl Fabel: Das n-Damen-Problem, Die Schwalbe, Heft 1, октомври 1969, стр. 20.

[5] Karl Fabel: Das n-Damen-Problem, Die Schwalbe, Heft 5, септември 1970 стр. 146.

[6] The World Record by FPGAs! Архивирано на 10 ноември 2017 г., Queens@TUD, TU Dresden, Deutschland

[7] „Solving the N-Queens problem for N = 26 using MC# Programming System“. Архивирано од изворникот на 2012-03-01. Посетено на 2010-11-19.

[Rivin-8] I. Rivin, I. Vardi, P. Zimmermann: The n-Queens Problem, The American Mathematical Monthly, Band 101, 1994, стр. 629-639.

[9] 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.

[1]

[2]

[б]

[3]

[4]

[5]

[6]

[7]

[8]

[а]

[в]

[9]