Chinese Rings Puzzle Solver

main.cc

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// This class solves the Chinese Rings puzzle (https://en.wikipedia.org/wiki/Baguenaudier),
// optionally printing each move, and tells you how many moves it takes to solve it. It runs in O(2^N)
// time, because it actually simulates each move and it takes 2^N - 1 moves in the worst case.
class ChineseRings {
public:
  // Initializes the solver with the given state. Pass verbose = false to
  // suppress output, in case you're solving a large input.
  ChineseRings(const vector<bool> &initial_state, bool verbose = true)
      : state_(initial_state), verbose_(verbose) {}

  // If unspecified, then we'll solve for all rings off. Otherwise we solve for
  // the desired state.
  void Solve(const vector<bool> &desired_state = {}) {
    if (!desired_state.empty() && desired_state.size() != state_.size())
      cout << "Desired state must be the same size as initial state" << endl;

    PrintLastMove(-1); // show the initial state

    // We can solve each ring in order, starting from the largest index to the
    // smallest, since each ring is only limited by the rings that precede it.
    for (int i = state_.size() - 1; i >= 0; i--)
      SetRing(i, desired_state.empty() ? false : desired_state[i]);
  }

  int move_count() const { return move_cnt_; }

private:
  // Sets the given ring N to the target state. This mutates all rings <= N, but
  // does not mutate any rings > N. It guarantees that the given index will be
  // set to the target upon return, although there is no guarantee about the
  // rings < N.
  //
  // This method is recursive, with maximum call depth of N.
  void SetRing(int N, bool target) {
    // Look at the current ring state.
    bool cur = state_[N];
    if (cur == target)
      return; // ring is already in desired state

    // We can change the ring at N=0 any time we want. Rings at N > 0 must
    // satisfy a precondition in order to be changed.
    if (N > 0) {
      // In order to change the state of the given ring, the ring at N-1 must be
      // the only one < N which is on. We don't care about any rings > N.
      SetRing(N - 1, true); // put on the ring at N-1
      for (int i = N - 2; i >= 0; i--)
        SetRing(i, false); // take off all the other rings < N
    }

    // Now we are free to change the state of the current ring.
    state_[N] = target;
    move_cnt_++;
    if (verbose_)
      PrintLastMove(N);
  }

  // Prints the last move to the console, for visual inspection.
  void PrintLastMove(int N) {
    string note = "Initial Position";
    if (N >= 0)
      note = state_[N] ? "Raise" : "Lower";
    cout << String() << " - " << note << " Index " << N << endl;
  }

  // Serializes the current puzzle state into a string.
  // 'N' indicates the ring is 'on' and 'F' indicates the ring is 'off'.
  string String() const {
    string ret;
    for (bool ring : state_) {
      ret += ring ? "N" : "F";
    }
    return ret;
  }

  // True = ON, False = OFF
  vector<bool> state_;
  vector<int> moves_;
  int64_t move_cnt_ = 0;
  bool verbose_ = false;
};

int main(int argc, char **argv) {
  // Solve the puzzle when all rings are initially "on".
  vector<bool> input{true, true, true, true, true, true, true, true, true};
  ChineseRings rings(input, /*verbose=*/true);
  rings.Solve();
  cout << "# of moves: " << rings.move_count() << endl;
  return 0;
}