Ութ թագուհիների խնդիրը շախմատի տախտակի վրա խաղաքարերը դասավորելու Հայտնի կոմբինատորային խնդիր է ։ Նախնական ձևակերպումը հետևյալն է."ստանդարտ 64-բջջային շախմատի տախտակի վրա Դասավորել 8 թագուհի, որպեսզի նրանցից ոչ մեկը մյուսի կռվի տակ չլինի":
Խստորեն մաթեմատիկորեն, խնդիրը կարող է ձևակերպվել մի քանի եղանակով, Օրինակ ՝ " Լրացրեք մատրիցը չափի մեջ
8
×
8
զրոներով և միավորներով այնպես, որ մատրիցայի բոլոր տարրերի գումարը հավասար լինի 8-ի, Ընդ որում մատրիցայի ոչ մի սյունակում, շարքում կամ անկյունագծային շարքում տարրերի գումարը չի գերազանցում միավորները":
Վերջնական նպատակը, որը դրված է խնդրի լուծման համար, կարող է ձևակերպվել մի քանի տարբերակներով:
Կառուցեք մեկ խնդրի ցանկացած լուծում:
Վերլուծականորեն ապացուցեք, որ լուծումը գոյություն ունի:
Որոշեք լուծումների քանակը:
Կառուցեք բոլոր հնարավոր լուծումները:
Ստեղծեք համակարգչային ծրագիր, որը գտնում է խնդրի բոլոր հնարավոր լուծումները: Մեկը բնորոշ խնդիրների ծրագրավորման busting ալգորիթմներ.
Երբեմն խնդրի հայտարարությունը պահանջում է գտնել դասավորության մեթոդներ
թագուհին տախտակի վրա
×
բջիջները (Նշենք, որ երբ
1
<
<
4
խնդիրը լուծում չունի):
էփորձելի է, որ շատ հեղինակներ սխալմամբ ութ թագուհիների խնդիրը և դրա լուծումը վերագրում են հենց Գաուսին ։ Իրականում այն առաջինը ձևակերպել է 1848 թվականին գերմանացի շախմատիստ Մ. Բեցելը։ Գիտական \ u200b \ u200bդոկտոր (ծնված կույր) գտավ 60 լուծում և հրապարակեց դրանք illustrierte Zeitung թերթում 1 թվականի հունիսի 1850-ին: Միայն դրանից հետո Գաուսը հետաքրքրվեց առաջադրանքով և գտավ 72 լուծում, որոնք նա հայտնեց իր ընկերոջ աստղագետ Շումախերին ուղղված նամակում 2 թվականի սեպտեմբերի 1850-ին: լուծումների ամբողջական փաթեթը, որը բաղկացած էր 92 դիրքերից, ստացավ նույն Ֆ.գիտությունները (նա դրանք մեջբերեց 1850 թվականի սեպտեմբերի 21-ի Այս ժամանակագրությունը հաստատել է մաթեմատիկական զվարճանքի հայտնի գերմանացի հետազոտող Վ. Արենսը, ով իր գրքերում շատ տեղ է հատկացրել խնդրո առարկա խնդրին ։
Ապացույցը, որ 92 լուծումները սպառում են բոլոր հնարավորությունները, ստացվել է միայն 1874 թվականին անգլիացի մաթեմատիկոս Դ.Գլեշերի կողմից (որոշիչների տեսության օգնությամբ) ։
Սկզբունքորեն, տախտակի վրա տեղադրելով ութ թագուհիներ ամեն կերպ, մենք, ի վերջո, կգտնենք մեզ հարմար բոլոր համաստեղությունները: Այնուամենայնիվ, այս ճանապարհը չափազանց երկար է և ձանձրալի: Դուք կարող եք սահմանափակվել միայն նավակների վերաբերյալ համապատասխան խնդրի լուծումներով և դրանց մեջ ընտրել այնպիսիները, որոնցում ոչ մի զույգ նավակներ արժանի չեն մեկ անկյունագծի: Բայց նույնիսկ այս դեպքում գերբեռնվածությունը բավականին մեծ է (ձեզ հարկավոր կլինի, ինչպես գիտենք, ավելի քան 40,000 փորձ): Այսպիսով, խնդիրը "ձեռքով" լուծելիս (և հենց այդպես են վարվել անցյալ դարում), համաստեղությունների հարկադիր կրկնությունը պետք է լավ մտածված լինի ։ Հայտնի են թագուհիների որոնված վայրերի քիչ թե շատ խելամիտ որոնումը կազմակերպելու բազմաթիվ եղանակներ (Պերմանտիեի, Լա-Նոյի, Գյունտերի, Գլաշերի, Լակիերի և այլնի մեթոդներ): Այս մեթոդները նկարագրված են զվարճալի մաթեմատիկայի վերաբերյալ բազմաթիվ գրականության մեջ (հիմնականում անցյալ դարում և ներկայիս սկզբին): Հաշվողական մեքենաների մեր դարաշրջանում Այս բազմազանության խնդիրը չէր կարող այդքան մեծ հետաքրքրություն առաջացնել: Ի վերջո, բավական է համակարգիչների համար պարզ ծրագիր կազմել, և մեքենայի մեջ դրա ներդրումից մի քանի րոպե անց բոլոր 92 անհրաժեշտ դիրքերը տրվելու ենպաշտոնները կտրվեն տպագրության:
Queens-ի խնդրի յուրաքանչյուր լուծումից դուք կարող եք ձեռք բերել մի շարք ուրիշներ ' օգտագործելով տախտակի պտույտները (պտույտները) կենտրոնի շուրջ 90, 180 և 270° ժամացույցի սլաքի ուղղությամբ (360° շրջադարձը հանգեցնում է մեկնարկային դիրքի): Թագուհիների այս դասավորությունից նորը կարելի է ձեռք բերել նաև տախտակի հայելային արտացոլմամբ ' նկ. 43 (1-ին դիրք)35. Օրինակ, այս գործչի առաջին դասավորությունից, երբ տախտակը 90° - ով շրջվում է, մենք ստանում ենք երրորդը, իսկ երբ արտացոլվում ենք թագավորական և թագուհու եզրերը բաժանող գծի համեմատ, չորրորդը: Այլ շրջադարձերի և արտացոլումների օգնությամբ դուք կարող եք ստանալ ևս հինգ լուծում:
Այսպիսով, տախտակների շրջադարձերի և արտացոլումների ժամանակ թագուհիների մեկ դասավորությունից ստացվում է, ընդհանուր առմամբ, յոթ նոր: Ապացուցված է, որ ընդհանուր դեպքում n×n տախտակի վրա (n \ u003e 1-ում) հնարավոր է միայն երեք իրավիճակ ' միմյանց չվտանգող n թագուհիների ցանկացած պայմանավորվածության համար. Ա) տախտակի մեկ արտացոլմամբ ձեռք է բերվում նոր դասավորություն, իսկ շրջադարձերը և այլ արտացոլումները նոր բան չեն տալիս.բ) նոր լուծում է ձեռք բերվում տախտակը 90° պտտելիս, իսկ արտացոլումները տալիս են ևս երկու դասավորություն. գ) տախտակի բոլոր երեք շրջադարձերը և չորս արտացոլումները հանգեցնում են ութ անհամապատասխան դասավորությունների (ներառյալ բնօրինակը):
Ա) դեպքում սկզբնական լուծումը կոչվում է երկու անգամ սիմետրիկ, Բ) դեպքում 'սիմետրիկ, իսկ Գ) դեպքում' պարզ: Սովորական տախտակի համար յուրաքանչյուր լուծում կամ պարզ է, կամ սիմետրիկ, և երկու անգամ սիմետրիկ գոյություն չունի: Յուրաքանչյուր դասի լուծումների հանրահաշվական մեկնաբանությունը կարելի է գտնել Օկունևում:
Ութ թագուհիների համաստեղությունների բազմությունը (հավաքածուն) կոչվում է հիմնական,եթե դրանք, առաջին հերթին, տախտակի շրջադարձերի և արտացոլումների ժամանակ միմյանց չեն անցնում, և, Երկրորդ, ցանկացած այլ համաստեղություն ստացվում է ինչ-որ հիմնականից ՝ օգտագործելով այս վերափոխումները: Հայտնի է, որ խնդրի հիմնական լուծումների Յուրաքանչյուր հավաքածու պարունակում է ուղիղ 12 դիրք (համաստեղություններ):պաշտոնները կտրվեն տպագրության:
Queens-ի խնդրի յուրաքանչյուր լուծումից դուք կարող եք ձեռք բերել մի շարք ուրիշներ ' օգտագործելով տախտակի պտույտները (պտույտները) կենտրոնի շուրջ 90, 180 և 270° ժամացույցի սլաքի ուղղությամբ (360° շրջադարձը հանգեցնում է մեկնարկային դիրքի): Թագուհիների այս դասավորությունից նորը կարելի է ձեռք
բերել նաև տախտակի հայելային ա&#