rust_algorithms/other/

backtracking.rs

//! Backtracking — "sinab ko'r, bo'lmasa orqaga qayt".
//!
//! **Shablon:**
//!
//! ```text
//! fn qidir(holat):
//!     agar holat to'liq bo'lsa → javobga qo'sh, qaytish
//!     har bir mumkin bo'lgan qadam uchun:
//!         agar qadam qoidaga zid bo'lmasa:
//!             qadamni QO'YAMIZ
//!             qidir(yangi holat)      ← chuqurroq ketamiz
//!             qadamni OLIB TASHLAYMIZ ← backtrack!
//! ```
//!
//! Backtracking — bu **kesilgan** (pruned) to'liq izlash. Umid yo'q shoxni
//! erta tashlab yuborish algoritmni amalda ishlaydigan qiladi.

/// Barcha o'rin almashtirishlar (permutations).
///
/// `n` ta elementdan `n!` ta variant chiqadi.
///
/// - **Time:** O(n · n!), **Space:** O(n) (natijadan tashqari).
///
/// # Misol
/// ```
/// use rust_algorithms::other::backtracking::permutations;
///
/// let p = permutations(&[1, 2, 3]);
/// assert_eq!(p.len(), 6);
/// assert!(p.contains(&vec![2, 1, 3]));
/// ```
pub fn permutations<T: Clone>(items: &[T]) -> Vec<Vec<T>> {
    fn go<T: Clone>(hozir: &mut Vec<T>, qolgan: &mut Vec<T>, out: &mut Vec<Vec<T>>) {
        if qolgan.is_empty() {
            out.push(hozir.clone());
            return;
        }
        for i in 0..qolgan.len() {
            let x = qolgan.remove(i); // qadamni qo'yamiz
            hozir.push(x.clone());
            go(hozir, qolgan, out);
            hozir.pop(); // backtrack
            qolgan.insert(i, x);
        }
    }
    let mut out = Vec::new();
    go(&mut Vec::new(), &mut items.to_vec(), &mut out);
    out
}

/// Barcha qism to'plamlar (power set) — `2ⁿ` ta.
///
/// **G'oya:** har bir element uchun ikkita qaror — "olaman" yoki "olmayman".
///
/// # Misol
/// ```
/// use rust_algorithms::other::backtracking::subsets;
///
/// let s = subsets(&[1, 2, 3]);
/// assert_eq!(s.len(), 8);
/// assert!(s.contains(&vec![]));
/// assert!(s.contains(&vec![1, 3]));
/// ```
pub fn subsets<T: Clone>(items: &[T]) -> Vec<Vec<T>> {
    fn go<T: Clone>(items: &[T], i: usize, hozir: &mut Vec<T>, out: &mut Vec<Vec<T>>) {
        if i == items.len() {
            out.push(hozir.clone());
            return;
        }
        go(items, i + 1, hozir, out); // olmaymiz
        hozir.push(items[i].clone()); // olamiz
        go(items, i + 1, hozir, out);
        hozir.pop(); // backtrack
    }
    let mut out = Vec::new();
    go(items, 0, &mut Vec::new(), &mut out);
    out
}

/// **N vazir masalasi**: `n × n` shaxmat taxtasiga `n` ta vazirni bir-birini
/// urmaydigan qilib joylashning barcha usullari.
///
/// Vazir gorizontal, vertikal va diagonal bo'ylab yuradi.
///
/// **Optimallashtirish:** har bir qatorga aynan bitta vazir qo'yiladi, shuning uchun
/// faqat ustunlar va ikki diagonalni `bool` massivlarda kuzatib borish yetarli —
/// tekshiruv **O(1)**.
///
/// ```text
///  n = 4 uchun 2 ta yechim:
///   . Q . .        . . Q .
///   . . . Q        Q . . .
///   Q . . .        . . . Q
///   . . Q .        . Q . .
/// ```
///
/// Qaytadi: har bir yechim — `qator → ustun` massivi.
///
/// # Misol
/// ```
/// use rust_algorithms::other::backtracking::n_queens;
///
/// assert_eq!(n_queens(4).len(), 2);
/// assert_eq!(n_queens(8).len(), 92);
/// assert_eq!(n_queens(1).len(), 1);
/// assert_eq!(n_queens(3).len(), 0); // yechim yo'q
/// ```
pub fn n_queens(n: usize) -> Vec<Vec<usize>> {
    struct Holat {
        ustun: Vec<bool>,
        diag1: Vec<bool>, // qator + ustun
        diag2: Vec<bool>, // qator - ustun + n - 1
        joylashuv: Vec<usize>,
        yechimlar: Vec<Vec<usize>>,
    }

    fn go(h: &mut Holat, qator: usize, n: usize) {
        if qator == n {
            h.yechimlar.push(h.joylashuv.clone());
            return;
        }
        for ustun in 0..n {
            let d1 = qator + ustun;
            let d2 = qator + n - 1 - ustun;
            if h.ustun[ustun] || h.diag1[d1] || h.diag2[d2] {
                continue; // urilib qoladi — bu shoxni kesamiz
            }
            h.ustun[ustun] = true;
            h.diag1[d1] = true;
            h.diag2[d2] = true;
            h.joylashuv.push(ustun);

            go(h, qator + 1, n);

            h.joylashuv.pop(); // backtrack
            h.ustun[ustun] = false;
            h.diag1[d1] = false;
            h.diag2[d2] = false;
        }
    }

    if n == 0 {
        return Vec::new();
    }
    let mut h = Holat {
        ustun: vec![false; n],
        diag1: vec![false; 2 * n],
        diag2: vec![false; 2 * n],
        joylashuv: Vec::with_capacity(n),
        yechimlar: Vec::new(),
    };
    go(&mut h, 0, n);
    h.yechimlar
}

