Skip to content

Instantly share code, notes, and snippets.

@fuyufjh
Created July 23, 2016 18:19
Show Gist options
  • Save fuyufjh/6bb9ead7271d0320077859622b0c9c28 to your computer and use it in GitHub Desktop.
Save fuyufjh/6bb9ead7271d0320077859622b0c9c28 to your computer and use it in GitHub Desktop.
Algorithm to solve Baguenaudier (aka. Chinese Rings)
#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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment