O‘zbekiston Respublikasi Raqamli texnologiyalari Vazirligi Muhammad al-Xorazmiy nomidagi Toshkent axborot texnologiyalari universiteti

O‘zbekiston Respublikasi Raqamli texnologiyalari
Vazirligi
Muhammad al-Xorazmiy nomidagi Toshkent axborot texnologiyalari universiteti

Amaliy topshiriq

Mavzu: Shaxmat taxtasida malikalar masalasini yechish
Fan: Kriptografiya 1
Bajardi: Suyunov Ferdavs
Tekshirdi: Mardiyev Ulugbek
TOSHKENT – 2023
Mavzu: Shaxmat taxtasida malikalar masalasini yechish
Reja

1. 
   Kirish
   
2. 
   Asosiy qism
   

1. 
   

3. 
   Xulosa
   
4. 
   Foydalanilgan adabiyotlar
   

Kirish
Qirolichalar boshqotirmasi - bu ajoyib va qiyin masala bo'lib, NxN shaxmat taxtasiga ikkita malika bir-biriga hujum qila olmaydigan tarzda N qirolichani joylashtirishni o'z ichiga oladi. Ushbu klassik jumboq asrlar davomida matematiklar va boshqotirma ishqibozlarini qiziqtirib, yechimlarni topish uchun turli yondashuvlar va strategiyalarni ilhomlantirgan.

Grafik nazariyasi ob'ektlar o'rtasidagi munosabatlarni o'rganish uchun matematik asosni taqdim etadi va kombinatsion muammolarni hal qilish bo'yicha qimmatli tushunchalarni beradi. Bu erda biz grafik nazariyasi yordamida Qirolicha jumboqini hal qilishning noyob va kuchli usulini o'rganamiz. Qirolicha jumboqini echishda grafik nazariyasini qo'llashning asosiy g'oyasi muammoni grafik sifatida ko'rsatishdir, bu erda har bir cho'qqi shaxmat taxtasidagi pozitsiyaga mos keladi va qirralari ikkita malika bir-biriga hujum qilish imkoniyatini ifodalaydi.

Qo'shni bo'lmagan cho'qqilar to'plami bo'lgan cho'qqiga mustaqil to'plamlarning grafik nazariyasi kontseptsiyasidan foydalangan holda, biz ikkita malika bir-biriga tahdid solmaydigan malikalarning haqiqiy konfiguratsiyasini aniqlashimiz mumkin. Ushbu yondashuv Qirolicha boshqotirmasi uchun oqlangan va samarali yechimni taqdim etadi, bu bizga boshqotirma cheklovlarini qondiradigan shaxmat taxtasida malikalarning barcha mumkin bo'lgan tartibini muntazam ravishda topishga imkon beradi.

Bu yerda sizga qirrali mustaqil toʻplamlar yordamida Qirolicha jumboqini yechish boʻyicha bosqichma-bosqich yoʻl-yoʻriq koʻrsatiladi. Biz Qirolichalar Graph qurilishini muhokama qilamiz va har xil taxta o'lchamlari uchun echimlar sonini o'rganamiz. Bundan tashqari, biz boshqotirmalarni yechishdan tashqari grafik nazariyasini qo'llash bo'yicha qimmatli tushunchalarga ega bo'lamiz, chunki u turli xil real muammolarni hal qilish uchun ko'p qirrali asosni taqdim etadi.

Asosiy qism


Qirolichalar boshqotirmasi

Qirolichalar boshqotirmasi shaxmat va kombinatoriy optimallashtirish sohasidagi klassik muammodir. Qirolichalar boshqotirmasi eng mashhur namunasi 8-qirolicha boshqotirmasi boʻlib, biz 8x8 shaxmat taxtasiga 8 ta malikani joylashtirishni maqsad qilganmiz, shunda hech bir malika boshqa malikani qoʻlga kirita olmaydi. Bu asl muammoni birinchi marta 1848 yilda nemis shaxmatchisi qo'ygan.O'z davrining atoqli matematigi Gauss bu masalani bilgan va 72 ta yechim topgan. Biroq, keyinchalik u bundan ham ko'proq echimlar borligini tushundi va u yechimlarning umumiy soni 92 ta ekanligini da'vo qildi. Keyinchalik E. Pauls 1874 yilda dalilni nashr etdi, bu savolni hal qildi va jumboqni qondiradigan 92 ta noyob konfiguratsiya mavjudligini tasdiqladi. cheklovlar.

Queens Puzzle N ning turli qiymatlariga ega kattaroq shaxmat taxtalariga ham kengaytirilishi mumkin. Umuman olganda, n qirolichalar muammosi NxN shaxmat taxtasiga ikkita malika bir-biriga hujum qila olmaydigan tarzda N qirolichalarni joylashtirishni o'z ichiga oladi. Ushbu cheklov ikkita malika bir xil satr, ustun yoki diagonalni taqsimlamasligi kerakligini anglatadi.

Qirolicha jumboqini hal qilish uchun malikalarning to'g'ri joylashishini ta'minlash uchun tizimli yondashuv talab etiladi. Ko'p ishlatiladigan usullardan biri bu orqaga qaytish algoritmidir. Ushbu algoritm tizimli ravishda yechim maydonini o'rganadi, malikalarni shaxmat taxtasiga birma-bir joylashtiradi va nizo yuzaga kelganda orqaga qaytadi. Bu kombinatsion muammolarni hal qilish uchun kuchli va samarali texnikadir.

Qirolicha jumboqini hal qilish uchun malikalarning to'g'ri joylashishini ta'minlash uchun tizimli yondashuv talab etiladi. Ko'p ishlatiladigan usullardan biri bu orqaga qaytish algoritmidir. Ushbu algoritm tizimli ravishda yechim maydonini o'rganadi, malikalarni shaxmat taxtasiga birma-bir joylashtiradi va nizo yuzaga kelganda orqaga qaytadi. Bu kombinatsion muammolarni hal qilish uchun kuchli va samarali texnikadir.