permute.rs

use std::collections::Bitv;
use std::num;

fn main() {
let mut solved = Bitv::with_capacity(9999999999u, false);
let mut todo = vec![
    1123456789u,
    2123456789u,
    3123456789u,
    4123456789u,
    5123456789u,
    6123456789u,
    7123456789u,
    8123456789u,
    9123456789u
];

let mut n = 0u;
while !todo.is_empty() {
    let mut todo_next = vec![];
    for t in todo.iter() {
        if solved.get(*t) { continue; }
        let pm = t % num::pow(10u, 9);
        n = n + 1;
        solved.set(*t, true);
        let prev = t - pm;
//        println!("Solving: {} prev {}", pm, prev);
        for i in range(1u, 9) {
            for j in range(i+1, 10) {
                let di = pm % num::pow(10u, i)
                       / num::pow(10u, (i-1));
                let dj = pm % num::pow(10u, j)
                       / num::pow(10u, (j-1));
//            println!("Testing {} (that is {} with {}({})<->{}({}) resolving to {} vs {})", pm_prev, pm, i, di, j, dj, (di+dj)%9, prev%9);
                if (prev % 9) == (di + dj) % 9 {
                    let pm_prev = pm
                        - (di * num::pow(10u, (i-1)))
                        - (dj * num::pow(10u, (j-1)))
                        + (di * num::pow(10u, (j-1)))
                        + (dj * num::pow(10u, (i-1)));
                    let wip_i = di * num::pow(10u, 9) + pm_prev;
                    let wip_j = dj * num::pow(10u, 9) + pm_prev;
                    todo_next.push(wip_i);
                    todo_next.push(wip_j);
                }
            }
        }
    }
    todo = todo_next;
    println!("Solved: {}\nTo solve: {}", n, todo.len());
}
println!("Total bits set to true (should be 3265920 = 9!*9): {}", n);
}