Backtracking chuqur va kesish (pruning): N-Queens, Sudoku, so'z qidirish

Qisqacha: Kesish (pruning) — shox javob bermasligi aniq bo'lgan zahoti unga tushmaslik. Sodda backtracking hamma variantni oxirigacha quradi va faqat keyin tekshiradi. Kesish bilan esa qoida har tanlovda tekshiriladi: yomon tanlov butun pastki daraxti bilan birga tashlab yuboriladi. Masalan, 8 farzin masalasida bu 19 million tugunni 2 057 taga, vaqtni 233 ms dan ≈ 1 ms ga tushirdi. Eng yomon holat baribir eksponensial, lekin amalda farq — yuz va ming baravar. Uch asosiy usul: qoidani darhol tekshirish (O(1) uchun Set), saralab break qilish va eng tor joydan boshlash.

Bu darsda

• Kesish nima ekanini va u Big-O'ni emas, amaliy vaqtni o'zgartirishini tushuntira olasiz.
• N-Queens'ni Set bilan O(1) tekshiruvli backtracking orqali yecha olasiz.
• Jadvalda so'z qidirish va Sudoku yechuvchini "band qil → qidir → qaytar" qolipida yoza olasiz.
• Combination sum'da saralash va break bilan kesishni qo'llay olasiz, tugunlarni sanab samarasini o'lchaysiz.

Oldin bilishingiz kerak: Backtracking asoslari, Matritsa bilan ishlash, Set.

1. Nega bu kerak?

O'tgan darsning 2-mashqida byudjetga sig'adigan kombolarni sanagan edik: avval hamma 32 ta qism-to'plam yasaldi, keyin filtrlandi. Salat va somsa olingach, boshqa hech narsa sig'masligi aniq edi — lekin dastur baribir o'sha shoxning har bir variantini oxirigacha qurdi.

Endi Jasur aka murakkabroq narsa so'radi: "Mehmon 20 000 so'mlik aniq to'plam olsin: choy 5 000, somsa 8 000, non 4 000, salat 12 000. Bitta taomni bir necha marta olsa ham bo'ladi. Qanday to'plamlar bor?" Bu yerda variantlar cheksiz: non, non, non… Har shoxni oxirigacha qurish umuman mumkin emas — qayerdadir to'xtash kerak.

Bugungi g'oya oddiy: shoxning kelajagi yo'qligini qanchalik erta bilsak, shuncha kam ish qilamiz. Bu — kesish (pruning): daraxt bog'bonining keraksiz shoxni tubidan kesishi kabi. Bitta kesilgan shox bilan uning hamma bargi ham yo'qoladi.

2. Combination sum: birinchi kesish

2.1 Ikki versiya

Eng sodda versiya ham bitta tekshiruvsiz ishlamaydi: yig'indi maqsaddan oshganda to'xtash shart, aks holda "non, non, non…" cheksiz davom etadi. Lekin u oshib ketishni faqat qo'shib bo'lgandan keyin biladi. Yaxshiroq versiya narxlarni saralaydi va qo'shishdan oldin tekshiradi:

const prices = [5000, 8000, 4000, 12000]; // choy, somsa, non, salat
const target = 20000;

function comboSumNaive(prices, target) {
  const result = [];
  const current = [];
  let nodes = 0;
  function backtrack(start, sum) {
    nodes++;
    if (sum > target) return; // oshib ketdi — endi bildik
    if (sum === target) {
      result.push([...current]);
      return;
    }
    for (let i = start; i < prices.length; i++) {
      current.push(prices[i]);
      // i (i + 1 emas): bitta taom qayta olinishi mumkin
      backtrack(i, sum + prices[i]);
      current.pop();
    }
  }
  backtrack(0, 0);
  return { count: result.length, nodes };
}

function comboSumPruned(prices, target) {
  const sorted = prices.toSorted((a, b) => a - b);
  const result = [];
  const current = [];
  let nodes = 0;
  function backtrack(start, remaining) {
    nodes++;
    if (remaining === 0) {
      result.push([...current]);
      return;
    }
    for (let i = start; i < sorted.length; i++) {
      // kesish: bu narx sig'masa, keyingilari undan ham qimmat
      if (sorted[i] > remaining) break;
      current.push(sorted[i]);
      backtrack(i, remaining - sorted[i]);
      current.pop();
    }
  }
  backtrack(0, target);
  return { count: result.length, nodes, first: result[0] };
}