/// Berilgan summani beradigan barcha qism to'plamlar (subset sum).
///
/// # Misol
/// ```
/// use rust_algorithms::other::backtracking::subset_sum;
///
/// let mut natija = subset_sum(&[2, 3, 5, 7], 10);
/// natija.sort();
/// assert_eq!(natija, vec![vec![2, 3, 5], vec![3, 7]]);
/// ```
pub fn subset_sum(nums: &[i64], target: i64) -> Vec<Vec<i64>> {
    fn go(nums: &[i64], i: usize, qolgan: i64, hozir: &mut Vec<i64>, out: &mut Vec<Vec<i64>>) {
        if qolgan == 0 {
            out.push(hozir.clone());
            return;
        }
        if i == nums.len() || qolgan < 0 {
            return; // kesish (pruning)
        }
        hozir.push(nums[i]);
        go(nums, i + 1, qolgan - nums[i], hozir, out);
        hozir.pop();
        go(nums, i + 1, qolgan, hozir, out);
    }
    let mut out = Vec::new();
    go(nums, 0, target, &mut Vec::new(), &mut out);
    out
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn permutatsiyalar_soni_va_ozgachaligi() {
        for n in 0..=6usize {
            let items: Vec<usize> = (0..n).collect();
            let p = permutations(&items);
            let kutilgan: usize = (1..=n).product::<usize>().max(1);
            assert_eq!(p.len(), kutilgan, "n = {n}");

            let mut nusxa = p.clone();
            nusxa.sort();
            nusxa.dedup();
            assert_eq!(nusxa.len(), p.len(), "takrorlanish bor");
        }
    }

    #[test]
    fn qism_toplamlar() {
        for n in 0..=8usize {
            let items: Vec<usize> = (0..n).collect();
            assert_eq!(subsets(&items).len(), 1 << n);
        }
    }

    #[test]
    fn n_vazir_yechimlari_haqiqiy() {
        for n in 1..=8usize {
            for yechim in n_queens(n) {
                assert_eq!(yechim.len(), n);
                for (q1, &u1) in yechim.iter().enumerate() {
                    for (q2, &u2) in yechim.iter().enumerate().skip(q1 + 1) {
                        assert_ne!(u1, u2, "bir ustunda");
                        let dq = (q2 - q1) as i64;
                        let du = (u2 as i64 - u1 as i64).abs();
                        assert_ne!(dq, du, "diagonalda");
                    }
                }
            }
        }
    }

    #[test]
    fn n_vazir_mashhur_sonlar() {
        let kutilgan = [1, 0, 0, 2, 10, 4, 40, 92]; // n = 1..=8
        for (i, &k) in kutilgan.iter().enumerate() {
            assert_eq!(n_queens(i + 1).len(), k, "n = {}", i + 1);
        }
    }

    #[test]
    fn qism_toplam_summasi() {
        assert!(subset_sum(&[1, 2, 3], 100).is_empty());
        assert_eq!(subset_sum(&[5], 5), vec![vec![5]]);
        let n = subset_sum(&[1, 1, 1], 2);
        assert_eq!(n.len(), 3); // 1+1 ni uch xil tanlash mumkin
    }
}