Tarkibga o'tish

N-vazir

N × N shaxmat taxtasiga N ta vazir (queen) shunday joylashtirilsinki, hech biri boshqasini ura olmasin.

Vazir: bir xil qator, ustun yoki diagonal bo'ylab istalgan masofaga yurishi mumkin.

Barcha mumkin bo'lgan joylashtirish variantlarini toping.

Kirish: N = 4

Bitta yechim:
  . Q . .
  . . . Q
  Q . . .
  . . Q .

Boshqa yechim:
  . . Q .
  Q . . .
  . . . Q
  . Q . .

Chiqish: 2 ta yechim

Kirish: N = 1
Chiqish: [[Q]]   // 1 ta yechim

Kirish: N = 2
Chiqish: []   // yechim yo'q

Kirish: N = 3
Chiqish: []   // yechim yo'q

Asosiy g'oya: qator bo'ylab backtracking

Har qatorda aynan bitta vazir bo'lishi kerak (N ta qatorda N ta vazir). Shuning uchun qator bo'ylab ketamiz — har qatorda bitta vazirni qaysi ustunda joylashtirish kerakligini tanlaymiz.

Backtracking:

  1. 0-qatordan boshlaymiz.
  2. Har qator uchun har ustunni sinab ko'ramiz.
  3. Agar pozitsiya xavfsiz bo'lsa — vazirni joylashtiramiz va keyingi qatorga o'tamiz.
  4. Agar N-qatorgacha yetsak — yechim topildi.
  5. Xavfsiz pozitsiya topilmasa — orqaga qaytib, oldingi qatorda boshqa ustunni sinab ko'ramiz.

Xavfsizlik tekshiruvi

Yangi vazir (row, col) ga joylashtirilsa, oldingi vazirlar bilan to'qnashishini tekshirish:

  • Bir xil ustun: queens[r] = col — r qatordagi vazir shu ustunda.
  • Diagonal (chapdan o'ngga): queens[r] - r = col - row → queens[r] - col = r - row
  • Diagonal (o'ngdan chapga): queens[r] + r = col + row → queens[r] - col = -(r - row) → |queens[r] - col| = |r - row|

Sodda: |queens[r] - col| = |r - row| — diagonallik shartidir. Ustun shartiys: queens[r] = col.

FUNCTION IS_SAFE(queens, row, col)
    FOR r = 0 DAN row - 1 GACHA
        IF queens[r] = col
            RETURN FALSE   // bir xil ustun
        IF ABS(queens[r] - col) = ABS(r - row)
            RETURN FALSE   // diagonal
    RETURN TRUE

Pseudocode

FUNCTION SOLVE_N_QUEENS(n)
    result = bo'sh list
    queens = n ta -1 qiymatdan iborat array   // queens[r] = r-qatordagi vazir ustuni
    BACKTRACK(n, 0, queens, result)
    RETURN result

FUNCTION BACKTRACK(n, row, queens, result)
    IF row = n
        // Barcha qatorlar joylashtirildi
        result ga queens dan qurigan taxtani qo'sh
        RETURN

    FOR col = 0 DAN n - 1 GACHA
        IF IS_SAFE(queens, row, col)
            queens[row] = col            // joylashtirish
            BACKTRACK(n, row + 1, queens, result)
            queens[row] = -1             // bekor qilish

Bosqichma-bosqich dry run: N = 4

queens = [-1, -1, -1, -1]

row=0: col 0,1,2,3 sinab ko'ramiz

  col=0: safe? (birinchi qator, doim xavfsiz) → queens=[0,-1,-1,-1]

    row=1, col=0: queens[0]=0, 0=0 → bir xil ustun → SKIP
    col=1: ABS(0-1)=1, ABS(0-1)=1 → diagonal → SKIP
    col=2: ustun OK. diagonal: ABS(0-2)=2, ABS(0-1)=1 → OK → queens=[0,2,-1,-1]

      row=2, col=0: ABS(0-0)=0=0? diagonal: ABS(2-0)=2, ABS(1-2)=1 → no
              ustun: queens[0]=0=0 → bir xil ustun → SKIP
      col=1: queens[1]=2≠1 OK; ABS(2-1)=1, ABS(1-2)=1 → diagonal → SKIP
      col=2: queens[1]=2=2 → bir xil ustun → SKIP
      col=3: queens[0]=0≠3 OK; ABS(0-3)=3, ABS(0-2)=2 → OK
             queens[1]=2≠3 OK; ABS(2-3)=1, ABS(1-2)=1 → diagonal → SKIP
      Hech narsa topilmadi → qaytish

    queens=[0,-1,-1,-1]
    col=3: ABS(0-3)=3, ABS(0-1)=1 → OK → queens=[0,3,-1,-1]

      row=2, col=0: queens[0]=0=0 → SKIP
      col=1: queens[0]=0≠1 OK, diagonal: ABS(0-1)=1=ABS(0-2)=2? NO → OK
             queens[1]=3≠1 OK, diagonal: ABS(3-1)=2=ABS(1-2)=1? NO → OK → queens=[0,3,1,-1]

        row=3, col=0: queens[0]=0=0 → SKIP
        col=1: queens[2]=1=1 → SKIP
        col=2: queens[0]=0≠2 OK, diag: ABS(0-2)=2=ABS(0-3)=3? NO → OK
               queens[1]=3≠2 OK, diag: ABS(3-2)=1=ABS(1-3)=2? NO → OK
               queens[2]=1≠2 OK, diag: ABS(1-2)=1=ABS(2-3)=1? YES → diagonal → SKIP
        col=3: queens[1]=3=3 → SKIP
        Topilmadi → qaytish

      col=2: ...
      col=3: queens[1]=3=3 → SKIP

    queens=[0,-1,-1,-1]

  col=1: queens=[1,-1,-1,-1]
    row=1, col=3: → queens=[1,3,-1,-1]
      row=2, col=0: → queens=[1,3,0,-1]
        row=3, col=2: → queens=[1,3,0,2]
          row=4=N → YECHIM TOPILDI!

Birinchi yechim: queens=[1,3,0,2]
  Qator 0: ustun 1 → . Q . .
  Qator 1: ustun 3 → . . . Q
  Qator 2: ustun 0 → Q . . .
  Qator 3: ustun 2 → . . Q .

Natijani qurish

queens massividan taxtani matritsa sifatida quriladi:

FUNCTION BUILD_BOARD(queens, n)
    board = bo'sh list
    FOR r = 0 DAN n - 1 GACHA
        row = n ta '.' belgisidan iborat array
        row[queens[r]] = 'Q'
        board ga row ni qo'sh
    RETURN board

Optimallashtirilgan: set bilan tekshirish

Har tekshiruvda O(row) vaqt. cols, diag1, diag2 set'lar bilan O(1):

FUNCTION SOLVE_N_QUEENS_FAST(n)
    result = bo'sh list
    queens = n ta -1 qiymatdan iborat array
    cols   = bo'sh set   // ishlatilgan ustunlar
    diag1  = bo'sh set   // r - c qiymatlari (chapdan-o'ng diagonal)
    diag2  = bo'sh set   // r + c qiymatlari (o'ngdan-chap diagonal)

    BACKTRACK(n, 0, queens, cols, diag1, diag2, result)
    RETURN result