console.log(comboSumNaive(prices, target));
console.log(comboSumPruned(prices, target));

Konsolda:

{ count: 6, nodes: 58 }
{ count: 6, nodes: 30, first: [ 4000, 4000, 4000, 4000, 4000 ] }

Ikkalasi ham 6 ta to'plam topdi, lekin ikkinchisi ikki baravar kam tugunga kirdi. Farq ikki joyda:

• Birinchisi sum > target ni chaqiruv ichida tekshiradi — ya'ni "yomon" chaqiruv baribir sodir bo'ladi va stekka tushadi. Ikkinchisi chaqiruvdan oldin tekshiradi: yomon tugun umuman yaratilmaydi.
• Narxlar saralangan. Agar 12 000 qolgan pulga sig'masa, undan keyingilar (undan qimmatlar) ham sig'maydi. Shuning uchun continue emas, break — siklning qolgan qismi ham kesiladi.

Bu yerdagi backtrack(i, …) ga e'tibor bering: kombinatsiyalarda i + 1 edi, endi i. Joriy taom qayta tanlanishi mumkin, lekin chapdagilar — yo'q, shuning uchun [4 000, 5 000] va [5 000, 4 000] ikki marta chiqmaydi.

2.2 Kesish nimani o'zgartiradi?

Kesish javobni o'zgartirmaydi — faqat yo'lni qisqartiradi. To'g'ri kesish faqat javobsiz shoxlarni tashlaydi. Agar u javobli shoxni ham kessa — bu kesish emas, xato.

Big-O ham ko'pincha o'zgarmaydi: eng yomon holat baribir eksponensial. Lekin amalda kesilgan daraxt ko'p marta kichik. Maqsadni oshirib ko'rdik:

Bu masalada kesish 1,2–2 baravar yutuq berdi — chunki daraxtning ko'p qismi haqiqatan javob beradi. Kesishning kuchi masalaga bog'liq. Keyingi masalada u ming baravar bo'ladi.

Tekshirib ko'ring: Sardor saralashni unutdi: narxlar [12000, 4000, 8000], qolgan pul 5 000. Sikl birinchi narxda — 12 000 da — break qiladi. Nima yo'qoladi?

3. N-Queens: qoidani darhol tekshirish

3.1 Masala

«Bahor» da mehmonlar uchun shaxmat burchagi ochildi. Devorga klassik boshqotirma osildi: 8×8 taxtaga 8 ta farzinni (queen) shunday qo'yingki, hech biri boshqasini ura olmasin. Farzin o'z qatori, ustuni va ikkala diagonali bo'ylab uradi. Bu — N-Queens masalasi: n×n taxtada n ta farzin.

Har qatorda aynan bitta farzin bo'ladi (ikkitasi bir qatorda bo'lsa — urishadi). Demak, tanlov: har qator uchun ustun.

3.2 Sodda yechim: oxirida tekshirish

Har qatorga istalgan ustunni qo'yib, n qatorni to'ldiramiz, keyin hamma juftlarni tekshiramiz. Bu n × n × … × n = nⁿ ta joylashtirish. 8 da — 16,7 million; har birini to'liq qurish uchun daraxtda 19 million tugun.

3.3 Kesish: band ustun va diagonallar

Farzin qo'yishdan oldin tekshiramiz: shu ustun yoki diagonalda farzin bormi? Bor bo'lsa — bu katakni o'tkazib yuboramiz va uning ostidagi butun daraxtga tushmaymiz.

Tekshiruvni O(1) qilish uchun band chiziqlarni uchta Set da saqlaymiz. Ustun — col. Diagonallar uchun hiyla bor: bitta "\" diagonaldagi hamma kataklarda row - col bir xil, bitta "/" diagonalda esa row + col bir xil. Masalan, (0, 1), (1, 2), (2, 3) — row - col uchalasida −1.

Nega shunday? "\" diagonal bo'ylab bir katak pastga tushsangiz, qator ham, ustun ham bittaga oshadi — ayirma o'zgarmaydi. "/" diagonalda esa qator oshadi, ustun kamayadi — yig'indi o'zgarmaydi. 4×4 taxtada row - col qiymatlari:

       col: 0   1   2   3
row 0:      0  -1  -2  -3
row 1:      1   0  -1  -2
row 2:      2   1   0  -1
row 3:      3   2   1   0

Bir xil son — bitta "\" diagonal. Demak, diagonalni bitta son bilan eslab qolish mumkin, Set.has esa uni O(1) da tekshiradi. Qadamlarda 4×4 taxtani kuzating:

