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

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

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

 Историја 
За првпат, проблемот со дамите бил формулиран од страна на германскиот шаховски мајстор, Макс Бецел. Во 1848 година, во списанието „Deutsche Schachzeitung“ бил побаран одговор на бројот на можни решенија на проблемот. Прв кој го дал точниот број на решенија, кој изнесува 92, бил Франц Наук, кој во 1850 година, својот одговор го објавил во списанието „Illustrirte Zeitung“. Понеговата појава, многу видни математичари се заинтересирале за проблемот, вклучуваји го и Карл Фридрих Гаус. Во 1874 година, англискиот математичар, Џејмс Витбрид Ле Глејшер, докажал дека нема повеќе решенија на проблемот.Evgeni J. Gik: Schach und Mathematik. Verlag Deutsch Harri GmbH, ISBN 3-87144-987-3. Со тоа, почетнозададениот проблем бил целосно решен.

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

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

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

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

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

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

Ефикасниот алгоритам со методот на целосна обработка сместува по една дама во секој ред, притоа намалувајќи ја коплексноста на можните позиции, кој изнесува 88 = 224.

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

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

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

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

Посебно решение на проблемот за која било големина на таблата, нуди алгоритмот развиен од страна на Бо Бернардсон.Bo Bernhardsson: Explicit solutions to the N-queens problem for all N, ACM SIGART Bulletin 2/2, 1991.

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

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

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

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

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

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

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

 Број на решенија до 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.Karl Fabel: Das n-Damen-Problem, Die Schwalbe, Heft 1, октомври 1969, стр. 20. Во 1970 година, Линделоф го премсетал бројот и за n=15, со забелешка дека за поголемите шаховски табли потребни се компјутери кои поседуваат од 50 до 100 пати поголем капацитет од тогашните.Karl Fabel: Das n-Damen-Problem, Die Schwalbe, Heft 5, септември 1970 стр. 146.

Бројот на решенија за n=26 беше пресметан на 11 јули 2009 година, со проектот Queens@TUDThe World Record by FPGAs! , Queens@TUD, TU Dresden, Deutschland и примената на FPGA и на 30 август 2009, со проектот MC# и примената на два руски суперсметачи, кои се наоѓаа на тогашниот список TOP500.

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

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

Асимптотскиот облик на D(n) не е познат. Претпоставка е дека може да се употреби формулата:
  ist.I. Rivin, I. Vardi, P. Zimmermann: The n-Queens Problem, The American Mathematical Monthly, Band 101, 1994, стр. 629-639.

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

 Сродни проблеми 
 Други фигури 
Проблемот може да биде зададен и со останатите шаховски фигури. Како такви, познати се проблемите со 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.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. ВО 2009 година, бил создаден алгоритам за поставување на n2 дами на шаховска табла со димензии n×n×n. Исто така е посочено дека преку зададениот проблем на овој начин е можно наоѓање на решенија и за четиридимензионална варијанта на проблемот.

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

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

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

 Белешки 
  .
  Со други зборови, кога ќе се отстрани еден ред од шаховска табла со димензии n×(n−1) на која е решен проблемот за n-1 дами, повторно се добива решение на проблемот, но со n−2 дами на табла со димензии n×(n−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.

 Надворешни врски  
 The N Queens Problem , Jeff Somers
 The N-Queens Problem, Durango Bill
 Queens Problem, MathWorld
 Solving The Eight Queens Problem
 Algorithmus und Lösungen 
 Beliebige Brettgrößen in JavaScript, ArsTechnica.de
 Lösung und Hintergrund

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