Drive Ya Nuts Solver

drive_ya_nuts.cc

// Solution to Drive Ya Nuts
// http://www.hasbro.com/common/instruct/DriveYaNuts.PDF
//
// Program output:
//
//     1 3 5 4 2 6
//     1 5 3 2 6 4
//     3 4 5 6 1 2
//     5 2 4 6 1 3
//     4 3 2 1 6 5
//     2 5 6 3 4 1
//     6 1 4 2 3 5
//
//     1 solutions found.
//     Finished in 8.7104e-05s

#include <iostream>
#include <array>
#include <algorithm>
#include <chrono>

#define CREATE_RING(a, b, c, d, e, f) ( \
    (a) | ((b) << 3) | ((c) << 6) | ((d) << 9) | \
    ((e) << 12) | ((f) << 15) \
)

std::array<int, 7> rings = {
    // Drive Ya Nuts Pieces
    CREATE_RING(1, 2, 3, 4, 5, 6),
    CREATE_RING(1, 2, 5, 6, 3, 4),
    CREATE_RING(1, 3, 5, 2, 4, 6),
    CREATE_RING(1, 3, 5, 4, 2, 6),
    CREATE_RING(1, 4, 2, 3, 5, 6),
    CREATE_RING(1, 5, 3, 2, 6, 4),
    CREATE_RING(1, 6, 5, 4, 3, 2),

    // Pieces with 31 unique solutions
    // CREATE_RING(1, 2, 3, 4, 5, 6),
    // CREATE_RING(1, 2, 3, 4, 6, 5),
    // CREATE_RING(1, 2, 3, 5, 4, 6),
    // CREATE_RING(1, 2, 3, 5, 6, 4),
    // CREATE_RING(1, 4, 2, 3, 5, 6),
    // CREATE_RING(1, 4, 2, 6, 3, 5),
    // CREATE_RING(1, 5, 2, 6, 3, 4),
};

inline int get_ring_side(int ring, int side) {
    return (ring >> (side * 3)) & 7;
}

inline int rotate_ring(int ring) {
    return (ring >> 3) | ((ring & 7) << 15);
}

void print_ring(int ring) {
    std::cout << get_ring_side(ring, 0) << ' '
              << get_ring_side(ring, 1) << ' '
              << get_ring_side(ring, 2) << ' '
              << get_ring_side(ring, 3) << ' '
              << get_ring_side(ring, 4) << ' '
              << get_ring_side(ring, 5) << std::endl;
}

int solve_center(int num) {
    int center = rings[num];
    int solution_count = 0;
    std::array<int, 6> edges, state;

    for (int i = 0, j = 0; i < 7; i++)
        if (i != num)
            edges[j++] = rings[i];

    do {
        bool is_solution = true;
        std::copy(edges.begin(), edges.end(), state.begin());
        for (int i = 0; i < 6; i++) {
            int match = get_ring_side(center, i);
            while (get_ring_side(state[i], 0) != match)
                state[i] = rotate_ring(state[i]);
            if (i == 0)
                continue;
            if (get_ring_side(state[i], 1) != get_ring_side(state[i - 1], 5)) {
                is_solution = false;
                break;
            }
        }
        if (is_solution) {
            solution_count += 1;
            print_ring(center);
            std::for_each(state.begin(), state.end(), print_ring);
            std::cout << std::endl;
        }
    } while (std::next_permutation(edges.begin(), edges.end()));
    return solution_count;
}

int solve() {
    int solution_count = 0;
    std::sort(rings.begin(), rings.end());
    for (int i = 0; i < 7; i++)
        solution_count += solve_center(i);
    return solution_count;
}

int main() {
    using namespace std::chrono;
    high_resolution_clock::time_point t1 = high_resolution_clock::now();

    int solution_count = solve();

    high_resolution_clock::time_point t2 = high_resolution_clock::now();
    duration<double> time = duration_cast<duration<double>>(t2 - t1);
    std::cout << solution_count << " solutions found.\n";
    std::cout << "Finished in " << time.count() << "s\n";
}