N-Queens II

N-Ferzi masalasida n x n shaxmat taxtasiga n ta ferzini shunday joylashtirish kerakki, ularning biortasi boshqasini shoh (tahdid) qilmasin.

Sizga n berilgan. Bunday joylashtirishlar sonini toping va qaytaring.

func solve(n int) int {
    // ...
}

Misollar

Input: n = 4
Output: 2
Tushuntirish: 4 x 4 taxtasida ferzlarni shart bilan joylashtirishning 2 xil usuli bor.

Input: n = 1
Output: 1

Input: n = 5
Output: 10

Maslahatlar

1. Bu klassik backtracking (orqaga qaytish) masalasi — ferzilarni qatorma-qator joylashtirib boring, har bir qatorda faqat bitta ferzi bo'ladi, shuning uchun faqat ustunlar va ikkala diagonal bo'yicha to'qnashuvni tekshirish kifoya.
2. Har bir ustun uchun cols[], har bir "/" diagonal uchun row+col, har bir "" diagonal uchun row-col+n (manfiy bo'lmasligi uchun n qo'shiladi) qiymatlaridan foydalanib band joylarni belgilovchi uchta bool massiv yuriting. Qatorni to'ldirishda mos ustun/diagonal band bo'lmasa uni band deb belgilab keyingi qatorga o'ting, qaytishda esa belgini qaytadan bo'shating (backtrack); barcha n qator to'ldirilganda hisoblagichni oshiring.