Uchinchi qadamdan keyin qiziq narsa yuz berdi: (0, 0) dagi farzin bilan 1- va 2-qatorlar to'lmaydigan bo'lib chiqdi. Algoritm orqaga qaytdi va birinchi farzinni (0, 1) ga ko'chirdi — keyin hammasi joyiga tushdi. 26 ta sinalgan katakdan 18 tasi birinchi tekshiruvdayoq kesildi.

3.4 O'lchov

Ikkala versiyani o'lchadik — hamma yechimlarni sanash bilan (benchmarking darsidagi usul: har n alohida jarayonda, isitish, 5 o'lchov medianasi). Avval tugunlar soni — u kompyuterga bog'liq emas, aniq sanaldi:

Endi vaqt:

8 farzinda kesish tugunlarni 9 300 baravar, vaqtni ≈ 250 baravar kamaytirdi. Sodda versiyada n bittaga oshganda vaqt 17–21 baravar oshdi (nⁿ); kesishli versiyada — 4–5 baravar. Kesishli versiya ham eksponensial (12 da allaqachon 0,4 s), lekin chegarani 8 dan 12–13 gacha surdi.

Tekshirib ko'ring: (2, 1) va (0, 3) kataklaridagi farzinlar bir-birini uradimi? Qaysi Set buni ushlaydi?

4. Jadvalda so'z qidirish

4.1 Masala

Bolalar burchagi uchun Sardor harflar o'yinini yozyapti: jadvalda so'z yashiringan, uni qo'shni kataklar (o'ng, past, chap, tepa) bo'ylab o'qish mumkin, har katak bir marta. "OSH" bormi?

Bu backtracking'ning yana bir ko'rinishi. Tanlov — keyingi qo'shni katak. Kesish — katakdagi harf so'zdagi navbatdagi harfga mos kelmasa, shu zahoti qaytish. Yo'nalishlar massivi [[0, 1], [1, 0], …] — Matritsa bilan ishlash darsidan tanish.

4.2 Band qil, qidir, qaytar

"Har katak bir marta" shartini qanday tekshiramiz? Alohida visited massivi o'rniga ko'p ishlatiladigan hiyla: katakni vaqtincha "#" bilan almashtiramiz. "#" hech qaysi harfga teng emas, shuning uchun shu yo'lda unga qayta kirib bo'lmaydi. Qaytishda harfni joyiga qo'yamiz — bu "bekor qil" qadami:

Birinchi "O" (0, 0) dan boshlangan yo'l "OS" gacha bordi, lekin (0, 1) ning qo'shnilarida "H" yo'q edi — boshi berk. Algoritm "S" ni qaytardi, keyin "O" ni ham qaytardi va keyingi boshlang'ich katakka o'tdi. Oxirida jadval asl holatida: hamma "#" harfga qaytdi.

4.3 Murakkablik

Har boshlang'ich katakdan (m × n ta) qidiruv eng ko'pi bilan har qadamda 3 yo'nalishga tarmoqlanadi (kelgan katakka qaytish — "#" tufayli darhol kesiladi). So'z uzunligi L bo'lsa: O(m · n · 3ᴸ) eng yomon holatda. Amalda harflar mos kelmagani uchun shoxlarning ko'pi birinchi qadamdayoq kesiladi. Xotira — O(L): rekursiya chuqurligi so'z uzunligicha.

5. Sudoku

5.1 Qoidalar va yechuvchi

Sudoku: 9×9 jadval, har qator, har ustun va har 3×3 kvadratda 1 dan 9 gacha raqamlar bittadan. Ba'zi kataklar oldindan to'ldirilgan, qolganlarini topish kerak.

Kesishsiz yondashuv aql bovar qilmaydigan: 56 ta bo'sh katakka 9 tadan raqam — 9⁵⁶ ≈ 10⁵³ variant. Kesish bilan esa — har raqamni qo'yishdan oldin uchta qoidani tekshiramiz:

const puzzle = [
  "8....57..",
  "32..1.8..",
  "......32.",
  "46...7...",
  "2...9....",
  ".......5.",
  "....7..8.",
  "...98...2",
  ".84.3.5.1",
];
// "." — bo'sh katak (0)
const board = puzzle.map((row) =>
  [...row].map((ch) => Number(ch) || 0),
);

