21-dars: Backtracking

3-darajaOltin — graflar17–24 darslar

HayotdaSudoku

Sudoku yechayotganda bo’sh katakka son yozasiz, davom etasiz va bir necha qadamdan keyin ziddiyatga duch kelasiz. Butun jadvalni tashlamaysiz — oxirgi shubhali katakka qaytib, boshqa son sinaysiz. Aynan shu — backtracking.

Bu darsdan keyin siz

• backtracking sxemasini yozasiz: urin, tekshir, orqaga qayt
• kesish (pruning) ish hajmini qanchalik kamaytirishini o’lchaysiz
• holatni tiklashni unutmaysiz — eng ko’p uchraydigan xato shu

Avval qo’lda

Avval qo‘lda

~7 daqiqa·juftlikda·Shaxmat taxtasi yoki katakli qog'oz

6 × 6 taxta chizing va oltita farzin qo’yishga urinib ko’ring — ular bir-birini urmasin. Farzin o’z qatori, o’z ustuni va ikkala diagonali bo’ylab uradi.

Qoida: qatorma-qator yuring va har qatorga bittadan qo’ying. Joy topilmasa oldingi qatorga qaytib, u yerdagi farzinni keyingi ustunga suring.

Nimani sezishingiz kerak

Nechta marta orqaga qaytdingiz? Har qaytishda siz butun bir «kelajak»ni tashladingiz — o’sha buzuq boshlanishdan chiqadigan hamma joylashuvni. Bu kesish.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Sxema

backtrackingbacktracking

Yechimni qadamma-qadam qurib, har qadamda shart buzilganini tekshiradigan va buzilsa oldingi qadamga qaytadigan to’liq izlash.

kesishpruning

Yaroqsiz bo’lib chiqqan qisman yechimni davom ettirmaslik. Bir kesish o’sha shoxdagi barcha to’liq yechimlarni bir zarbada yo’q qiladi.

Sxema uch qatorga sig’adi va u har masalada bir xil: variantni qo’y, chuqurroq kir, keyin qo’yganingni olib tashla. Oxirgi qadam eng ko’p unutiladigani.

Sekin yechim

To’liq izlash avval butun joylashuvni quradi, keyingina tekshiradi. Har qatorda bitta farzin turishi shart, demak yechim — ustunlarning o’rin almashtirishi.

sekin.pyNusxalash

1from itertools import permutations2def sekin(n):3  soni = 04  for u in permutations(range(n)):5      yaxshi = True6      for i in range(n):7          for j in range(i + 1, n):8              if abs(u[i] - u[j]) == j - i:9                  yaxshi = False10      if yaxshi:11          soni += 112  return soni13print(sekin(4), sekin(6))

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1from itertools import permutations2def sekin(n):3  soni = 04  for u in permutations(range(n)):5      yaxshi = True6      for i in range(n):7          for j in range(i + 1, n):8              if abs(u[i] - u[j]) == j - i:9                  yaxshi = False10      if yaxshi:11          soni += 112  return soni13print(sekin(4), sekin(6))

Sizning bashoratingizTekshirish

Javobni ko'rish

2 4

Birinchi ikki farzin bir-birini urib turgan bo'lsa ham, qolganlari baribir joylashtiriladi va faqat oxirida tekshiriladi. Hech qanday kesish yo'q.

Nega sekin

n! ta joylashuv quriladi. Har biri to’liq qurilgandan keyingina tekshiriladi — ya’ni birinchi qadamdayoq buzilgan variantlarning butun shoxi baribir ishlanadi.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 8	n = 10	n = 12
Barcha o‘rin almashtirishn!	40 320sig‘adi	10⁶sig‘adi	10⁸chegarada
Kesish bilan (taxminan)2^n	256sig‘adi	1 024sig‘adi	4 096sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Tez yechim

Farzinni qo’yishdan oldin tekshiramiz. To’qnashuv bo’lsa o’sha zahoti keyingi ustunga o’tamiz va bu shoxni umuman qurmaymiz.

Diagonallarni raqamlash hiylasi ishni osonlashtiradi: bir yo’nalishdagi diagonalda qator − ustun o’zgarmaydi, ikkinchisida qator + ustun.

tez.pyNusxalash

1def tez(n):2  ustun, chap, ong = set(), set(), set()3  soni = 04  def qoy(i):5      nonlocal soni6      if i == n:7          soni += 18          return9      for j in range(n):10          if j in ustun or (i - j) in chap or (i + j) in ong:11              continue12          ustun.add(j)13          chap.add(i - j)14          ong.add(i + j)15          qoy(i + 1)16          ustun.remove(j)17          chap.remove(i - j)18          ong.remove(i + j)19  qoy(0)20  return soni21print(tez(4), tez(6), tez(8))

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1def tez(n):2  ustun, chap, ong = set(), set(), set()3  soni = 04  def qoy(i):5      nonlocal soni6      if i == n:7          soni += 18          return9      for j in range(n):10          if j in ustun or (i - j) in chap or (i + j) in ong:11              continue12          ustun.add(j)13          chap.add(i - j)14          ong.add(i + j)15          qoy(i + 1)16          ustun.remove(j)17          chap.remove(i - j)18          ong.remove(i + j)19  qoy(0)20  return soni21print(tez(4), tez(6), tez(8))

