backtrack 0.3.0

Solve hard constraints easily
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

use crate::problem::{CheckInc, Scope};
use std::fmt::{Debug, Formatter};

#[derive(Debug)]
pub struct BitQueens {
    n: usize,
}

impl BitQueens {
    /// Returns largest solvable size
    pub fn max_n() -> usize {
        std::mem::size_of::<usize>() * 8
    }
    pub fn new(n: usize) -> Self {
        let bit_width = Self::max_n();
        assert!(n <= bit_width, "Only problem sizes up to {} supported (usize width)", bit_width);
        BitQueens { n }
    }
}

#[derive(Copy, Clone)]
struct UBitVec(usize);

impl Debug for UBitVec {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(f, "{:b}", self.0)
    }
}

impl Scope<'_> for BitQueens {
    fn size(&self) -> usize {
        self.n
    }

    fn value(&self, index: usize) -> usize {
        index
    }

    fn len(&self) -> usize {
        self.size()
    }
}

#[derive(Debug, Clone)]
pub struct QueenField {
    straight: UBitVec,
    diagonal_left: UBitVec,
    diagonal_right: UBitVec,
    contended: bool,
}

impl CheckInc for BitQueens {
    type Accumulator = QueenField;

    fn fold_acc(
        &self,
        accu: Option<Self::Accumulator>,
        x: &usize,
        _position: usize,
    ) -> Self::Accumulator {
        let one_hot = 1 << x;

        if let Some(mut accu) = accu {
            let diagonal_left = accu.diagonal_left.0 << 1;
            let diagonal_right = accu.diagonal_right.0 >> 1;
            let all = diagonal_left | diagonal_right | accu.straight.0;

            if (all & one_hot) > 0 {
                accu.contended = true;
                return accu;
            }

            accu.straight.0 |= one_hot;
            accu.diagonal_left.0 = diagonal_left | one_hot;
            accu.diagonal_right.0 = diagonal_right | one_hot;

            accu
        } else {
            QueenField {
                straight: UBitVec(one_hot),
                diagonal_left: UBitVec(one_hot),
                diagonal_right: UBitVec(one_hot),
                contended: false,
            }
        }
    }

    fn accu_sat(&self, accu: &Self::Accumulator, _x: &usize, _position: usize) -> bool {
        !accu.contended
    }
}