function canPlace(r, c, d) {
  for (let i = 0; i < 9; i++) {
    if (board[r][i] === d || board[i][c] === d) return false;
  }
  const br = r - (r % 3); // 3×3 kvadratning chap-yuqori burchagi
  const bc = c - (c % 3);
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (board[br + i][bc + j] === d) return false;
    }
  }
  return true;
}

let nodes = 0;
function solve(pos) {
  nodes++;
  if (pos === 81) return true; // hamma katak to'ldi
  const r = Math.floor(pos / 9);
  const c = pos % 9;
  if (board[r][c] !== 0) return solve(pos + 1); // berilgan raqam
  for (let d = 1; d <= 9; d++) {
    if (!canPlace(r, c, d)) continue; // kesish: qoida buziladi
    board[r][c] = d;
    if (solve(pos + 1)) return true;
    board[r][c] = 0; // bekor qil
  }
  return false;
}

console.log(solve(0), nodes);
console.log(board.map((row) => row.join("")).join("\n"));

Konsolda:

true 1353
846325719
325719846
179468325
461257938
257893164
938146257
692571483
513984672
784632591

10⁵³ o'rniga 1 353 ta chaqiruv. Har raqam qo'yilishidan oldin qator, ustun va kvadrat tekshiriladi — noto'g'ri raqam butun pastki daraxti bilan kesiladi.

5.2 Eng tor joydan boshlash

Yechuvchimiz bo'sh kataklarni chapdan o'ngga, yuqoridan pastga to'ldiradi. Aqlliroq tartib bor: har safar eng kam variantli katakni tanlash. Agar bitta katakka faqat bitta raqam sig'sa — avval uni qo'yamiz; birorta raqam sig'masa — shu zahoti orqaga qaytamiz, qolgan kataklarni ko'rmasdan. Bunday qoida evristika (heuristic) deyiladi: u eng yaxshi tartibni kafolatlamaydi, lekin amalda ko'pincha juda yaxshi ishlaydi. Bu evristikaning nomi — MRV (minimum remaining values — "eng kam qolgan qiymatlar").

Shu jumboqni MRV bilan ham yechib ko'rdik: tugunlar 947 dan 57 ga tushdi (ikkala versiya ham bo'sh kataklarni sanagan, berilgan raqamlarni emas). Har tugunda biroz ko'proq ish bor (har bo'sh katak uchun variantlarni sanash), lekin qidiruv daraxti 16 baravar kichik. Odamlar ham sudokuni shunday yechadi: avval "bitta raqam sig'adigan" kataklarni to'ldiradi.

6. Kesish usullari

Uch masaladan umumiy qoidalar chiqadi. Ularni yangi masalaga kirishishdan oldin ro'yxat sifatida eslang: "qayerda erta bila olaman?"

Oxirgi qator — optimallashtirish masalalari uchun. Masalan, kuryerning eng qisqa yo'lini qidirayotganda, yarim yo'lning o'zi allaqachon topilgan eng yaxshi yo'ldan uzun bo'lsa — davom etishning ma'nosi yo'q. Bu usul branch and bound ("tarmoqlash va chegaralash") deb ataladi.

Diqqat: Kesish sharti to'g'ri bo'lishi shart. "Ehtimol bu yerda javob yo'q" deb kesish — tezlik uchun to'g'rilikni sotish. Har kesishga savol bering: "bu shoxda javob bo'lishi mumkin emasligi isbotlanganmi?"

7. Chegaraviy holatlar

• N-Queens, n = 2 va 3. Yechim yo'q — place hamma variantni kesib, false qaytaradi. n = 1 — bitta yechim.
• Bo'sh so'z. exists(grid, "") — search darhol i === word.length ga tushadi: true. Bu kelishuvga bog'liq; kerak bo'lsa alohida tekshiring.
• Bo'sh jadval. grid[0].length — grid bo'sh bo'lsa TypeError. Kirishni boshida tekshiring.
• Yechimsiz Sudoku. Ziddiyatli jumboqda yechuvchi hamma variantni sinab, false qaytaradi. Kesish tufayli bu ham tez bo'ladi.
• Nol yoki manfiy narx. Combination sum'da 0 so'mlik taom bo'lsa, backtrack(i, …) uni cheksiz qayta tanlaydi — remaining kamaymaydi. Narxlar musbat ekanini tekshiring.

8. Ko'p uchraydigan xatolar

8.1 Holatni qaytarishni unutish

