traverses the Cross Teaser state graph to calculate puzzle diameter

crossteaser.rs

#![feature(new_uninit)]

use std::mem::MaybeUninit;

// node is stored as 5 bits * 8.
// for bit, the eight S4 elements are separated into sign and A4.
// the A4 are all stored together as a base 12 number (29 bits), and the 8 signs are stored
// together in a bitfield at the MSB part. this concentrates the "islands" of elements together
// and keeps actual RSS at pretty much the real graph size (~3.5GiB/set) despite the ~16GiB/set
// virtual memory allocated. note that to make the code simpler, node stores the elements in
// *reverse* order to bit.

// this is the maximum bit value, NOT the used RAM
const LENGTH: usize = 2usize.pow(8 + 29);
const LENGTH_BYTES: usize = LENGTH / 8 + 1;
const LENGTH_QUADS: usize = LENGTH_BYTES / 8 + 1;

fn node_to_bit(mut node: usize) -> usize {
    let mut bit = 0;
    let mut signs = 0;
    for _ in 0..8 {
        // read from node
        let element = node % 32;
        node /= 32;
        // write to bit
        bit *= 12;
        bit += element / 2;
        // write to signs
        signs <<= 1;
        signs |= element % 2;
    }
    bit | (signs << 29)
}
fn bit_to_node(mut bit: usize) -> usize {
    let mut node = 0;
    let mut signs = bit >> 29;
    bit &= !((!0) << 29);
    for _ in 0..8 {
        // read from bit / signs
        let element = ((bit % 12) * 2) + (signs & 1);
        bit /= 12;
        signs >>= 1;
        // write to node
        node <<= 5;
        node |= element;
    }
    node
}

// sign combinations we will see
const SIGN_ISLANDS: [u8; 70] = [0, 3, 6, 9, 12, 15, 18, 24, 27, 30, 33, 36, 39, 45, 48, 51, 54, 57, 60, 63, 66, 72, 75, 78, 90, 96, 99, 102, 105, 108, 111, 114, 120, 123, 126, 129, 132, 135, 141, 144, 147, 150, 153, 156, 159, 165, 177, 180, 183, 189, 192, 195, 198, 201, 204, 207, 210, 216, 219, 222, 225, 228, 231, 237, 240, 243, 246, 249, 252, 255];

// this updated representation of S4 as int has the property that the sign of the element is the LSB
const S4_MULT_TABLE: [u8; 24*24] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 1, 0, 5, 4, 3, 2, 7, 6, 11, 10, 9, 8, 19, 18, 21, 20, 23, 22, 13, 12, 15, 14, 17, 16, 2, 3, 4, 5, 0, 1, 12, 13, 16, 17, 14, 15, 18, 19, 22, 23, 20, 21, 6, 7, 8, 9, 10, 11, 3, 2, 1, 0, 5, 4, 13, 12, 15, 14, 17, 16, 7, 6, 9, 8, 11, 10, 19, 18, 23, 22, 21, 20, 4, 5, 0, 1, 2, 3, 18, 19, 20, 21, 22, 23, 6, 7, 10, 11, 8, 9, 12, 13, 16, 17, 14, 15, 5, 4, 3, 2, 1, 0, 19, 18, 23, 22, 21, 20, 13, 12, 17, 16, 15, 14, 7, 6, 11, 10, 9, 8, 6, 7, 10, 11, 8, 9, 0, 1, 4, 5, 2, 3, 20, 21, 18, 19, 22, 23, 14, 15, 12, 13, 16, 17, 7, 6, 9, 8, 11, 10, 1, 0, 3, 2, 5, 4, 15, 14, 13, 12, 17, 16, 21, 20, 19, 18, 23, 22, 8, 9, 6, 7, 10, 11, 14, 15, 12, 13, 16, 17, 0, 1, 2, 3, 4, 5, 20, 21, 22, 23, 18, 19, 9, 8, 11, 10, 7, 6, 15, 14, 17, 16, 13, 12, 21, 20, 23, 22, 19, 18, 1, 0, 3, 2, 5, 4, 10, 11, 8, 9, 6, 7, 20, 21, 22, 23, 18, 19, 14, 15, 16, 17, 12, 13, 0, 1, 4, 5, 2, 3, 11, 10, 7, 6, 9, 8, 21, 20, 19, 18, 23, 22, 1, 0, 5, 4, 3, 2, 15, 14, 17, 16, 13, 12, 12, 13, 14, 15, 16, 17, 2, 3, 0, 1, 4, 5, 8, 9, 6, 7, 10, 11, 22, 23, 18, 19, 20, 21, 13, 12, 17, 16, 15, 14, 3, 2, 5, 4, 1, 0, 23, 22, 19, 18, 21, 20, 9, 8, 7, 6, 11, 10, 14, 15, 16, 17, 12, 13, 8, 9, 10, 11, 6, 7, 22, 23, 20, 21, 18, 19, 2, 3, 0, 1, 4, 5, 15, 14, 13, 12, 17, 16, 9, 8, 7, 6, 11, 10, 3, 2, 1, 0, 5, 4, 23, 22, 21, 20, 19, 18, 16, 17, 12, 13, 14, 15, 22, 23, 18, 19, 20, 21, 2, 3, 4, 5, 0, 1, 8, 9, 10, 11, 6, 7, 17, 16, 15, 14, 13, 12, 23, 22, 21, 20, 19, 18, 9, 8, 11, 10, 7, 6, 3, 2, 5, 4, 1, 0, 18, 19, 22, 23, 20, 21, 4, 5, 2, 3, 0, 1, 16, 17, 12, 13, 14, 15, 10, 11, 6, 7, 8, 9, 19, 18, 21, 20, 23, 22, 5, 4, 1, 0, 3, 2, 11, 10, 7, 6, 9, 8, 17, 16, 13, 12, 15, 14, 20, 21, 18, 19, 22, 23, 10, 11, 6, 7, 8, 9, 4, 5, 0, 1, 2, 3, 16, 17, 14, 15, 12, 13, 21, 20, 23, 22, 19, 18, 11, 10, 9, 8, 7, 6, 17, 16, 15, 14, 13, 12, 5, 4, 1, 0, 3, 2, 22, 23, 20, 21, 18, 19, 16, 17, 14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 0, 1, 23, 22, 19, 18, 21, 20, 17, 16, 13, 12, 15, 14, 5, 4, 3, 2, 1, 0, 11, 10, 9, 8, 7, 6];
// a*b in mathematical order, i.e. b applied first, then a
fn mult(a: u8, b: u8) -> u8 {
    let index = (a as usize) * 24 + (b as usize);
    * unsafe { S4_MULT_TABLE.get_unchecked(index) }
}

static mut SEEN_SET: MaybeUninit<&mut [u8; LENGTH_BYTES]> = MaybeUninit::uninit();
static mut PENDING_SET: MaybeUninit<&mut [u64; LENGTH_QUADS]> = MaybeUninit::uninit();
static mut QUEUED_SET: MaybeUninit<&mut [u64; LENGTH_QUADS]> = MaybeUninit::uninit();
static mut COUNT: usize = 0;

fn visit(bit: usize) {
    let slot = unsafe { SEEN_SET.assume_init_read().get_unchecked_mut(bit / 8) };
    let mask = 1u8 << (bit % 8);
    if ((*slot) & mask) != 0 { return }
    *slot |= mask;
    // queue it
    let slot = unsafe { QUEUED_SET.assume_init_read().get_unchecked_mut(bit / 64) };
    let mask = 1u64 << (bit % 64);
    *slot |= mask;
}

type Element = [(u8, u8); 3]; // a cycle of crosses, each tuple is (cross number, rotation applied before permuting)
const NEIGHBORS: [Element; 8] =
[[(0, 11), (1, 20), (7, 23)],
 [(0, 17), (7, 14), (1, 13)],
 [(5, 13), (6, 23), (7, 18)],
 [(5, 10), (7, 17), (6, 11)],
 [(3, 17), (4, 13), (5, 12)],
 [(3, 8), (5, 11), (4, 23)],
 [(1, 11), (2, 17), (3, 4)],
 [(1, 2), (3, 23), (2, 13)]]
;

fn process_pending(root: usize) {
    unsafe { COUNT += 1 };
    for el in NEIGHBORS {
        let mut root = root;
        fn swap_slot(root: &mut usize, cross: (u8, u8), value: u8) -> u8 {
            let bit = cross.0 * 5;
            let element = ((*root >> bit) & 0b11111usize) as u8;
            *root &= !(0b11111usize << bit);
            *root |= (value as usize) << bit;
            mult(cross.1, element)
        }
        // do the cycle
        let mut previous = swap_slot(&mut root, el[0], 0);
        for cross in &el[1..] {
            previous = swap_slot(&mut root, *cross, previous);
        }
        root |= (previous as usize) << (el[0].0 * 5);
        // visit
        visit(node_to_bit(root));
    }
}

fn bfs_pass_island(island: u8) {
    let words_per_island = 12usize.pow(8) / 64 + 1;
    let start = ((island as usize) << 29) / 64;
    for index in start..(start + words_per_island) {
        let word = unsafe { PENDING_SET.assume_init_read().get_unchecked_mut(index) };
        if *word == 0 { continue }
        for i in 0..64 {
            if ((*word) & (1 << i)) == 0 { continue }
            let node = bit_to_node((index * 64) | i);
            process_pending(node);
        }
        *word = 0;
    }
}

unsafe fn allocate_zeroed<T>(bucket: &mut MaybeUninit<&mut T>) {
    let b = Box::new_zeroed();
    let b = unsafe { b.assume_init() };
    bucket.write(Box::leak(b));
}

fn main() {
    unsafe { allocate_zeroed(&mut SEEN_SET) };
    unsafe { allocate_zeroed(&mut QUEUED_SET) };
    unsafe { allocate_zeroed(&mut PENDING_SET) };

    // queue roots
    let start = std::time::Instant::now();
    for orient in 0..24 {
        let mut root = 0;
        for _ in 0..8 {
            root <<= 5;
            root |= orient;
        }
        visit(node_to_bit(root));
    }

    // start BFS (with a reasonable depth limit just in case)
    for depth in 0..35 {
        let count_before_pass = unsafe { COUNT };

        // swap queue sets before starting a BFS pass
        unsafe { std::mem::swap(&mut PENDING_SET, &mut QUEUED_SET) };

        for (idx, &island) in SIGN_ISLANDS.iter().enumerate() {
            bfs_pass_island(island);

            // print current progress
            let now = start.elapsed().as_secs_f32();
            let count = unsafe { COUNT };
            println!("depth {depth:2}, island {idx:2}, count {count:11}, time {now:.2}");
        }

        if unsafe { COUNT } == count_before_pass { break }
    }
}

results.md

what's this

