Algorithm to solve Baguenaudier (aka. Chinese Rings)

baguenaudier.cpp

#include <cstdio>
#include <algorithm>

const int MAX_N = 20;
int n;
bool state[MAX_N];
int count_op = 0;

void print_state()
{
    for (int i = n - 1; i >= 0; i--) {
        printf("%d", state[i]);
    }
    printf("\n");
}

void flip(int c)
{
    state[c] = !state[c];
    print_state();
    count_op++;
}

void solve(int n);
void rsolve(int n);

// 111 -> 000
void solve(int n)
{
    if (n == 1) {
        flip(0);
    } else if (n == 2) {
        flip(1);
        solve(1);
    } else {
        solve(n - 2);
        flip(n - 1);
        rsolve(n - 2);
        solve(n - 1);
    }
}

// 000 -> 111
void rsolve(int n)
{
    if (n == 1) {
        flip(0);
    } else if (n == 2) {
        rsolve(1);
        flip(1);
    } else {
        rsolve(n - 1);
        solve(n - 2);
        flip(n - 1);
        rsolve(n - 2);
    }
}

int main()
{
    printf("How many rings?\n");
    scanf("%d", &n);
    std::fill_n(state, n, 1);
    printf("Solution:\n");
    print_state();
    solve(n);
    printf("Steps: %d\n", count_op);
}