So'z qidirishda topilganda return true dan oldin harfni qaytarmasangiz, jadvalda "#" qoladi — keyingi qidiruv buzuq jadval bilan ishlaydi. N-Queens'da Set dan o'chirishni unutsangiz, keyingi shoxlar mavjud bo'lmagan farzinlardan "qo'rqadi" va yechimlar yo'qoladi. Tuzatish: har add ga delete, har "#" ga harfni qaytarish — har chiqish yo'lida.

8.2 break va continue ni almashtirish

Saralanmagan ro'yxatda break — javoblarni yo'qotadi: arzon taom qimmatidan keyin turgan bo'lishi mumkin. Saralangan ro'yxatda continue — xato emas, lekin kesish yarim samarali. Qoida: break faqat "keyingilar baribir yomonroq" isbotlangan bo'lsa.

8.3 Tekshiruvni sekin qilish

Har farzin uchun hamma oldingi farzinlarni sikl bilan tekshirish — O(n) tekshiruv. Ishlaydi, lekin Set bilan O(1). Kesish tekshiruvi har tugunda bajariladi — u qanchalik arzon bo'lsa, shuncha yaxshi.

9. Mashqlar

1-mashq (oson): 4 farzin

4×4 taxtada 4 farzin masalasining nechta yechimi bor? Darsdagi jadvaldan yoki vizualdan foydalaning.

2-mashq (o'rta): Har taom bir marta

Combination sum'ni o'zgartiring: har taom ko'pi bilan bir marta olinadi, lekin ro'yxatda bir xil narxli taomlar bo'lishi mumkin (ikki xil choy — 5 000 dan). Narxlar: [5000, 5000, 8000, 4000, 12000, 3000], maqsad 20 000. Takroriy to'plamlar chiqmasin. Ishora: ikki o'zgarish — i + 1 va o'tgan darsdagi "bir qavatda bir xil elementni o'tkazib yuborish".

function comboSumOnce(prices, target) {
  const sorted = prices.toSorted((a, b) => a - b);
  const result = [];
  const current = [];
  function backtrack(start, remaining) {
    if (remaining === 0) {
      result.push([...current]);
      return;
    }
    for (let i = start; i < sorted.length; i++) {
      if (i > start && sorted[i] === sorted[i - 1]) continue;
      if (sorted[i] > remaining) break;
      current.push(sorted[i]);
      backtrack(i + 1, remaining - sorted[i]);
      current.pop();
    }
  }
  backtrack(0, target);
  return result;
}

const prices = [5000, 5000, 8000, 4000, 12000, 3000];
const sets = comboSumOnce(prices, 20000);
console.log(sets.map((s) => s.join("+")).join("\n"));

3000+4000+5000+8000
3000+5000+12000
8000+12000

3-mashq (qiyin): So'z qidirish va testlar

kurs/mashqlar/14/25-kesish/search.test.mjs faylida darsdagi exists ni yozing va yana bitta funksiya qo'shing: findPath(grid, word) — topilgan yo'lning kataklari ro'yxati ([[r, c], …]) yoki null. Testlar (node:test):

1. "OSH" — darsdagi jadvalda yo'l [[1, 1], [1, 2], [2, 2]].
2. Katak qayta ishlatilmaydi: [["N", "O"]] jadvalida "NON" yo'q.
3. Qidiruvdan keyin jadval o'zgarmagan.
4. Yo'q so'z — null.

// kurs/mashqlar/14/25-kesish/search.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

const DIRS = [[0, 1], [1, 0], [0, -1], [-1, 0]];

function findPath(grid, word) {
  const rows = grid.length;
  const cols = grid[0].length;
  const path = [];
  function search(r, c, i) {
    if (i === word.length) return true;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (grid[r][c] !== word[i]) return false;
    const letter = grid[r][c];
    grid[r][c] = "#";
    path.push([r, c]);
    for (const [dr, dc] of DIRS) {
      if (search(r + dr, c + dc, i + 1)) {
        grid[r][c] = letter;
        return true;
      }
    }
    grid[r][c] = letter;
    path.pop(); // bu katak yo'ldan chiqdi
    return false;
  }
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (search(r, c, 0)) return path;
    }
  }
  return null;
}

const exists = (grid, word) => findPath(grid, word) !== null;

const makeGrid = () => [
  ["O", "S", "T"],
  ["K", "O", "S"],
  ["A", "L", "H"],
];

test("OSH yo'li", () => {
  assert.deepEqual(findPath(makeGrid(), "OSH"),
    [[1, 1], [1, 2], [2, 2]]);
});