Sizning bashoratingizTekshirish

Javobni ko'rish

2 4 92

Javoblar sekin yechim bilan bir xil, ish hajmi esa ancha kam. 8 x 8 taxtada 92 ta yechim bor — bu klassik natija.

▲Bu yerda xato qilishadi

Rekursiv chaqiruvdan keyingi uchta remove — holatni tiklash. Uni unutish backtrackingdagi eng ko’p uchraydigan xato: keyingi variant oldingisining izlari bilan tekshiriladi va javob kam chiqadi.

Bu yerda rekursiya xavfsiz: chuqurlik n ga teng, n esa kichik. Rekursiya faqat chuqurlik uchlar soniga yetganda (18 va 20-darslar) muammoga aylanadi.

Sinab ko’r

Vizualda kulrang «x» — kesilgan variant. O’sha katakdan keyingi hamma joylashuv umuman qurilmasligini kuzating.

Backtracking — farzinlar

Kulrang «x» — kesilgan variant. Undan keyingi hamma joylashuv umuman qurilmaydi.

Farzinlar qatorma-qator qo'yiladi; to'qnashuv chiqqan zahoti o'sha shox tashlanadi va oldingi qatorga qaytiladi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. To'rtta farzin, to'rtta qator. Har qatorda aniq bittasi turadi — aks holda ular bir-birini uradi.
2. Farzin (0, 0) ga qo'yildi. Keyingi qatorga o'tamiz.
3. 1-qatorning 0-ustuni yaramaydi: yuqoridagi farzin uni uradi. Bu variantdan keyingi HAMMA joylashuv o'chadi — kesish shu.
4. 1-qatorning 1-ustuni yaramaydi: yuqoridagi farzin uni uradi. Bu variantdan keyingi HAMMA joylashuv o'chadi — kesish shu.
5. Farzin (1, 2) ga qo'yildi. Keyingi qatorga o'tamiz.
6. 2-qatorning 0-ustuni yaramaydi: yuqoridagi farzin uni uradi. Bu variantdan keyingi HAMMA joylashuv o'chadi — kesish shu.
7. 2-qatorning 1-ustuni yaramaydi: yuqoridagi farzin uni uradi. Bu variantdan keyingi HAMMA joylashuv o'chadi — kesish shu.
8. 2-qatorning 2-ustuni yaramaydi: yuqoridagi farzin uni uradi. Bu variantdan keyingi HAMMA joylashuv o'chadi — kesish shu.
9. 2-qatorning 3-ustuni yaramaydi: yuqoridagi farzin uni uradi. Bu variantdan keyingi HAMMA joylashuv o'chadi — kesish shu.
10. (1, 2) dan yechim chiqmadi — farzin olib tashlanadi va keyingi ustun sinaladi. Bu ORQAGA QAYTISH.
11. Farzin (1, 3) ga qo'yildi. Keyingi qatorga o'tamiz.
12. 2-qatorning 0-ustuni yaramaydi: yuqoridagi farzin uni uradi. Bu variantdan keyingi HAMMA joylashuv o'chadi — kesish shu.
13. Farzin (2, 1) ga qo'yildi. Keyingi qatorga o'tamiz.
14. 3-qatorning 0-ustuni yaramaydi: yuqoridagi farzin uni uradi. Bu variantdan keyingi HAMMA joylashuv o'chadi — kesish shu.
15. 3-qatorning 1-ustuni yaramaydi: yuqoridagi farzin uni uradi. Bu variantdan keyingi HAMMA joylashuv o'chadi — kesish shu.
16. 3-qatorning 2-ustuni yaramaydi: yuqoridagi farzin uni uradi. Bu variantdan keyingi HAMMA joylashuv o'chadi — kesish shu.
17. 3-qatorning 3-ustuni yaramaydi: yuqoridagi farzin uni uradi. Bu variantdan keyingi HAMMA joylashuv o'chadi — kesish shu.
18. (2, 1) dan yechim chiqmadi — farzin olib tashlanadi va keyingi ustun sinaladi. Bu ORQAGA QAYTISH.
19. 2-qatorning 2-ustuni yaramaydi: yuqoridagi farzin uni uradi. Bu variantdan keyingi HAMMA joylashuv o'chadi — kesish shu.
20. 2-qatorning 3-ustuni yaramaydi: yuqoridagi farzin uni uradi. Bu variantdan keyingi HAMMA joylashuv o'chadi — kesish shu.
21. (1, 3) dan yechim chiqmadi — farzin olib tashlanadi va keyingi ustun sinaladi. Bu ORQAGA QAYTISH.
22. (0, 0) dan yechim chiqmadi — farzin olib tashlanadi va keyingi ustun sinaladi. Bu ORQAGA QAYTISH.
23. Farzin (0, 1) ga qo'yildi. Keyingi qatorga o'tamiz.
24. 1-qatorning 0-ustuni yaramaydi: yuqoridagi farzin uni uradi. Bu variantdan keyingi HAMMA joylashuv o'chadi — kesish shu.
25. 1-qatorning 1-ustuni yaramaydi: yuqoridagi farzin uni uradi. Bu variantdan keyingi HAMMA joylashuv o'chadi — kesish shu.
26. 1-qatorning 2-ustuni yaramaydi: yuqoridagi farzin uni uradi. Bu variantdan keyingi HAMMA joylashuv o'chadi — kesish shu.
27. Farzin (1, 3) ga qo'yildi. Keyingi qatorga o'tamiz.
28. Farzin (2, 0) ga qo'yildi. Keyingi qatorga o'tamiz.
29. 3-qatorning 0-ustuni yaramaydi: yuqoridagi farzin uni uradi. Bu variantdan keyingi HAMMA joylashuv o'chadi — kesish shu.
30. 3-qatorning 1-ustuni yaramaydi: yuqoridagi farzin uni uradi. Bu variantdan keyingi HAMMA joylashuv o'chadi — kesish shu.
31. Farzin (3, 2) ga qo'yildi. Keyingi qatorga o'tamiz.
32. Yechim topildi. Jami 26 ta joylashtirish urinishi ketdi. To'liq izlash 4! = 24 ta tayyor joylashuvni oxirigacha qurgan bo'lardi.