it visits every possible state of the Cross Teaser that is reachable through legal moves, and does so through a BFS in order to prove the "diameter" (the smallest number of moves that allows solving the puzzle. note that:

• only states where the middle spot is empty are considered.
• only states reachable through legal moves starting from the solved state (where crosses are all equally oriented) are considered.
• a "move" is a combination of 4 cross moves, i.e. cycling 3 crosses (clockwise or counterclockwise).
• "solving" means the "stricter" notion, in which you need to get the 8 crosses to be equally oriented (but you're still free to choose what that common orientation is).

more info: https://tech.lgbt/@mildsunrise/111027029987010552

results

12 moves only solves 60% of the states.
13 moves solves 97%.
14 moves solves 99.99%.
15 moves solves 99.9999983%.

the diameter of the puzzle is 16 moves.

depth 16 states

only 504 states require 16 moves (or more) to solve. because of cross rotational symmetry (there is no "base" orientation for the crosses) these reduce into 21 groups, reproduced below:

0123 1320 0231 1023 0321 3102 1023 3201
0123 2310 0321 1203 2031 0132 2013 3021
0123 3210 0231 1023 3201 1032 0213 3201
0123 2310 0231 2013 0321 0132 1023 0231
0123 2310 0231 1203 2031 0312 2103 3201
0123 1320 3201 2103 2031 3012 1203 0231
0123 2310 0132 1320 2103 0132 2013 3102
0123 2013 0312 1230 2031 0321 2310 3102
0123 2310 0321 1203 2031 0312 2013 3201
0123 2310 0213 1032 2310 0132 2013 3210
0123 2310 0231 1023 2031 0312 2103 3021
0123 2130 0321 1203 2031 0132 2013 3201
0123 2130 0321 1023 2031 0312 2013 3201
0123 2310 0231 0123 3201 0132 0213 2301
0123 2310 0231 1203 2031 0132 2103 3021
0123 2310 2031 1023 0321 3102 1203 0231
0123 2130 0231 1203 2301 0312 2013 3021
0123 2301 0213 1023 2310 0123 2013 3201
0123 2013 0132 1023 2103 0231 2013 3201
0123 2130 0231 1023 2031 0312 2103 3201
0123 2013 0312 1320 2103 0132 2031 3201

each line is a state, and lists the rotations of each of the crosses, in the following order:

each rotation is given as a 4-element permutation, where 0123 is the identity. because each element represents a group of states, they've all been normalized so that cross 0 is always the identity.

output

Full output

depth  0, island  0, count          12, time 0.03
depth  0, island  1, count          12, time 0.04
depth  0, island  2, count          12, time 0.05
depth  0, island  3, count          12, time 0.05
depth  0, island  4, count          12, time 0.06
depth  0, island  5, count          12, time 0.06
depth  0, island  6, count          12, time 0.07
depth  0, island  7, count          12, time 0.07
depth  0, island  8, count          12, time 0.08
depth  0, island  9, count          12, time 0.09
depth  0, island 10, count          12, time 0.09
depth  0, island 11, count          12, time 0.10
depth  0, island 12, count          12, time 0.10
depth  0, island 13, count          12, time 0.11
depth  0, island 14, count          12, time 0.12
depth  0, island 15, count          12, time 0.12
depth  0, island 16, count          12, time 0.13
depth  0, island 17, count          12, time 0.13
depth  0, island 18, count          12, time 0.14
depth  0, island 19, count          12, time 0.15
depth  0, island 20, count          12, time 0.15
depth  0, island 21, count          12, time 0.16
depth  0, island 22, count          12, time 0.17
depth  0, island 23, count          12, time 0.17
depth  0, island 24, count          12, time 0.18
depth  0, island 25, count          12, time 0.19
depth  0, island 26, count          12, time 0.20
depth  0, island 27, count          12, time 0.20
depth  0, island 28, count          12, time 0.21
depth  0, island 29, count          12, time 0.21
depth  0, island 30, count          12, time 0.22
depth  0, island 31, count          12, time 0.23
depth  0, island 32, count          12, time 0.23
depth  0, island 33, count          12, time 0.24
depth  0, island 34, count          12, time 0.25
depth  0, island 35, count          12, time 0.25
depth  0, island 36, count          12, time 0.26
depth  0, island 37, count          12, time 0.27
depth  0, island 38, count          12, time 0.27
depth  0, island 39, count          12, time 0.28
depth  0, island 40, count          12, time 0.29
depth  0, island 41, count          12, time 0.29
depth  0, island 42, count          12, time 0.30
depth  0, island 43, count          12, time 0.30
depth  0, island 44, count          12, time 0.31
depth  0, island 45, count          12, time 0.32
depth  0, island 46, count          12, time 0.32
depth  0, island 47, count          12, time 0.33
depth  0, island 48, count          12, time 0.34
depth  0, island 49, count          12, time 0.34
depth  0, island 50, count          12, time 0.35
depth  0, island 51, count          12, time 0.36
depth  0, island 52, count          12, time 0.36
depth  0, island 53, count          12, time 0.37
depth  0, island 54, count          12, time 0.38
depth  0, island 55, count          12, time 0.38
depth  0, island 56, count          12, time 0.39
depth  0, island 57, count          12, time 0.40
depth  0, island 58, count          12, time 0.40
depth  0, island 59, count          12, time 0.41
depth  0, island 60, count          12, time 0.42
depth  0, island 61, count          12, time 0.42
depth  0, island 62, count          12, time 0.43
depth  0, island 63, count          12, time 0.44
depth  0, island 64, count          12, time 0.44
depth  0, island 65, count          12, time 0.45
depth  0, island 66, count          12, time 0.46
depth  0, island 67, count          12, time 0.46
depth  0, island 68, count          12, time 0.47
depth  0, island 69, count          24, time 0.51
depth  1, island  0, count          24, time 0.52
depth  1, island  1, count          36, time 0.54
depth  1, island  2, count          48, time 0.55
depth  1, island  3, count          48, time 0.56
depth  1, island  4, count          60, time 0.58
depth  1, island  5, count          60, time 0.59
depth  1, island  6, count          60, time 0.60
depth  1, island  7, count          72, time 0.61
depth  1, island  8, count          72, time 0.62
depth  1, island  9, count          72, time 0.64
depth  1, island 10, count          72, time 0.65
depth  1, island 11, count          72, time 0.65
depth  1, island 12, count          72, time 0.66
depth  1, island 13, count          72, time 0.67
depth  1, island 14, count          84, time 0.68
depth  1, island 15, count          84, time 0.68
depth  1, island 16, count          84, time 0.69
depth  1, island 17, count          84, time 0.70
depth  1, island 18, count          84, time 0.71
depth  1, island 19, count          96, time 0.72
depth  1, island 20, count          96, time 0.72
depth  1, island 21, count          96, time 0.73
depth  1, island 22, count          96, time 0.74
depth  1, island 23, count          96, time 0.75
depth  1, island 24, count          96, time 0.76
depth  1, island 25, count         108, time 0.77
depth  1, island 26, count         108, time 0.77
depth  1, island 27, count         108, time 0.78
depth  1, island 28, count         108, time 0.79
depth  1, island 29, count         108, time 0.79
depth  1, island 30, count         108, time 0.80
depth  1, island 31, count         108, time 0.81
depth  1, island 32, count         108, time 0.82
depth  1, island 33, count         108, time 0.82
depth  1, island 34, count         120, time 0.83
depth  1, island 35, count         132, time 0.84
depth  1, island 36, count         132, time 0.85
depth  1, island 37, count         132, time 0.85
depth  1, island 38, count         132, time 0.86
depth  1, island 39, count         132, time 0.87
depth  1, island 40, count         132, time 0.87
depth  1, island 41, count         132, time 0.88
depth  1, island 42, count         132, time 0.89
depth  1, island 43, count         132, time 0.89
depth  1, island 44, count         144, time 0.90
depth  1, island 45, count         144, time 0.91
depth  1, island 46, count         144, time 0.91
depth  1, island 47, count         144, time 0.92
depth  1, island 48, count         144, time 0.93
depth  1, island 49, count         144, time 0.93
depth  1, island 50, count         156, time 0.94
depth  1, island 51, count         156, time 0.95
depth  1, island 52, count         156, time 0.95
depth  1, island 53, count         156, time 0.96
depth  1, island 54, count         156, time 0.97
depth  1, island 55, count         168, time 0.97
depth  1, island 56, count         168, time 0.98
depth  1, island 57, count         168, time 0.99
depth  1, island 58, count         168, time 0.99
depth  1, island 59, count         168, time 1.00
depth  1, island 60, count         168, time 1.01
depth  1, island 61, count         168, time 1.01
depth  1, island 62, count         180, time 1.02
depth  1, island 63, count         180, time 1.03
depth  1, island 64, count         180, time 1.03
depth  1, island 65, count         192, time 1.04
depth  1, island 66, count         192, time 1.05
depth  1, island 67, count         204, time 1.05
depth  1, island 68, count         216, time 1.06
depth  1, island 69, count         216, time 1.07
depth  2, island  0, count         216, time 1.08
depth  2, island  1, count         228, time 1.08
depth  2, island  2, count         240, time 1.09
depth  2, island  3, count         252, time 1.10
depth  2, island  4, count         264, time 1.10
depth  2, island  5, count         312, time 1.11
depth  2, island  6, count         324, time 1.12
depth  2, island  7, count         336, time 1.13
depth  2, island  8, count         360, time 1.13
depth  2, island  9, count         408, time 1.14
depth  2, island 10, count         420, time 1.15
depth  2, island 11, count         432, time 1.15
depth  2, island 12, count         444, time 1.16
depth  2, island 13, count         444, time 1.17
depth  2, island 14, count         456, time 1.17
depth  2, island 15, count         480, time 1.18
depth  2, island 16, count         492, time 1.19
depth  2, island 17, count         516, time 1.20
depth  2, island 18, count         564, time 1.20
depth  2, island 19, count         576, time 1.21
depth  2, island 20, count         588, time 1.22
depth  2, island 21, count         600, time 1.22
depth  2, island 22, count         600, time 1.23
depth  2, island 23, count         624, time 1.24
depth  2, island 24, count         624, time 1.24
depth  2, island 25, count         636, time 1.25
depth  2, island 26, count         648, time 1.26
depth  2, island 27, count         672, time 1.26
depth  2, island 28, count         672, time 1.27
depth  2, island 29, count         696, time 1.28
depth  2, island 30, count         708, time 1.28
depth  2, island 31, count         720, time 1.29
depth  2, island 32, count         768, time 1.30
depth  2, island 33, count         780, time 1.30
depth  2, island 34, count         792, time 1.31
depth  2, island 35, count         804, time 1.32
depth  2, island 36, count         816, time 1.33
depth  2, island 37, count         864, time 1.33
depth  2, island 38, count         876, time 1.34
depth  2, island 39, count         888, time 1.35
depth  2, island 40, count         912, time 1.36
depth  2, island 41, count         912, time 1.36
depth  2, island 42, count         936, time 1.37
depth  2, island 43, count         948, time 1.38
depth  2, island 44, count         960, time 1.38
depth  2, island 45, count         960, time 1.39
depth  2, island 46, count         984, time 1.40
depth  2, island 47, count         984, time 1.40
depth  2, island 48, count         996, time 1.41
depth  2, island 49, count        1008, time 1.42
depth  2, island 50, count        1020, time 1.42
depth  2, island 51, count        1068, time 1.43
depth  2, island 52, count        1092, time 1.44
depth  2, island 53, count        1104, time 1.44
depth  2, island 54, count        1128, time 1.45
depth  2, island 55, count        1140, time 1.46
depth  2, island 56, count        1140, time 1.46
depth  2, island 57, count        1152, time 1.47
depth  2, island 58, count        1164, time 1.47
depth  2, island 59, count        1176, time 1.48
depth  2, island 60, count        1224, time 1.49
depth  2, island 61, count        1248, time 1.49
depth  2, island 62, count        1260, time 1.50
depth  2, island 63, count        1272, time 1.51
depth  2, island 64, count        1320, time 1.51
depth  2, island 65, count        1332, time 1.52
depth  2, island 66, count        1344, time 1.53
depth  2, island 67, count        1356, time 1.53
depth  2, island 68, count        1368, time 1.54
depth  2, island 69, count        1368, time 1.55
depth  3, island  0, count        1464, time 1.55
depth  3, island  1, count        1548, time 1.56
depth  3, island  2, count        1632, time 1.57
depth  3, island  3, count        1752, time 1.58
depth  3, island  4, count        1836, time 1.59
depth  3, island  5, count        1956, time 1.60
depth  3, island  6, count        2076, time 1.60
depth  3, island  7, count        2160, time 1.61
depth  3, island  8, count        2280, time 1.62
depth  3, island  9, count        2400, time 1.63
depth  3, island 10, count        2520, time 1.64
depth  3, island 11, count        2640, time 1.65
depth  3, island 12, count        2736, time 1.65
depth  3, island 13, count        2784, time 1.66
depth  3, island 14, count        2868, time 1.67
depth  3, island 15, count        2916, time 1.68
depth  3, island 16, count        3012, time 1.68
depth  3, island 17, count        3132, time 1.69
depth  3, island 18, count        3252, time 1.70
depth  3, island 19, count        3336, time 1.71
depth  3, island 20, count        3456, time 1.72
depth  3, island 21, count        3576, time 1.73
depth  3, island 22, count        3624, time 1.74
depth  3, island 23, count        3744, time 1.75
depth  3, island 24, count        3792, time 1.75
depth  3, island 25, count        3876, time 1.76
depth  3, island 26, count        3972, time 1.77
depth  3, island 27, count        4020, time 1.78
depth  3, island 28, count        4068, time 1.79
depth  3, island 29, count        4188, time 1.80
depth  3, island 30, count        4308, time 1.81
depth  3, island 31, count        4404, time 1.82
depth  3, island 32, count        4524, time 1.83
depth  3, island 33, count        4644, time 1.83
depth  3, island 34, count        4728, time 1.84
depth  3, island 35, count        4812, time 1.85
depth  3, island 36, count        4932, time 1.86
depth  3, island 37, count        5052, time 1.87
depth  3, island 38, count        5148, time 1.88
depth  3, island 39, count        5268, time 1.88
depth  3, island 40, count        5388, time 1.89
depth  3, island 41, count        5436, time 1.90
depth  3, island 42, count        5484, time 1.91
depth  3, island 43, count        5580, time 1.92
depth  3, island 44, count        5664, time 1.93
depth  3, island 45, count        5712, time 1.93
depth  3, island 46, count        5832, time 1.94
depth  3, island 47, count        5880, time 1.95
depth  3, island 48, count        6000, time 1.96
depth  3, island 49, count        6120, time 1.97
depth  3, island 50, count        6204, time 1.98
depth  3, island 51, count        6324, time 1.99
depth  3, island 52, count        6444, time 1.99
depth  3, island 53, count        6540, time 2.00
depth  3, island 54, count        6588, time 2.01
depth  3, island 55, count        6672, time 2.02
depth  3, island 56, count        6720, time 2.02
depth  3, island 57, count        6816, time 2.03
depth  3, island 58, count        6936, time 2.04
depth  3, island 59, count        7056, time 2.05
depth  3, island 60, count        7176, time 2.06
depth  3, island 61, count        7296, time 2.06
depth  3, island 62, count        7380, time 2.07
depth  3, island 63, count        7500, time 2.08
depth  3, island 64, count        7620, time 2.09
depth  3, island 65, count        7704, time 2.09
depth  3, island 66, count        7824, time 2.10
depth  3, island 67, count        7908, time 2.11
depth  3, island 68, count        7992, time 2.12
depth  3, island 69, count        8088, time 2.13
depth  4, island  0, count        8712, time 2.14
depth  4, island  1, count        9348, time 2.17
depth  4, island  2, count        9984, time 2.19
depth  4, island  3, count       10608, time 2.20
depth  4, island  4, count       11244, time 2.22
depth  4, island  5, count       11652, time 2.23
depth  4, island  6, count       12276, time 2.24
depth  4, island  7, count       12912, time 2.26
depth  4, island  8, count       13320, time 2.27
depth  4, island  9, count       13728, time 2.28
depth  4, island 10, count       14352, time 2.29
depth  4, island 11, count       14976, time 2.31
depth  4, island 12, count       15516, time 2.32
depth  4, island 13, count       16044, time 2.33
depth  4, island 14, count       16680, time 2.35
depth  4, island 15, count       17160, time 2.36
depth  4, island 16, count       17700, time 2.37
depth  4, island 17, count       18108, time 2.38
depth  4, island 18, count       18516, time 2.39
depth  4, island 19, count       19152, time 2.40
depth  4, island 20, count       19776, time 2.41
depth  4, island 21, count       20400, time 2.43
depth  4, island 22, count       20928, time 2.44
depth  4, island 23, count       21336, time 2.45
depth  4, island 24, count       21864, time 2.46
depth  4, island 25, count       22500, time 2.47
depth  4, island 26, count       23040, time 2.48
depth  4, island 27, count       23520, time 2.49
depth  4, island 28, count       24048, time 2.50
depth  4, island 29, count       24456, time 2.51
depth  4, island 30, count       25080, time 2.52
depth  4, island 31, count       25620, time 2.53
depth  4, island 32, count       26028, time 2.54
depth  4, island 33, count       26652, time 2.55
depth  4, island 34, count       27288, time 2.57
depth  4, island 35, count       27924, time 2.58
depth  4, island 36, count       28548, time 2.59
depth  4, island 37, count       28956, time 2.60
depth  4, island 38, count       29496, time 2.61
depth  4, island 39, count       30120, time 2.63
depth  4, island 40, count       30528, time 2.64
depth  4, island 41, count       31056, time 2.65
depth  4, island 42, count       31536, time 2.66
depth  4, island 43, count       32076, time 2.67
depth  4, island 44, count       32712, time 2.69
depth  4, island 45, count       33240, time 2.70
depth  4, island 46, count       33648, time 2.71
depth  4, island 47, count       34176, time 2.72
depth  4, island 48, count       34800, time 2.73
depth  4, island 49, count       35424, time 2.74
depth  4, island 50, count       36060, time 2.75
depth  4, island 51, count       36468, time 2.76
depth  4, island 52, count       36876, time 2.77
depth  4, island 53, count       37416, time 2.79
depth  4, island 54, count       37896, time 2.80
depth  4, island 55, count       38532, time 2.81
depth  4, island 56, count       39060, time 2.82
depth  4, island 57, count       39600, time 2.83
depth  4, island 58, count       40224, time 2.84
depth  4, island 59, count       40848, time 2.85
depth  4, island 60, count       41256, time 2.86
depth  4, island 61, count       41664, time 2.87
depth  4, island 62, count       42300, time 2.88
depth  4, island 63, count       42924, time 2.89
depth  4, island 64, count       43332, time 2.90
depth  4, island 65, count       43968, time 2.91
depth  4, island 66, count       44592, time 2.92
depth  4, island 67, count       45228, time 2.93
depth  4, island 68, count       45864, time 2.94
depth  4, island 69, count       46488, time 2.96
depth  5, island  0, count       50520, time 3.03
depth  5, island  1, count       53508, time 3.10
depth  5, island  2, count       56496, time 3.14
depth  5, island  3, count       59376, time 3.17
depth  5, island  4, count       62364, time 3.20
depth  5, island  5, count       65460, time 3.24
depth  5, island  6, count       68340, time 3.26
depth  5, island  7, count       71328, time 3.30
depth  5, island  8, count       74088, time 3.34
depth  5, island  9, count       77184, time 3.38
depth  5, island 10, count       80064, time 3.42
depth  5, island 11, count       82944, time 3.45
depth  5, island 12, count       86088, time 3.47
depth  5, island 13, count       89376, time 3.50
depth  5, island 14, count       92364, time 3.53
depth  5, island 15, count       96060, time 3.56
depth  5, island 16, count       99204, time 3.59
depth  5, island 17, count      101964, time 3.61
depth  5, island 18, count      105060, time 3.64
depth  5, island 19, count      108048, time 3.67
depth  5, island 20, count      110928, time 3.69
depth  5, island 21, count      113808, time 3.71
depth  5, island 22, count      117096, time 3.73
depth  5, island 23, count      119856, time 3.75
depth  5, island 24, count      123144, time 3.77
depth  5, island 25, count      126132, time 3.80
depth  5, island 26, count      129276, time 3.82
depth  5, island 27, count      132972, time 3.84
depth  5, island 28, count      136260, time 3.86
depth  5, island 29, count      139020, time 3.88
depth  5, island 30, count      141900, time 3.90
depth  5, island 31, count      145044, time 3.92
depth  5, island 32, count      148140, time 3.94
depth  5, island 33, count      151020, time 3.96
depth  5, island 34, count      154008, time 3.98
depth  5, island 35, count      156996, time 4.00
depth  5, island 36, count      159876, time 4.03
depth  5, island 37, count      162972, time 4.06
depth  5, island 38, count      166116, time 4.09
depth  5, island 39, count      168996, time 4.12
depth  5, island 40, count      171756, time 4.14
depth  5, island 41, count      175044, time 4.17
depth  5, island 42, count      178740, time 4.20
depth  5, island 43, count      181884, time 4.23
depth  5, island 44, count      184872, time 4.26
depth  5, island 45, count      188160, time 4.28
depth  5, island 46, count      190920, time 4.30
depth  5, island 47, count      194208, time 4.32
depth  5, island 48, count      197088, time 4.34
depth  5, island 49, count      199968, time 4.36
depth  5, island 50, count      202956, time 4.38
depth  5, island 51, count      206052, time 4.40
depth  5, island 52, count      208812, time 4.42
depth  5, island 53, count      211956, time 4.44
depth  5, island 54, count      215652, time 4.46
depth  5, island 55, count      218640, time 4.48
depth  5, island 56, count      221928, time 4.50
depth  5, island 57, count      225072, time 4.51
depth  5, island 58, count      227952, time 4.53
depth  5, island 59, count      230832, time 4.55
depth  5, island 60, count      233928, time 4.56
depth  5, island 61, count      236688, time 4.58
depth  5, island 62, count      239676, time 4.59
depth  5, island 63, count      242556, time 4.61
depth  5, island 64, count      245652, time 4.63
depth  5, island 65, count      248640, time 4.64
depth  5, island 66, count      251520, time 4.66
depth  5, island 67, count      254508, time 4.67
depth  5, island 68, count      257496, time 4.69
depth  5, island 69, count      261528, time 4.70
depth  6, island  0, count      278016, time 4.77
depth  6, island  1, count      295416, time 4.85
depth  6, island  2, count      312816, time 4.93
depth  6, island  3, count      328884, time 5.00
depth  6, island  4, count      346284, time 5.07
depth  6, island  5, count      362964, time 5.12
depth  6, island  6, count      379032, time 5.18
depth  6, island  7, count      396432, time 5.23
depth  6, island  8, count      414000, time 5.30
depth  6, island  9, count      430680, time 5.38
depth  6, island 10, count      446748, time 5.48
depth  6, island 11, count      462816, time 5.53
depth  6, island 12, count      480096, time 5.57
depth  6, island 13, count      497352, time 5.61
depth  6, island 14, count      514752, time 5.66
depth  6, island 15, count      531600, time 5.70
depth  6, island 16, count      548880, time 5.74
depth  6, island 17, count      566448, time 5.77
depth  6, island 18, count      583128, time 5.81
depth  6, island 19, count      600528, time 5.85
depth  6, island 20, count      616596, time 5.88
depth  6, island 21, count      632664, time 5.91
depth  6, island 22, count      649920, time 5.95
depth  6, island 23, count      667488, time 5.98
depth  6, island 24, count      684744, time 6.01
depth  6, island 25, count      702144, time 6.04
depth  6, island 26, count      719424, time 6.07
depth  6, island 27, count      736272, time 6.10
depth  6, island 28, count      753528, time 6.12
depth  6, island 29, count      771096, time 6.15
depth  6, island 30, count      787164, time 6.17
depth  6, island 31, count      804444, time 6.20
depth  6, island 32, count      821124, time 6.23
depth  6, island 33, count      837192, time 6.25
depth  6, island 34, count      854592, time 6.28
depth  6, island 35, count      871992, time 6.33
depth  6, island 36, count      888060, time 6.38
depth  6, island 37, count      904740, time 6.42
depth  6, island 38, count      922020, time 6.45
depth  6, island 39, count      938088, time 6.49
depth  6, island 40, count      955656, time 6.53
depth  6, island 41, count      972912, time 6.56
depth  6, island 42, count      989760, time 6.59
depth  6, island 43, count     1007040, time 6.62
depth  6, island 44, count     1024440, time 6.65
depth  6, island 45, count     1041696, time 6.69
depth  6, island 46, count     1059264, time 6.74
depth  6, island 47, count     1076520, time 6.79
depth  6, island 48, count     1092588, time 6.83
depth  6, island 49, count     1108656, time 6.87
depth  6, island 50, count     1126056, time 6.91
depth  6, island 51, count     1142736, time 6.95
depth  6, island 52, count     1160304, time 6.99
depth  6, island 53, count     1177584, time 7.03
depth  6, island 54, count     1194432, time 7.07
depth  6, island 55, count     1211832, time 7.10
depth  6, island 56, count     1229088, time 7.14
depth  6, island 57, count     1246368, time 7.18
depth  6, island 58, count     1262436, time 7.23
depth  6, island 59, count     1278504, time 7.26
depth  6, island 60, count     1295184, time 7.30
depth  6, island 61, count     1312752, time 7.35
depth  6, island 62, count     1330152, time 7.40
depth  6, island 63, count     1346220, time 7.45
depth  6, island 64, count     1362900, time 7.49
depth  6, island 65, count     1380300, time 7.52
depth  6, island 66, count     1396368, time 7.54
depth  6, island 67, count     1413768, time 7.56
depth  6, island 68, count     1431168, time 7.59
depth  6, island 69, count     1447656, time 7.62
depth  7, island  0, count     1535928, time 7.74
depth  7, island  1, count     1628244, time 7.88
depth  7, island  2, count     1720560, time 8.00
depth  7, island  3, count     1813524, time 8.10
depth  7, island  4, count     1905840, time 8.20
depth  7, island  5, count     1999896, time 8.36
depth  7, island  6, count     2092860, time 8.51
depth  7, island  7, count     2185176, time 8.66
depth  7, island  8, count     2278968, time 8.79
depth  7, island  9, count     2373024, time 8.89
depth  7, island 10, count     2465988, time 9.01
depth  7, island 11, count     2558952, time 9.11
depth  7, island 12, count     2650752, time 9.20
depth  7, island 13, count     2742264, time 9.28
depth  7, island 14, count     2834580, time 9.37
depth  7, island 15, count     2924052, time 9.46
depth  7, island 16, count     3015852, time 9.55
depth  7, island 17, count     3109644, time 9.64
depth  7, island 18, count     3203700, time 9.74
depth  7, island 19, count     3296016, time 9.83
depth  7, island 20, count     3388980, time 9.90
depth  7, island 21, count     3481944, time 9.98
depth  7, island 22, count     3573456, time 10.06
depth  7, island 23, count     3667248, time 10.14
depth  7, island 24, count     3758760, time 10.22
depth  7, island 25, count     3851076, time 10.30
depth  7, island 26, count     3942876, time 10.38
depth  7, island 27, count     4032348, time 10.46
depth  7, island 28, count     4123860, time 10.54
depth  7, island 29, count     4217652, time 10.62
depth  7, island 30, count     4310616, time 10.70
depth  7, island 31, count     4402416, time 10.78
depth  7, island 32, count     4496472, time 10.86
depth  7, island 33, count     4589436, time 10.94
depth  7, island 34, count     4681752, time 11.02
depth  7, island 35, count     4774068, time 11.11
depth  7, island 36, count     4867032, time 11.22
depth  7, island 37, count     4961088, time 11.30
depth  7, island 38, count     5052888, time 11.38
depth  7, island 39, count     5145852, time 11.46
depth  7, island 40, count     5239644, time 11.55
depth  7, island 41, count     5331156, time 11.62
depth  7, island 42, count     5420628, time 11.70
depth  7, island 43, count     5512428, time 11.79
depth  7, island 44, count     5604744, time 11.87
depth  7, island 45, count     5696256, time 11.94
depth  7, island 46, count     5790048, time 12.03
depth  7, island 47, count     5881560, time 12.10
depth  7, island 48, count     5974524, time 12.18
depth  7, island 49, count     6067488, time 12.26
depth  7, island 50, count     6159804, time 12.34
depth  7, island 51, count     6253860, time 12.42
depth  7, island 52, count     6347652, time 12.50
depth  7, island 53, count     6439452, time 12.58
depth  7, island 54, count     6528924, time 12.66
depth  7, island 55, count     6621240, time 12.75
depth  7, island 56, count     6712752, time 12.82
depth  7, island 57, count     6804552, time 12.89
depth  7, island 58, count     6897516, time 12.97
depth  7, island 59, count     6990480, time 13.04
depth  7, island 60, count     7084536, time 13.12
depth  7, island 61, count     7178328, time 13.19
depth  7, island 62, count     7270644, time 13.27
depth  7, island 63, count     7363608, time 13.34
depth  7, island 64, count     7457664, time 13.42
depth  7, island 65, count     7549980, time 13.50
depth  7, island 66, count     7642944, time 13.58
depth  7, island 67, count     7735260, time 13.65
depth  7, island 68, count     7827576, time 13.73
depth  7, island 69, count     7915848, time 13.81
depth  8, island  0, count     8410332, time 14.07
depth  8, island  1, count     8901372, time 14.32
depth  8, island  2, count     9392412, time 14.58
depth  8, island  3, count     9896736, time 14.83
depth  8, island  4, count    10387776, time 15.10
depth  8, island  5, count    10892472, time 15.36
depth  8, island  6, count    11396796, time 15.61
depth  8, island  7, count    11887836, time 15.88
depth  8, island  8, count    12384672, time 16.15
depth  8, island  9, count    12889368, time 16.42
depth  8, island 10, count    13393692, time 16.70
depth  8, island 11, count    13898016, time 16.97
depth  8, island 12, count    14392248, time 17.24
depth  8, island 13, count    14887704, time 17.49
depth  8, island 14, count    15378744, time 17.79
depth  8, island 15, count    15870264, time 18.06
depth  8, island 16, count    16364496, time 18.34
depth  8, island 17, count    16861332, time 18.61
depth  8, island 18, count    17366028, time 18.90
depth  8, island 19, count    17857068, time 19.18
depth  8, island 20, count    18361392, time 19.45
depth  8, island 21, count    18865716, time 19.73
depth  8, island 22, count    19361172, time 19.98
depth  8, island 23, count    19858008, time 20.26
depth  8, island 24, count    20353464, time 20.52
depth  8, island 25, count    20844504, time 20.81
depth  8, island 26, count    21338736, time 21.10
depth  8, island 27, count    21830256, time 21.39
depth  8, island 28, count    22325712, time 21.66
depth  8, island 29, count    22822548, time 21.96
depth  8, island 30, count    23326872, time 22.26
depth  8, island 31, count    23821104, time 22.54
depth  8, island 32, count    24325800, time 22.85
depth  8, island 33, count    24830124, time 23.15
depth  8, island 34, count    25321164, time 23.44
depth  8, island 35, count    25812204, time 23.73
depth  8, island 36, count    26316528, time 24.00
depth  8, island 37, count    26821224, time 24.29
depth  8, island 38, count    27315456, time 24.56
depth  8, island 39, count    27819780, time 24.84
depth  8, island 40, count    28316616, time 25.13
depth  8, island 41, count    28812072, time 25.39
depth  8, island 42, count    29303592, time 25.68
depth  8, island 43, count    29797824, time 25.97
depth  8, island 44, count    30288864, time 26.26
depth  8, island 45, count    30784320, time 26.53
depth  8, island 46, count    31281156, time 26.82
depth  8, island 47, count    31776612, time 27.08
depth  8, island 48, count    32280936, time 27.35
depth  8, island 49, count    32785260, time 27.63
depth  8, island 50, count    33276300, time 27.92
depth  8, island 51, count    33780996, time 28.22
depth  8, island 52, count    34277832, time 28.52
depth  8, island 53, count    34772064, time 28.81
depth  8, island 54, count    35263584, time 29.10
depth  8, island 55, count    35754624, time 29.42
depth  8, island 56, count    36250080, time 29.71
depth  8, island 57, count    36744312, time 30.01
depth  8, island 58, count    37248636, time 30.30
depth  8, island 59, count    37752960, time 30.61
depth  8, island 60, count    38257656, time 30.91
depth  8, island 61, count    38754492, time 31.21
depth  8, island 62, count    39245532, time 31.51
depth  8, island 63, count    39749856, time 31.80
depth  8, island 64, count    40254552, time 32.11
depth  8, island 65, count    40745592, time 32.41
depth  8, island 66, count    41249916, time 32.70
depth  8, island 67, count    41740956, time 33.00
depth  8, island 68, count    42231996, time 33.30
depth  8, island 69, count    42726480, time 33.60
depth  9, island  0, count    45333768, time 34.57
depth  9, island  1, count    47967456, time 35.50
depth  9, island  2, count    50601144, time 36.44
depth  9, island  3, count    53241456, time 37.31
depth  9, island  4, count    55875144, time 38.25
depth  9, island  5, count    58486032, time 39.15
depth  9, island  6, count    61126344, time 40.07
depth  9, island  7, count    63760032, time 41.01
depth  9, island  8, count    66384288, time 41.93
depth  9, island  9, count    68995176, time 42.87
depth  9, island 10, count    71635488, time 43.79
depth  9, island 11, count    74275800, time 44.74
depth  9, island 12, count    76901196, time 45.73
depth  9, island 13, count    79547352, time 46.66
depth  9, island 14, count    82181040, time 47.64
depth  9, island 15, count    84794400, time 48.60
depth  9, island 16, count    87419796, time 49.51
depth  9, island 17, count    90044052, time 50.49
depth  9, island 18, count    92654940, time 51.44
depth  9, island 19, count    95288628, time 52.40
depth  9, island 20, count    97928940, time 53.38
depth  9, island 21, count   100569252, time 54.33
depth  9, island 22, count   103215408, time 55.24
depth  9, island 23, count   105839664, time 56.26
depth  9, island 24, count   108485820, time 57.24
depth  9, island 25, count   111119508, time 58.29
depth  9, island 26, count   113744904, time 59.27
depth  9, island 27, count   116358264, time 60.31
depth  9, island 28, count   119004420, time 61.26
depth  9, island 29, count   121628676, time 62.29
depth  9, island 30, count   124268988, time 63.30
depth  9, island 31, count   126894384, time 64.44
depth  9, island 32, count   129505272, time 65.45
depth  9, island 33, count   132145584, time 66.57
depth  9, island 34, count   134779272, time 67.79
depth  9, island 35, count   137412960, time 68.78
depth  9, island 36, count   140053272, time 69.81
depth  9, island 37, count   142664160, time 70.78
depth  9, island 38, count   145289556, time 71.73
depth  9, island 39, count   147929868, time 72.69
depth  9, island 40, count   150554124, time 73.69
depth  9, island 41, count   153200280, time 74.61
depth  9, island 42, count   155813640, time 75.61
depth  9, island 43, count   158439036, time 76.62
depth  9, island 44, count   161072724, time 77.62
depth  9, island 45, count   163718880, time 78.59
depth  9, island 46, count   166343136, time 79.61
depth  9, island 47, count   168989292, time 80.51
depth  9, island 48, count   171629604, time 81.48
depth  9, island 49, count   174269916, time 82.46
depth  9, island 50, count   176903604, time 83.52
depth  9, island 51, count   179514492, time 84.55
depth  9, island 52, count   182138748, time 85.60
depth  9, island 53, count   184764144, time 86.59
depth  9, island 54, count   187377504, time 87.63
depth  9, island 55, count   190011192, time 88.70
depth  9, island 56, count   192657348, time 89.71
depth  9, island 57, count   195282744, time 90.76
depth  9, island 58, count   197923056, time 91.80
depth  9, island 59, count   200563368, time 92.86
depth  9, island 60, count   203174256, time 93.91
depth  9, island 61, count   205798512, time 94.96
depth  9, island 62, count   208432200, time 96.02
depth  9, island 63, count   211072512, time 97.02
depth  9, island 64, count   213683400, time 98.07
depth  9, island 65, count   216317088, time 99.12
depth  9, island 66, count   218957400, time 100.11
depth  9, island 67, count   221591088, time 101.17
depth  9, island 68, count   224224776, time 102.21
depth  9, island 69, count   226832064, time 103.26
depth 10, island  0, count   240245568, time 105.86
depth 10, island  1, count   253641612, time 108.43
depth 10, island  2, count   267037656, time 111.01
depth 10, island  3, count   280423608, time 113.49
depth 10, island  4, count   293819652, time 116.10
depth 10, island  5, count   307185024, time 118.71
depth 10, island  6, count   320570976, time 121.23
depth 10, island  7, count   333967020, time 123.88
depth 10, island  8, count   347358852, time 126.53
depth 10, island  9, count   360724224, time 129.22
depth 10, island 10, count   374110176, time 131.89
depth 10, island 11, count   387496128, time 134.62
depth 10, island 12, count   400902852, time 137.38
depth 10, island 13, count   414384252, time 140.03
depth 10, island 14, count   427780296, time 142.74
depth 10, island 15, count   441237528, time 145.42
depth 10, island 16, count   454644252, time 147.99
depth 10, island 17, count   468036084, time 150.73
depth 10, island 18, count   481401456, time 153.44
depth 10, island 19, count   494797500, time 156.21
depth 10, island 20, count   508183452, time 159.03
depth 10, island 21, count   521569404, time 161.75
depth 10, island 22, count   535050804, time 164.39
depth 10, island 23, count   548442636, time 167.31
depth 10, island 24, count   561924036, time 170.14
depth 10, island 25, count   575320080, time 173.09
depth 10, island 26, count   588726804, time 175.83
depth 10, island 27, count   602184036, time 178.78
depth 10, island 28, count   615665436, time 181.45
depth 10, island 29, count   629057268, time 184.40
depth 10, island 30, count   642443220, time 187.32
depth 10, island 31, count   655849944, time 190.18
depth 10, island 32, count   669215316, time 193.15
depth 10, island 33, count   682601268, time 196.16
depth 10, island 34, count   695997312, time 199.13
depth 10, island 35, count   709393356, time 201.99
depth 10, island 36, count   722779308, time 204.59
depth 10, island 37, count   736144680, time 207.51
depth 10, island 38, count   749551404, time 210.31
depth 10, island 39, count   762937356, time 212.99
depth 10, island 40, count   776329188, time 215.86
depth 10, island 41, count   789810588, time 218.50
depth 10, island 42, count   803267820, time 221.41
depth 10, island 43, count   816674544, time 224.30
depth 10, island 44, count   830070588, time 227.22
depth 10, island 45, count   843551988, time 230.02
depth 10, island 46, count   856943820, time 232.95
depth 10, island 47, count   870425220, time 235.60
depth 10, island 48, count   883811172, time 238.38
depth 10, island 49, count   897197124, time 241.25
depth 10, island 50, count   910593168, time 244.34
depth 10, island 51, count   923958540, time 247.43
depth 10, island 52, count   937350372, time 250.51
depth 10, island 53, count   950757096, time 253.42
depth 10, island 54, count   964214328, time 256.50
depth 10, island 55, count   977610372, time 259.62
depth 10, island 56, count   991091772, time 262.59
depth 10, island 57, count  1004498496, time 265.68
depth 10, island 58, count  1017884448, time 268.77
depth 10, island 59, count  1031270400, time 271.86
depth 10, island 60, count  1044635772, time 274.96
depth 10, island 61, count  1058027604, time 278.06
depth 10, island 62, count  1071423648, time 281.16
depth 10, island 63, count  1084809600, time 284.13
depth 10, island 64, count  1098174972, time 287.22
depth 10, island 65, count  1111571016, time 290.30
depth 10, island 66, count  1124956968, time 293.22
depth 10, island 67, count  1138353012, time 296.32
depth 10, island 68, count  1151749056, time 299.41
depth 10, island 69, count  1165162560, time 302.50
depth 11, island  0, count  1226011260, time 311.68
depth 11, island  1, count  1286732088, time 321.07
depth 11, island  2, count  1347452916, time 330.67
depth 11, island  3, count  1408084572, time 340.29
depth 11, island  4, count  1468805400, time 350.13
depth 11, island  5, count  1529641908, time 359.99
depth 11, island  6, count  1590273564, time 369.90
depth 11, island  7, count  1650994392, time 379.89
depth 11, island  8, count  1711774452, time 389.85
depth 11, island  9, count  1772610960, time 399.81
depth 11, island 10, count  1833242616, time 409.67
depth 11, island 11, count  1893874272, time 419.58
depth 11, island 12, count  1954733892, time 429.42
depth 11, island 13, count  2015457096, time 439.29
depth 11, island 14, count  2076177924, time 449.25
depth 11, island 15, count  2137066224, time 459.34
depth 11, island 16, count  2197925844, time 469.13
depth 11, island 17, count  2258705904, time 478.94
depth 11, island 18, count  2319542412, time 488.68
depth 11, island 19, count  2380263240, time 498.48
depth 11, island 20, count  2440894896, time 508.27
depth 11, island 21, count  2501526552, time 518.02
depth 11, island 22, count  2562249756, time 527.65
depth 11, island 23, count  2623029816, time 537.31
depth 11, island 24, count  2683753020, time 546.78
depth 11, island 25, count  2744473848, time 556.32
depth 11, island 26, count  2805333468, time 566.05
depth 11, island 27, count  2866221768, time 575.51
depth 11, island 28, count  2926944972, time 584.81
depth 11, island 29, count  2987725032, time 594.14
depth 11, island 30, count  3048356688, time 603.38
depth 11, island 31, count  3109216308, time 612.69
depth 11, island 32, count  3170052816, time 621.99
depth 11, island 33, count  3230684472, time 630.93
depth 11, island 34, count  3291405300, time 640.15
depth 11, island 35, count  3352126128, time 650.25
depth 11, island 36, count  3412757784, time 660.32
depth 11, island 37, count  3473594292, time 670.51
depth 11, island 38, count  3534453912, time 680.54
depth 11, island 39, count  3595085568, time 690.57
depth 11, island 40, count  3655865628, time 700.70
depth 11, island 41, count  3716588832, time 710.60
depth 11, island 42, count  3777477132, time 720.66
depth 11, island 43, count  3838336752, time 730.37
depth 11, island 44, count  3899057580, time 740.24
depth 11, island 45, count  3959780784, time 750.10
depth 11, island 46, count  4020560844, time 759.97
depth 11, island 47, count  4081284048, time 769.60
depth 11, island 48, count  4141915704, time 779.08
depth 11, island 49, count  4202547360, time 788.58
depth 11, island 50, count  4263268188, time 798.07
depth 11, island 51, count  4324104696, time 807.57
depth 11, island 52, count  4384884756, time 817.13
depth 11, island 53, count  4445744376, time 826.51
depth 11, island 54, count  4506632676, time 835.94
depth 11, island 55, count  4567353504, time 845.31
depth 11, island 56, count  4628076708, time 854.64
depth 11, island 57, count  4688936328, time 864.19
depth 11, island 58, count  4749567984, time 873.36
depth 11, island 59, count  4810199640, time 882.31
depth 11, island 60, count  4871036148, time 891.50
depth 11, island 61, count  4931816208, time 900.62
depth 11, island 62, count  4992537036, time 909.73
depth 11, island 63, count  5053168692, time 918.73
depth 11, island 64, count  5114005200, time 927.84
depth 11, island 65, count  5174726028, time 936.89
depth 11, island 66, count  5235357684, time 945.74
depth 11, island 67, count  5296078512, time 954.70
depth 11, island 68, count  5356799340, time 963.66
depth 11, island 69, count  5417648040, time 972.60
depth 12, island  0, count  5598750984, time 1001.28
depth 12, island  1, count  5780256672, time 1029.62
depth 12, island  2, count  5961762360, time 1057.55
depth 12, island  3, count  6142575564, time 1084.83
depth 12, island  4, count  6324081252, time 1111.16
depth 12, island  5, count  6505418556, time 1137.33
depth 12, island  6, count  6686231760, time 1163.25
depth 12, island  7, count  6867737448, time 1188.68
depth 12, island  8, count  7048666608, time 1214.31
depth 12, island  9, count  7230003912, time 1239.60
depth 12, island 10, count  7410817116, time 1266.79
depth 12, island 11, count  7591630320, time 1292.37
depth 12, island 12, count  7772830692, time 1316.70
depth 12, island 13, count  7952603832, time 1340.57
depth 12, island 14, count  8134109520, time 1365.30
depth 12, island 15, count  8315375760, time 1389.53
depth 12, island 16, count  8496576132, time 1413.65
depth 12, island 17, count  8677505292, time 1437.47
depth 12, island 18, count  8858842596, time 1461.57
depth 12, island 19, count  9040348284, time 1485.36
depth 12, island 20, count  9221161488, time 1508.59
depth 12, island 21, count  9401974692, time 1531.74
depth 12, island 22, count  9581747832, time 1554.23
depth 12, island 23, count  9762676992, time 1576.97
depth 12, island 24, count  9942450132, time 1599.21
depth 12, island 25, count 10123955820, time 1621.86
depth 12, island 26, count 10305156192, time 1644.42
depth 12, island 27, count 10486422432, time 1666.90
depth 12, island 28, count 10666195572, time 1688.87
depth 12, island 29, count 10847124732, time 1711.15
depth 12, island 30, count 11027937936, time 1733.03
depth 12, island 31, count 11209138308, time 1755.25
depth 12, island 32, count 11390475612, time 1777.49
depth 12, island 33, count 11571288816, time 1799.12
depth 12, island 34, count 11752794504, time 1821.33
depth 12, island 35, count 11934300192, time 1846.24
depth 12, island 36, count 12115113396, time 1872.25
depth 12, island 37, count 12296450700, time 1896.29
depth 12, island 38, count 12477651072, time 1919.81
depth 12, island 39, count 12658464276, time 1944.32
depth 12, island 40, count 12839393436, time 1967.97
depth 12, island 41, count 13019166576, time 1990.77
depth 12, island 42, count 13200432816, time 2013.97
depth 12, island 43, count 13381633188, time 2036.78
depth 12, island 44, count 13563138876, time 2059.71
depth 12, island 45, count 13742912016, time 2082.67
depth 12, island 46, count 13923841176, time 2105.54
depth 12, island 47, count 14103614316, time 2127.84
depth 12, island 48, count 14284427520, time 2150.03
depth 12, island 49, count 14465240724, time 2172.23
depth 12, island 50, count 14646746412, time 2194.51
depth 12, island 51, count 14828083716, time 2216.63
depth 12, island 52, count 15009012876, time 2238.80
depth 12, island 53, count 15190213248, time 2260.75
depth 12, island 54, count 15371479488, time 2282.67
depth 12, island 55, count 15552985176, time 2304.61
depth 12, island 56, count 15732758316, time 2326.36
depth 12, island 57, count 15913958688, time 2348.31
depth 12, island 58, count 16094771892, time 2369.98
depth 12, island 59, count 16275585096, time 2391.57
depth 12, island 60, count 16456922400, time 2413.34
depth 12, island 61, count 16637851560, time 2435.08
depth 12, island 62, count 16819357248, time 2456.95
depth 12, island 63, count 17000170452, time 2478.60
depth 12, island 64, count 17181507756, time 2500.39
depth 12, island 65, count 17363013444, time 2522.19
depth 12, island 66, count 17543826648, time 2543.76
depth 12, island 67, count 17725332336, time 2565.47
depth 12, island 68, count 17906838024, time 2587.14
depth 12, island 69, count 18087940968, time 2608.79
depth 13, island  0, count 18246381888, time 2628.66
depth 13, island  1, count 18404592432, time 2648.41
depth 13, island  2, count 18562802976, time 2668.04
depth 13, island  3, count 18721317768, time 2687.54
depth 13, island  4, count 18879528312, time 2706.88
depth 13, island  5, count 19037805708, time 2726.21
depth 13, island  6, count 19196320500, time 2745.49
depth 13, island  7, count 19354531044, time 2764.65
depth 13, island  8, count 19512887808, time 2783.89
depth 13, island  9, count 19671165204, time 2803.04
depth 13, island 10, count 19829679996, time 2822.53
depth 13, island 11, count 19988194788, time 2841.81
depth 13, island 12, count 20146475316, time 2860.79
depth 13, island 13, count 20305323624, time 2879.67
depth 13, island 14, count 20463534168, time 2898.71
depth 13, island 15, count 20621803872, time 2917.54
depth 13, island 16, count 20780084400, time 2936.48
depth 13, island 17, count 20938441164, time 2955.28
depth 13, island 18, count 21096718560, time 2974.21
depth 13, island 19, count 21254929104, time 2992.95
depth 13, island 20, count 21413443896, time 3011.42
depth 13, island 21, count 21571958688, time 3029.91
depth 13, island 22, count 21730806996, time 3048.30
depth 13, island 23, count 21889163760, time 3066.71
depth 13, island 24, count 22048012068, time 3085.10
depth 13, island 25, count 22206222612, time 3103.47
depth 13, island 26, count 22364503140, time 3121.77
depth 13, island 27, count 22522772844, time 3140.14
depth 13, island 28, count 22681621152, time 3158.49
depth 13, island 29, count 22839977916, time 3176.87
depth 13, island 30, count 22998492708, time 3195.15
depth 13, island 31, count 23156773236, time 3213.48
depth 13, island 32, count 23315050632, time 3231.79
depth 13, island 33, count 23473565424, time 3250.04
depth 13, island 34, count 23631775968, time 3268.35
depth 13, island 35, count 23789986512, time 3287.02
depth 13, island 36, count 23948501304, time 3305.99
depth 13, island 37, count 24106778700, time 3324.54
depth 13, island 38, count 24265059228, time 3342.99
depth 13, island 39, count 24423574020, time 3361.63
depth 13, island 40, count 24581930784, time 3380.10
depth 13, island 41, count 24740779092, time 3398.47
depth 13, island 42, count 24899048796, time 3416.93
depth 13, island 43, count 25057329324, time 3435.27
depth 13, island 44, count 25215539868, time 3453.65
depth 13, island 45, count 25374388176, time 3472.08
depth 13, island 46, count 25532744940, time 3490.45
depth 13, island 47, count 25691593248, time 3508.79
depth 13, island 48, count 25850108040, time 3527.10
depth 13, island 49, count 26008622832, time 3545.39
depth 13, island 50, count 26166833376, time 3563.67
depth 13, island 51, count 26325110772, time 3581.97
depth 13, island 52, count 26483467536, time 3600.26
depth 13, island 53, count 26641748064, time 3618.54
depth 13, island 54, count 26800017768, time 3636.84
depth 13, island 55, count 26958228312, time 3655.09
depth 13, island 56, count 27117076620, time 3673.42
depth 13, island 57, count 27275357148, time 3691.70
depth 13, island 58, count 27433871940, time 3709.97
depth 13, island 59, count 27592386732, time 3728.29
depth 13, island 60, count 27750664128, time 3746.57
depth 13, island 61, count 27909020892, time 3764.84
depth 13, island 62, count 28067231436, time 3783.08
depth 13, island 63, count 28225746228, time 3801.30
depth 13, island 64, count 28384023624, time 3819.54
depth 13, island 65, count 28542234168, time 3837.76
depth 13, island 66, count 28700748960, time 3855.95
depth 13, island 67, count 28858959504, time 3874.10
depth 13, island 68, count 29017170048, time 3892.32
depth 13, island 69, count 29175610968, time 3910.52
depth 14, island  0, count 29188539264, time 3912.26
depth 14, island  1, count 29201412192, time 3913.98
depth 14, island  2, count 29214285120, time 3915.71
depth 14, island  3, count 29227617924, time 3917.45
depth 14, island  4, count 29240490852, time 3919.17
depth 14, island  5, count 29253388824, time 3920.89
depth 14, island  6, count 29266721628, time 3922.64
depth 14, island  7, count 29279594556, time 3924.36
depth 14, island  8, count 29292839700, time 3926.12
depth 14, island  9, count 29305737672, time 3927.84
depth 14, island 10, count 29319070476, time 3929.67
depth 14, island 11, count 29332403280, time 3931.44
depth 14, island 12, count 29345366304, time 3933.16
depth 14, island 13, count 29359211988, time 3934.98
depth 14, island 14, count 29372084916, time 3936.70
depth 14, island 15, count 29384932452, time 3938.41
depth 14, island 16, count 29397895476, time 3940.11
depth 14, island 17, count 29411140620, time 3941.87
depth 14, island 18, count 29424038592, time 3943.61
depth 14, island 19, count 29436911520, time 3945.33
depth 14, island 20, count 29450244324, time 3947.08
depth 14, island 21, count 29463577128, time 3948.80
depth 14, island 22, count 29477422812, time 3950.57
depth 14, island 23, count 29490667956, time 3952.33
depth 14, island 24, count 29504513640, time 3954.14
depth 14, island 25, count 29517386568, time 3955.85
depth 14, island 26, count 29530349592, time 3957.57
depth 14, island 27, count 29543197128, time 3959.28
depth 14, island 28, count 29557042812, time 3961.08
depth 14, island 29, count 29570287956, time 3962.84
depth 14, island 30, count 29583620760, time 3964.60
depth 14, island 31, count 29596583784, time 3966.32
depth 14, island 32, count 29609481756, time 3968.04
depth 14, island 33, count 29622814560, time 3969.80
depth 14, island 34, count 29635687488, time 3971.52
depth 14, island 35, count 29648560416, time 3973.24
depth 14, island 36, count 29661893220, time 3975.01
depth 14, island 37, count 29674791192, time 3976.74
depth 14, island 38, count 29687754216, time 3978.46
depth 14, island 39, count 29701087020, time 3980.23
depth 14, island 40, count 29714332164, time 3981.99
depth 14, island 41, count 29728177848, time 3983.77
depth 14, island 42, count 29741025384, time 3985.49
depth 14, island 43, count 29753988408, time 3987.21
depth 14, island 44, count 29766861336, time 3988.93
depth 14, island 45, count 29780707020, time 3990.75
depth 14, island 46, count 29793952164, time 3992.51
depth 14, island 47, count 29807797848, time 3994.29
depth 14, island 48, count 29821130652, time 3996.03
depth 14, island 49, count 29834463456, time 3997.79
depth 14, island 50, count 29847336384, time 3999.51
depth 14, island 51, count 29860234356, time 4001.23
depth 14, island 52, count 29873479500, time 4002.99
depth 14, island 53, count 29886442524, time 4004.68
depth 14, island 54, count 29899290060, time 4006.39
depth 14, island 55, count 29912162988, time 4008.11
depth 14, island 56, count 29926008672, time 4009.92
depth 14, island 57, count 29938971696, time 4011.65
depth 14, island 58, count 29952304500, time 4013.41
depth 14, island 59, count 29965637304, time 4015.18
depth 14, island 60, count 29978535276, time 4016.90
depth 14, island 61, count 29991780420, time 4018.65
depth 14, island 62, count 30004653348, time 4020.36
depth 14, island 63, count 30017986152, time 4022.12
depth 14, island 64, count 30030884124, time 4023.84
depth 14, island 65, count 30043757052, time 4025.56
depth 14, island 66, count 30057089856, time 4027.30
depth 14, island 67, count 30069962784, time 4029.02
depth 14, island 68, count 30082835712, time 4030.74
depth 14, island 69, count 30095764008, time 4032.47
depth 15, island  0, count 30095800032, time 4032.49
depth 15, island  1, count 30095837520, time 4032.52
depth 15, island  2, count 30095875008, time 4032.54
depth 15, island  3, count 30095920992, time 4032.57
depth 15, island  4, count 30095958480, time 4032.59
depth 15, island  5, count 30095995620, time 4032.61
depth 15, island  6, count 30096041604, time 4032.64
depth 15, island  7, count 30096079092, time 4032.66
depth 15, island  8, count 30096122064, time 4032.69
depth 15, island  9, count 30096159204, time 4032.71
depth 15, island 10, count 30096205188, time 4032.73
depth 15, island 11, count 30096251172, time 4032.76
depth 15, island 12, count 30096290064, time 4032.78
depth 15, island 13, count 30096345768, time 4032.81
depth 15, island 14, count 30096383256, time 4032.83
depth 15, island 15, count 30096420492, time 4032.85
depth 15, island 16, count 30096459384, time 4032.87
depth 15, island 17, count 30096502356, time 4032.90
depth 15, island 18, count 30096539496, time 4032.92
depth 15, island 19, count 30096576984, time 4032.94
depth 15, island 20, count 30096622968, time 4032.97
depth 15, island 21, count 30096668952, time 4032.99
depth 15, island 22, count 30096724656, time 4033.02
depth 15, island 23, count 30096767628, time 4033.04
depth 15, island 24, count 30096823332, time 4033.07
depth 15, island 25, count 30096860820, time 4033.10
depth 15, island 26, count 30096899712, time 4033.13
depth 15, island 27, count 30096936948, time 4033.16
depth 15, island 28, count 30096992652, time 4033.19
depth 15, island 29, count 30097035624, time 4033.24
depth 15, island 30, count 30097081608, time 4033.27
depth 15, island 31, count 30097120500, time 4033.31
depth 15, island 32, count 30097157640, time 4033.34
depth 15, island 33, count 30097203624, time 4033.37
depth 15, island 34, count 30097241112, time 4033.40
depth 15, island 35, count 30097278600, time 4033.44
depth 15, island 36, count 30097324584, time 4033.48
depth 15, island 37, count 30097361724, time 4033.52
depth 15, island 38, count 30097400616, time 4033.55
depth 15, island 39, count 30097446600, time 4033.58
depth 15, island 40, count 30097489572, time 4033.62
depth 15, island 41, count 30097545276, time 4033.65
depth 15, island 42, count 30097582512, time 4033.68
depth 15, island 43, count 30097621404, time 4033.71
depth 15, island 44, count 30097658892, time 4033.74
depth 15, island 45, count 30097714596, time 4033.77
depth 15, island 46, count 30097757568, time 4033.81
depth 15, island 47, count 30097813272, time 4033.83
depth 15, island 48, count 30097859256, time 4033.86
depth 15, island 49, count 30097905240, time 4033.89
depth 15, island 50, count 30097942728, time 4033.92
depth 15, island 51, count 30097979868, time 4033.95
depth 15, island 52, count 30098022840, time 4033.98
depth 15, island 53, count 30098061732, time 4034.01
depth 15, island 54, count 30098098968, time 4034.04
depth 15, island 55, count 30098136456, time 4034.06
depth 15, island 56, count 30098192160, time 4034.10
depth 15, island 57, count 30098231052, time 4034.12
depth 15, island 58, count 30098277036, time 4034.16
depth 15, island 59, count 30098323020, time 4034.18
depth 15, island 60, count 30098360160, time 4034.21
depth 15, island 61, count 30098403132, time 4034.24
depth 15, island 62, count 30098440620, time 4034.27
depth 15, island 63, count 30098486604, time 4034.30
depth 15, island 64, count 30098523744, time 4034.33
depth 15, island 65, count 30098561232, time 4034.35
depth 15, island 66, count 30098607216, time 4034.38
depth 15, island 67, count 30098644704, time 4034.41
depth 15, island 68, count 30098682192, time 4034.43
depth 15, island 69, count 30098718216, time 4034.46
depth 16, island  0, count 30098718228, time 4037.51
depth 16, island  1, count 30098718228, time 4037.52
depth 16, island  2, count 30098718228, time 4037.53
depth 16, island  3, count 30098718228, time 4037.54
depth 16, island  4, count 30098718228, time 4037.55
depth 16, island  5, count 30098718240, time 4037.56
depth 16, island  6, count 30098718240, time 4037.57
depth 16, island  7, count 30098718240, time 4037.58
depth 16, island  8, count 30098718240, time 4037.59
depth 16, island  9, count 30098718252, time 4037.59
depth 16, island 10, count 30098718252, time 4037.61
depth 16, island 11, count 30098718252, time 4037.61
depth 16, island 12, count 30098718288, time 4037.62
depth 16, island 13, count 30098718300, time 4037.63
depth 16, island 14, count 30098718300, time 4037.64
depth 16, island 15, count 30098718300, time 4037.65
depth 16, island 16, count 30098718336, time 4037.66
depth 16, island 17, count 30098718336, time 4037.67
depth 16, island 18, count 30098718348, time 4037.68
depth 16, island 19, count 30098718348, time 4037.69
depth 16, island 20, count 30098718348, time 4037.70
depth 16, island 21, count 30098718348, time 4037.71
depth 16, island 22, count 30098718360, time 4037.72
depth 16, island 23, count 30098718360, time 4037.73
depth 16, island 24, count 30098718372, time 4037.74
depth 16, island 25, count 30098718372, time 4037.75
depth 16, island 26, count 30098718408, time 4037.76
depth 16, island 27, count 30098718408, time 4037.77
depth 16, island 28, count 30098718420, time 4037.79
depth 16, island 29, count 30098718420, time 4037.80
depth 16, island 30, count 30098718420, time 4037.81
depth 16, island 31, count 30098718456, time 4037.82
depth 16, island 32, count 30098718468, time 4037.83
depth 16, island 33, count 30098718468, time 4037.84
depth 16, island 34, count 30098718468, time 4037.86
depth 16, island 35, count 30098718468, time 4037.87
depth 16, island 36, count 30098718468, time 4037.88
depth 16, island 37, count 30098718480, time 4037.89
depth 16, island 38, count 30098718516, time 4037.91
depth 16, island 39, count 30098718516, time 4037.92
depth 16, island 40, count 30098718516, time 4037.93
depth 16, island 41, count 30098718528, time 4037.94
depth 16, island 42, count 30098718528, time 4037.95
depth 16, island 43, count 30098718564, time 4037.97
depth 16, island 44, count 30098718564, time 4037.98
depth 16, island 45, count 30098718576, time 4037.99
depth 16, island 46, count 30098718576, time 4038.01
depth 16, island 47, count 30098718588, time 4038.02
depth 16, island 48, count 30098718588, time 4038.03
depth 16, island 49, count 30098718588, time 4038.04
depth 16, island 50, count 30098718588, time 4038.05
depth 16, island 51, count 30098718600, time 4038.06
depth 16, island 52, count 30098718600, time 4038.07
depth 16, island 53, count 30098718636, time 4038.08
depth 16, island 54, count 30098718636, time 4038.09
depth 16, island 55, count 30098718636, time 4038.10
depth 16, island 56, count 30098718648, time 4038.11
depth 16, island 57, count 30098718684, time 4038.11
depth 16, island 58, count 30098718684, time 4038.12
depth 16, island 59, count 30098718684, time 4038.13
depth 16, island 60, count 30098718696, time 4038.14
depth 16, island 61, count 30098718696, time 4038.14
depth 16, island 62, count 30098718696, time 4038.15
depth 16, island 63, count 30098718696, time 4038.16
depth 16, island 64, count 30098718708, time 4038.17
depth 16, island 65, count 30098718708, time 4038.17
depth 16, island 66, count 30098718708, time 4038.18
depth 16, island 67, count 30098718708, time 4038.19
depth 16, island 68, count 30098718708, time 4038.19
depth 16, island 69, count 30098718720, time 4038.20
depth 17, island  0, count 30098718720, time 4041.04
depth 17, island  1, count 30098718720, time 4041.05
depth 17, island  2, count 30098718720, time 4041.06
depth 17, island  3, count 30098718720, time 4041.06
depth 17, island  4, count 30098718720, time 4041.07
depth 17, island  5, count 30098718720, time 4041.08
depth 17, island  6, count 30098718720, time 4041.09
depth 17, island  7, count 30098718720, time 4041.10
depth 17, island  8, count 30098718720, time 4041.10
depth 17, island  9, count 30098718720, time 4041.11
depth 17, island 10, count 30098718720, time 4041.12
depth 17, island 11, count 30098718720, time 4041.12
depth 17, island 12, count 30098718720, time 4041.13
depth 17, island 13, count 30098718720, time 4041.14
depth 17, island 14, count 30098718720, time 4041.15
depth 17, island 15, count 30098718720, time 4041.16
depth 17, island 16, count 30098718720, time 4041.17
depth 17, island 17, count 30098718720, time 4041.18
depth 17, island 18, count 30098718720, time 4041.19
depth 17, island 19, count 30098718720, time 4041.19
depth 17, island 20, count 30098718720, time 4041.20
depth 17, island 21, count 30098718720, time 4041.21
depth 17, island 22, count 30098718720, time 4041.22
depth 17, island 23, count 30098718720, time 4041.23
depth 17, island 24, count 30098718720, time 4041.24
depth 17, island 25, count 30098718720, time 4041.25
depth 17, island 26, count 30098718720, time 4041.26
depth 17, island 27, count 30098718720, time 4041.26
depth 17, island 28, count 30098718720, time 4041.27
depth 17, island 29, count 30098718720, time 4041.28
depth 17, island 30, count 30098718720, time 4041.29
depth 17, island 31, count 30098718720, time 4041.30
depth 17, island 32, count 30098718720, time 4041.30
depth 17, island 33, count 30098718720, time 4041.31
depth 17, island 34, count 30098718720, time 4041.32
depth 17, island 35, count 30098718720, time 4041.33
depth 17, island 36, count 30098718720, time 4041.33
depth 17, island 37, count 30098718720, time 4041.34
depth 17, island 38, count 30098718720, time 4041.35
depth 17, island 39, count 30098718720, time 4041.35
depth 17, island 40, count 30098718720, time 4041.36
depth 17, island 41, count 30098718720, time 4041.37
depth 17, island 42, count 30098718720, time 4041.38
depth 17, island 43, count 30098718720, time 4041.38
depth 17, island 44, count 30098718720, time 4041.39
depth 17, island 45, count 30098718720, time 4041.40
depth 17, island 46, count 30098718720, time 4041.41
depth 17, island 47, count 30098718720, time 4041.42
depth 17, island 48, count 30098718720, time 4041.43
depth 17, island 49, count 30098718720, time 4041.44
depth 17, island 50, count 30098718720, time 4041.44
depth 17, island 51, count 30098718720, time 4041.46
depth 17, island 52, count 30098718720, time 4041.46
depth 17, island 53, count 30098718720, time 4041.47
depth 17, island 54, count 30098718720, time 4041.48
depth 17, island 55, count 30098718720, time 4041.49
depth 17, island 56, count 30098718720, time 4041.50
depth 17, island 57, count 30098718720, time 4041.51
depth 17, island 58, count 30098718720, time 4041.52
depth 17, island 59, count 30098718720, time 4041.53
depth 17, island 60, count 30098718720, time 4041.53
depth 17, island 61, count 30098718720, time 4041.54
depth 17, island 62, count 30098718720, time 4041.55
depth 17, island 63, count 30098718720, time 4041.56
depth 17, island 64, count 30098718720, time 4041.57
depth 17, island 65, count 30098718720, time 4041.58
depth 17, island 66, count 30098718720, time 4041.59
depth 17, island 67, count 30098718720, time 4041.60
depth 17, island 68, count 30098718720, time 4041.60
depth 17, island 69, count 30098718720, time 4041.61

depth 16, island 69, count 30098718720, time 1331.48

Faster multithreaded version. Tested on an E5 2680 v4, resulting in a 3.5x speed-up. Ordering::Relaxed is surprisingly accurate

#![feature(new_uninit)]

use std::mem::MaybeUninit;
use std::sync::atomic::{AtomicUsize, Ordering, AtomicU8, AtomicU64};

use rayon::prelude::*;

// node is stored as 5 bits * 8. for bit, the eight S4 elements are separated into sign and A4.
// the A4 are all stored together as a base 12 number (29 bits), and the 8 signs are stored
// together in a bitfield at the MSB part. this concentrates the "islands" of elements together
// and keeps actual RSS at pretty much the real graph size (~3.5GiB/set) despite the ~16GiB/set
// virtual memory allocated. note that to make the code simpler, node stores the elements in
// *reverse* order to bit.

// this is the maximum bit value, NOT the used RAM
const LENGTH: usize = 2usize.pow(8 + 29);
const LENGTH_BYTES: usize = LENGTH / 8 + 1;
const LENGTH_QUADS: usize = LENGTH_BYTES / 8 + 1;

fn node_to_bit(mut node: usize) -> usize {
    let mut bit = 0;
    let mut signs = 0;

    for _ in 0..8 {
        // read from node
        let element = node % 32;
        node /= 32;

        // write to bit
        bit *= 12;
        bit += element / 2;

        // write to signs
        signs <<= 1;
        signs |= element % 2;
    }

    bit | (signs << 29)
}
fn bit_to_node(mut bit: usize) -> usize {
    let mut node = 0;
    let mut signs = bit >> 29;

    bit &= !((!0) << 29);

    for _ in 0..8 {
        // read from bit / signs
        let element = ((bit % 12) * 2) + (signs & 1);
        bit /= 12;
        signs >>= 1;

        // write to node
        node <<= 5;
        node |= element;
    }

    node
}

// sign combinations we will see
const SIGN_ISLANDS: [u8; 70] = [
    0, 3, 6, 9, 12, 15, 18, 24, 27, 30, 33, 36, 39, 45, 48, 51, 54, 57, 60, 63, 66, 72, 75, 78, 90,
    96, 99, 102, 105, 108, 111, 114, 120, 123, 126, 129, 132, 135, 141, 144, 147, 150, 153, 156,
    159, 165, 177, 180, 183, 189, 192, 195, 198, 201, 204, 207, 210, 216, 219, 222, 225, 228, 231,
    237, 240, 243, 246, 249, 252, 255,
];

// this updated representation of S4 as int has the property that the sign of the element is the LSB
const S4_MULT_TABLE: [u8; 24 * 24] = [
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 1, 0, 5,
    4, 3, 2, 7, 6, 11, 10, 9, 8, 19, 18, 21, 20, 23, 22, 13, 12, 15, 14, 17, 16, 2, 3, 4, 5, 0, 1,
    12, 13, 16, 17, 14, 15, 18, 19, 22, 23, 20, 21, 6, 7, 8, 9, 10, 11, 3, 2, 1, 0, 5, 4, 13, 12,
    15, 14, 17, 16, 7, 6, 9, 8, 11, 10, 19, 18, 23, 22, 21, 20, 4, 5, 0, 1, 2, 3, 18, 19, 20, 21,
    22, 23, 6, 7, 10, 11, 8, 9, 12, 13, 16, 17, 14, 15, 5, 4, 3, 2, 1, 0, 19, 18, 23, 22, 21, 20,
    13, 12, 17, 16, 15, 14, 7, 6, 11, 10, 9, 8, 6, 7, 10, 11, 8, 9, 0, 1, 4, 5, 2, 3, 20, 21, 18,
    19, 22, 23, 14, 15, 12, 13, 16, 17, 7, 6, 9, 8, 11, 10, 1, 0, 3, 2, 5, 4, 15, 14, 13, 12, 17,
    16, 21, 20, 19, 18, 23, 22, 8, 9, 6, 7, 10, 11, 14, 15, 12, 13, 16, 17, 0, 1, 2, 3, 4, 5, 20,
    21, 22, 23, 18, 19, 9, 8, 11, 10, 7, 6, 15, 14, 17, 16, 13, 12, 21, 20, 23, 22, 19, 18, 1, 0,
    3, 2, 5, 4, 10, 11, 8, 9, 6, 7, 20, 21, 22, 23, 18, 19, 14, 15, 16, 17, 12, 13, 0, 1, 4, 5, 2,
    3, 11, 10, 7, 6, 9, 8, 21, 20, 19, 18, 23, 22, 1, 0, 5, 4, 3, 2, 15, 14, 17, 16, 13, 12, 12,
    13, 14, 15, 16, 17, 2, 3, 0, 1, 4, 5, 8, 9, 6, 7, 10, 11, 22, 23, 18, 19, 20, 21, 13, 12, 17,
    16, 15, 14, 3, 2, 5, 4, 1, 0, 23, 22, 19, 18, 21, 20, 9, 8, 7, 6, 11, 10, 14, 15, 16, 17, 12,
    13, 8, 9, 10, 11, 6, 7, 22, 23, 20, 21, 18, 19, 2, 3, 0, 1, 4, 5, 15, 14, 13, 12, 17, 16, 9, 8,
    7, 6, 11, 10, 3, 2, 1, 0, 5, 4, 23, 22, 21, 20, 19, 18, 16, 17, 12, 13, 14, 15, 22, 23, 18, 19,
    20, 21, 2, 3, 4, 5, 0, 1, 8, 9, 10, 11, 6, 7, 17, 16, 15, 14, 13, 12, 23, 22, 21, 20, 19, 18,
    9, 8, 11, 10, 7, 6, 3, 2, 5, 4, 1, 0, 18, 19, 22, 23, 20, 21, 4, 5, 2, 3, 0, 1, 16, 17, 12, 13,
    14, 15, 10, 11, 6, 7, 8, 9, 19, 18, 21, 20, 23, 22, 5, 4, 1, 0, 3, 2, 11, 10, 7, 6, 9, 8, 17,
    16, 13, 12, 15, 14, 20, 21, 18, 19, 22, 23, 10, 11, 6, 7, 8, 9, 4, 5, 0, 1, 2, 3, 16, 17, 14,
    15, 12, 13, 21, 20, 23, 22, 19, 18, 11, 10, 9, 8, 7, 6, 17, 16, 15, 14, 13, 12, 5, 4, 1, 0, 3,
    2, 22, 23, 20, 21, 18, 19, 16, 17, 14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 0, 1, 23,
    22, 19, 18, 21, 20, 17, 16, 13, 12, 15, 14, 5, 4, 3, 2, 1, 0, 11, 10, 9, 8, 7, 6,
];

// a*b in mathematical order, i.e. b applied first, then a
fn mult(a: u8, b: u8) -> u8 {
    let index = (a as usize) * 24 + (b as usize);
    *unsafe { S4_MULT_TABLE.get_unchecked(index) }
}

static mut SEEN_SET: MaybeUninit<&mut [AtomicU8; LENGTH_BYTES]> = MaybeUninit::uninit();
static mut PENDING_SET: MaybeUninit<&mut [AtomicU64; LENGTH_QUADS]> = MaybeUninit::uninit();
static mut QUEUED_SET: MaybeUninit<&mut [AtomicU64; LENGTH_QUADS]> = MaybeUninit::uninit();
static COUNT: AtomicUsize = AtomicUsize::new(0);

fn visit(bit: usize) {
    let slot = unsafe { SEEN_SET.assume_init_read().get_unchecked(bit / 8) };
    let mask = 1u8 << (bit % 8);
    if ((slot.fetch_or(mask, Ordering::Relaxed)) & mask) != 0 {
        return;
    }

    // count & queue it
    COUNT.fetch_add(1, Ordering::Relaxed);
    let slot = unsafe { QUEUED_SET.assume_init_read().get_unchecked(bit / 64) };
    let mask = 1u64 << (bit % 64);
    slot.fetch_or(mask, Ordering::Relaxed);
}

type Element = [(u8, u8); 3]; // a cycle of crosses, each tuple is (cross number, rotation applied before permuting)
const NEIGHBORS: [Element; 8] = [
    [(0, 11), (1, 20), (7, 23)],
    [(0, 17), (7, 14), (1, 13)],
    [(5, 13), (6, 23), (7, 18)],
    [(5, 10), (7, 17), (6, 11)],
    [(3, 17), (4, 13), (5, 12)],
    [(3, 8), (5, 11), (4, 23)],
    [(1, 11), (2, 17), (3, 4)],
    [(1, 2), (3, 23), (2, 13)],
];

fn process_pending(root: usize) {
    for el in NEIGHBORS {
        let mut root = root;

        fn swap_slot(root: &mut usize, cross: (u8, u8), value: u8) -> u8 {
            let bit = cross.0 * 5;
            let element = ((*root >> bit) & 0b11111usize) as u8;
            *root &= !(0b11111usize << bit);
            *root |= (value as usize) << bit;
            mult(cross.1, element)
        }

        // do the cycle
        let mut previous = swap_slot(&mut root, el[0], 0);

        for cross in &el[1..] {
            previous = swap_slot(&mut root, *cross, previous);
        }

        root |= (previous as usize) << (el[0].0 * 5);

        // visit
        visit(node_to_bit(root));
    }
}

fn bfs_pass_island(island: u8) {
    let words_per_island = 12usize.pow(8) / 64 + 1;
    let start = ((island as usize) << 29) / 64;

    (start..(start + words_per_island))
        .into_par_iter()
        //.into_iter()
        .for_each(|index| {
            let word = unsafe { PENDING_SET.assume_init_read().get_unchecked(index) };

            if word.load(Ordering::Relaxed) == 0 {
                return
            }

            for i in 0..64 {
                if ((word.load(Ordering::Relaxed)) & (1 << i)) == 0 {
                    continue;
                }

                let node = bit_to_node((index * 64) | i);
                process_pending(node);
            }

            word.store(0, Ordering::Relaxed);
        });
}

fn main() {
    {
        let b = Box::new_zeroed();
        let b = unsafe { b.assume_init() };
        let b = Box::leak(b);
        unsafe { PENDING_SET.write(b) };
    }
    {
        let b = Box::new_zeroed();
        let b = unsafe { b.assume_init() };
        let b = Box::leak(b);
        unsafe { QUEUED_SET.write(b) };
    }
    {
        println!("start allocating");
        let b = Box::new_zeroed();
        let b = unsafe { b.assume_init() };
        println!("end allocating");
        let b = Box::leak(b);
        unsafe { SEEN_SET.write(b) };
    }

    let start = std::time::Instant::now();

    for orient in 0..24 {
        let mut root = 0;
        for _ in 0..8 {
            root <<= 5;
            root |= orient;
        }
        visit(node_to_bit(root));
    }

    for depth in 1..24 {
        unsafe { std::mem::swap(&mut PENDING_SET, &mut QUEUED_SET) };

        for (idx, island) in SIGN_ISLANDS.iter().enumerate() {
            bfs_pass_island(*island);

            let now = start.elapsed().as_secs_f32();
            let count = COUNT.load(Ordering::Relaxed);

            println!("depth {depth:2}, island {idx:2}, count {count:11}, time {now:.2}");
        }
    }
}

thanks, luv u 💙