Vaqt murakkabligi
O(N!)
N ta farzin muammosi quyidagi savolni qo‘yadi: N×N o‘lchamdagi shaxmat taxtasiga bir-biriga tahdid solmaydigan qilib N ta farzinni qanday joylashtirish mumkin?
Farzin bir xil satr, ustun yoki diagonalda joylashgan istalgan donani ura oladi. Shuning uchun yechimda hech qanday ikkita farzin bir xil satr, ustun yoki diagonalda joylashmasligi kerak.
Qanday ishlaydi (Backtracking — ortga qaytish):
1. Farzinlarni satrma-satr joylashtirish
2. Har bir satr uchun barcha ustunlarni sinab ko‘rish
3. Tanlangan joy xavfsiz ekanini (ziddiyat yo‘qligini) tekshirish
4. Agar joy xavfsiz bo‘lsa, farzinni joylashtirib, keyingi satrga o‘tish
5. Agar xavfsiz ustun topilmasa, oldingi satrga qaytib, farzin joylashuvini o‘zgartirish
Ushbu vizualizatsiyada 4×4 o‘lchamdagi taxtada 4 ta farzinni joylashtirish muammosi ko‘rsatilgan.
Vaqt murakkabligi: O(N!) — eng yomon holatda
Xotira murakkabligi: O(N²) — taxtani saqlash uchun
N ta farzin muammosi ortga qaytish algoritmlari va cheklovlarni qanoatlantirish masalalarining klassik namunasidir.
O'xshash algoritmlar
Ko'p beriladigan savollar
- N ta farzin muammosi nima?
- N ta farzin muammosi quyidagi savolni qo‘yadi: N×N o‘lchamdagi shaxmat taxtasiga bir-biriga tahdid solmaydigan qilib N ta farzinni qanday joylashtirish mumkin?
- N ta farzin muammosi murakkabligi qanday?
- Vaqt (o'rtacha): O(N!) · Xotira: O(N²)
- Ushbu N ta farzin muammosi vizualizatori kimlar uchun?
- N ta farzin muammosi vizualizatsiyasi "Qaytish orqali qidirish" kategoriyasida yuqori darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.
- N ta farzin muammosi ga o'xshash qanday algoritmlar bor?
- Shu kategoriyada (Qaytish orqali qidirish) quyidagilarni ko'rishingiz mumkin: Sudoku Solver, Maze Pathfinding. Har biri interaktiv vizualizatsiyaga ega.