FUNCTION BACKTRACK(n, row, queens, cols, diag1, diag2, result)
    IF row = n
        result ga queens dan taxtani qo'sh
        RETURN

    FOR col = 0 DAN n - 1 GACHA
        IF col cols ichida     CONTINUE
        IF (row-col) diag1 ichida  CONTINUE
        IF (row+col) diag2 ichida  CONTINUE

        queens[row] = col
        cols ga col ni qo'sh
        diag1 ga (row - col) ni qo'sh
        diag2 ga (row + col) ni qo'sh

        BACKTRACK(n, row + 1, queens, cols, diag1, diag2, result)

        queens[row] = -1
        cols dan col ni olib tashla
        diag1 dan (row - col) ni olib tashla
        diag2 dan (row + col) ni olib tashla

Set tekshiruvi O(1) shuning uchun bu versiya har qator uchun O(n) o'rniga O(n) qoladi, lekin doimiy koeffitsient kichikroq.

Vaqt va xotira murakkabligi

Xususiyat Qiymat Izoh
Vaqt O(n!) worst case Pruning bilan amalda kamroq
Xotira O(n) Rekursiya chuqurligi + queens array

Yechimlar soni: N=4 → 2, N=5 → 10, N=6 → 4, N=8 → 92, N=12 → 14200. Tez o'sadi, lekin barcha variantlar eksponensialdan kamroq — pruning kuchli ishlaydi.

Edge case'lar

N = 1: bitta yechim: [[Q]].

N = 2, N = 3: yechim yo'q — [].

N = 4: 2 ta yechim.

Katta N: N = 15 da 2 279 184 ta yechim. Ularni natijaga yig'ish ko'p xotira oladi. Ba'zan faqat yechimlar sonini sanash (massivga yozmasdan) talab qilinadi.

N-vazir faqat yechimlar soni (N-Queens II)

Barcha taxtalarni tuzmasdan, faqat soni:

FUNCTION TOTAL_N_QUEENS(n)
    count  = 0
    queens = n ta -1 qiymatdan iborat array
    cols   = bo'sh set
    diag1  = bo'sh set
    diag2  = bo'sh set

    FUNCTION BACKTRACK(row)
        IF row = n
            count = count + 1
            RETURN

        FOR col = 0 DAN n - 1 GACHA
            IF col cols ichida YOKI ...
                CONTINUE
            // tanlash, rekursiya, bekor qilish

    BACKTRACK(0)
    RETURN count

Pruningning kuchi

N=8 uchun: - Pruningsiz: 8^8 = 16 777 216 variant - Faqat ustun tekshiruvi bilan: 8! = 40 320 - Barcha cheklovlar bilan: ~2000 ta tekshiruv

Bu pruning algoritmni qanchalik tezlashtirganini ko'rsatadi.

Xulosa

N-vazir — backtracking ning eng mashhur masalasi. Qator bo'ylab harakat qilinadi, har qatorda xavfsiz ustun tanlanadi. Xavfsizlik: bir xil ustun va diagonal bo'ylab to'qnashuv yo'q.

Optimallashtirilgan versiyada cols, diag1, diag2 set'lari bilan har tekshiruv O(1). Pruning kuchli — amalda n! dan ancha kam variant tekshiriladi.