gistfile1.txt

#include <iostream>
enum e { a, c, d };
class o {
  uint32_t b = 0;
  void p(int c) { b |= 1 << c; }
  bool s(int c) { return b >> c & 1; }

public:
  void t(int f, int col, e h) {
    int g = 2 * (3 * f + col);
    switch (h) {
    case c:
      p(g + 1);
      break;
    case d:
      int c = g;
      b |= 1 << c;
      p(g + 1);
    }
  }
  e u(int f, int col) {
    int v = 2 * (3 * f + col);
    if (!s(v + 1))
      return a;
    if (s(v))
      return d;
    return c;
  }
};
bool draw(o b) {
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
      if (b.u(i, j) == a)
        return false;
  return true;
}
bool k(o b, int f) {
  return b.u(f, 0) && b.u(f, 0) == b.u(f, 1) && b.u(f, 0) == b.u(f, 2);
}
bool l(o b, int col) {
  return b.u(0, col) && b.u(0, col) == b.u(1, col) &&
         b.u(0, col) == b.u(2, col);
}
bool m(o b) {
  for (int i = 0; i < 3; i++) {
    if (k(b, i))
      return true;
    if (l(b, i))
      return true;
  }
  if (b.u(0, 0) && b.u(0, 0) == b.u(1, 1) && b.u(0, 0) == b.u(2, 2))
    return true;
  if (b.u(0, 2) && b.u(0, 2) == b.u(1, 1) && b.u(0, 2) == b.u(2, 0))
    return true;
  return false;
}
e n(e q) {
  if (q == c)
    return d;
  return c;
}
long play(o b, e q) {
  if (draw(b) || m(b))
    return 1;
  long count = 0;
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
      if (b.u(i, j) == a) {
        o r = b;
        r.t(i, j, q);
        e w = n(q);
        count += play(r, w);
      }
  return count;
}
int main() {
  o b;
  std::cout << play(b, c) << "\n";
}