test("katak qayta ishlatilmaydi", () => {
  assert.equal(exists([["N", "O"]], "NON"), false);
  assert.equal(exists([["N", "O"], ["A", "N"]], "NON"), true);
});

test("qidiruvdan keyin jadval o'zgarmaydi", () => {
  const grid = makeGrid();
  exists(grid, "OSH");
  exists(grid, "SOL");
  assert.deepEqual(grid, makeGrid());
});

test("yo'q so'z — null", () => {
  assert.equal(findPath(makeGrid(), "NON"), null);
});

✔ OSH yo'li (1.3231ms)
✔ katak qayta ishlatilmaydi (0.1941ms)
✔ qidiruvdan keyin jadval o'zgarmaydi (0.1389ms)
✔ yo'q so'z — null (0.7239ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 88.4806

4-mashq: Amaliy tajriba — murakkablik jadvali

kurs/mashqlar/14/MURAKKABLIK.md ga N-Queens (sodda va kesish bilan), so'z qidirish va Sudoku qatorlarini qo'shing. "Amaliy chegara" ustuniga o'lchangan tugunlar sonini yozing.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| N farzin | hamma joylashtirish | O(nⁿ · n²) | O(n) |
| N farzin | kesish, 3 ta Set | O(n!) eng yomon | O(n) |
| So'z qidirish | backtracking, # bilan | O(m · n · 3ᴸ) | O(L) |
| Sudoku | backtracking + qoidalar | O(9ᵏ) eng yomon, k — bo'sh | O(k) |

git add 14/MURAKKABLIK.md 14/25-kesish
git commit -m "14/25: kesish — N farzin, so'z qidirish testlari"

10. Real ishda

• Cheklovlarni qanoatlantirish. Dars jadvali, smenalar grafigi, xonalarni band qilish, turnir taqvimi — hammasi "qoidalarni buzmasdan hamma narsani joylashtir" masalasi. Ularni yechadigan vositalar (constraint solver) ichida backtracking, kesish va MRV kabi evristikalar ishlaydi.
• O'yinlar. Shaxmat dasturlari qidiruv daraxtini alfa-beta kesish bilan qisqartiradi — bu "chegara" turidagi kesish. Boshqotirma yechuvchilar (Sudoku, krossvord) — aynan bugungi qolip.
• Kod tahlili. Regex dvigateli (a+)+ kabi naqshda aynan backtracking qiladi — kesishsiz. Regex amaliyotda va ReDoS darsidagi halokatli backtracking shu daraxtning portlashi edi.
• Intervyu. "51. N-Queens", "37. Sudoku Solver", "79. Word Search", "39. Combination Sum" — LeetCode'dagi klassik backtracking masalalari (leetcode.com/problems/n-queens). Intervyuda kod bilan birga "qayerda kesyapsiz?" savoli kutiladi.

Xulosa

• Kesish — javobsiz shoxga tushmaslik. U javobni emas, yo'lni o'zgartiradi; noto'g'ri kesish — xato.
• Tekshiruvni tanlovdan oldin qiling va arzon qiling: N-Queens'da col, row - col, row + col uchun uchta Set.
• O'lchov: 8 farzin — 19,2 mln tugun (≈ 233 ms) o'rniga 2 057 tugun (≈ 0,9 ms); Sudoku'da MRV tugunlarni 947 dan 57 ga tushirdi.
• "Band qil → qidir → qaytar": jadvalda "#", Set dan delete, path.pop() — har chiqishda holat tiklansin.
• Saralangan ro'yxatda break butun dumni kesadi; saralanmaganda — javoblarni yo'qotadi.

Keyingi dars: Bo'lib-yech (divide and conquer) — masalani mustaqil yarimlarga bo'lish, alohida yechish va birlashtirish: tez darajaga ko'tarish, eng yaqin juftlik g'oyasi va merge sort'ga ko'prik.

Manbalar

• Steven S. Skiena, "The Algorithm Design Manual", 3-nashr, Springer, 2020 — "Search Pruning" va "Sudoku" bo'limlari.
• Stuart Russell, Peter Norvig, "Artificial Intelligence: A Modern Approach", 4-nashr, 2020 — 6-bob (cheklovlarni qanoatlantirish, MRV).
• N-Queens yechimlari soni: OEIS A000170 — oeis.org/A000170
• LeetCode: 51. N-Queens, 37. Sudoku Solver, 79. Word Search, 39. Combination Sum — leetcode.com