0

1

2

3

To'rtta farzin, to'rtta qator. Har qatorda aniq bittasi turadi — aks holda ular bir-birini uradi.

Urinish0

OrqagaO‘ynatishOldinga1/32Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

21 / 40

MasalaFarzinlar masalasini backtracking bilan yeching.

Taklif qilingan yechim

1. 1Har qatorga bittadan farzin qo‘yamiz.
2. 2Qo‘yishdan oldin ustun va ikki diagonal band emasligini tekshiramiz.
3. 3Bo‘sh bo‘lsa belgilaymiz va keyingi qatorga o‘tamiz.
4. 4Chaqiruv qaytgach keyingi ustunni sinaymiz.

Bu javobning 4-qismi noto'g'ri. Keyingi ustunni sinashdan oldin oldingi farzinning izlari TOZALANISHI kerak: ustun va ikki diagonal to'plamidan olib tashlanadi. Tozalanmasa, taxta borgan sari «band» bo'lib boradi va yechimlar soni kam chiqadi — n = 8 da 92 o'rniga bir nechta.

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1Backtracking sxemasining uch qadami qanday?

Javobni ko'rish

Variantni qo’y, chuqurroq kir, qo’yganingni olib tashla. Uchinchisi — holatni tiklash — eng ko’p unutiladigani.

2Kesish nima beradi?

Javobni ko'rish

Yaroqsiz qisman yechim davom ettirilmaydi, ya’ni o’sha shoxdagi barcha to’liq yechimlar bir zarbada tashlanadi. Ish hajmi n! dan ancha pastga tushadi.

3Nega diagonal uchun i - j va i + j ishlatiladi?

Javobni ko'rish

Bir yo’nalishdagi diagonalda i - j barcha kataklarda bir xil, ikkinchisida i + j. Shu sababli diagonal bandligini bitta son bilan belgilash mumkin.

4Bu darsda rekursiya nega xavfsiz?

Javobni ko'rish

Chuqurlik n ga teng, n esa kichik (odatda 20 dan oshmaydi). 18 va 20-darslarda chuqurlik uchlar soniga tenglashardi — farq shunda.

5Kesishni kuchaytirishning umumiy yo'li qanday?

Javobni ko'rish

Qisman yechim yaroqsiz ekanini imkon qadar erta aniqlash. Qancha erta sezilsa, shuncha katta shox tashlanadi.

Masalalar

Masalalar

3 ta

• Chessboard and QueensCSES 1624o'rta

  Darsdagi masala, ustiga ba‘zi kataklar taqiqlangan. Tekshiruvga bitta shart qo‘shiladi.

• Grid PathsCSES 1625qiyin

  Kesishsiz umuman o‘tmaydi. Ikkita kuchli kesish bor: tupikka kirish va maydonni ikkiga bo‘lib qo‘yish.

• Fox And Two DotsCodeforces 510Bo'rta

  Panjarada halqa qidirilmoqda. Kezish paytida OTASI bo‘lmagan ko‘rilgan katakka duch kelsangiz — halqa bor.

Lokal mashq: mashqlar/21-farzinlar/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

4 × 4 taxtada to’rtta farzinni qo’lda joylashtiring. Nechta marta orqaga qaytdingiz? Ikkala yechimni ham toping va ular bir-birining ko’zgudagi aksi ekanini tekshiring.

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

21-farzinlar masalasini yeching. sekin.py va tez.py ni n = 8 da o’lchang — farq necha barobar chiqdi?

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Yechimingizga hisoblagich qo’shing: qoy() funksiyasi necha marta chaqirilgan? Uni n = 8 uchun 8! = 40320 bilan solishtiring. Keyin holatni tiklashni ataylab o’chirib, javob qanday buzilishini yozing.

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim