明治ミルクチョコレートパズル（ブラック）：回答編

programming

いきなり回答編ですが。

最近研究室の後ろに座ってる人がこれ（http://www.amazon.co.jp/%E3%83%8F%E3%83%8A%E3%83%A4%E3%83%9E-%E6%98%8E%E6%B2%BB%E3%83%9F%E3%83%AB%E3%82%AF%E3%83%81%E3%83%A7%E3%82%B3%E3%83%91%E3%82%BA%E3%83%AB/dp/B000BVN0AA）を持っていて、遊んでいたら元に戻せなくなったのでプログラムを書きました。最初std::vector >でピースを管理してたので全ての解を表示するのに2時間強かかってましたが、最終的にピースをunsignedな64bit整数にしてビット演算でほげほげするようにしたら5分で終わるようになりました。アルゴリズムは単純な深さ優先探索+枝刈り（全てのピースは5つのマスを占有するので、連続した空きマスで個数の和が5の倍数になっていないようなものを見つけたら刈る）です。固有な解は2339ですが、裏表を反転したものと180度回転したものを含めて2339 * 2 * 2 = 9356個の解を表示するようになっています。

#include <iostream>
#include <set>

using namespace std;

typedef unsigned long long ull;

char color[10][6];
ull choco[12][8 * 10 * 6];
int choco_size[12];
ull pieces[12] = { 271,527,8642,12676,8327,16833,199,327,28737,31,899,16834 };

inline ull Pos(int i, int j) { return 1LL << (i * 6 + j); }
inline ull At(ull n, int i, int j) { return n & Pos(i, j); }

ull Rotate90(ull n, int maxr, int maxc) {
  ull ret = 0;
  for (int i = 0; i <= maxr; ++i) {
    for (int j = 0; j <= maxc; ++j) {
      if (At(n, i, j)) {
        ret |= Pos(j, maxr - i);
      }
    }
  }
  return ret;
}

ull Reverse(ull n, int maxr, int maxc) {
  ull ret = 0;
  for (int i = 0; i <= maxr; ++i) {
    for (int j = 0; j <= maxc; ++j) {
      if (At(n, i, j)) {
        ret |= Pos(i, maxc - j);
      }
    }
  }
  return ret;
}

int dr[] = {1, 0, -1, 0};
int dc[] = {0, 1, 0, -1};

int Count(ull &b, int r, int c) {
  b |= Pos(r, c);
  int ret = 1;
  for (int i = 0; i < 4; ++i) {
    int nr = r + dr[i], nc = c + dc[i];
    if (0 <= nr && nr < 10 &&
        0 <= nc && nc < 6 &&
        !At(b, nr, nc)) {
      ret += Count(b, nr, nc);
    }
  }
  return ret;
}

void Dfs(int depth, ull board) {
  static int num = 0;
  if (depth == 12) {
    printf("Answer %d:\n", ++num);
    for (int j = 0; j < 6; ++j) {
      for (int i = 0; i < 10; ++i) {
        cout << color[i][j];
      }
      cout << endl;
    }
    cout << endl;
  } else {
    for (int i = 0; i < choco_size[depth]; ++i) {
      ull shifted = choco[depth][i];
      if (!(board & shifted)) {
        ull board_shifted = board | shifted;
        for (int ii = 0; ii < 10; ++ii) {
          for (int jj = 0; jj < 6; ++jj) {
            if (At(shifted, ii, jj)) {
              for (int k = 0; k < 4; ++k) {
                int iii = ii + dr[k];
                int jjj = jj + dc[k];
                if (0 <= iii && iii < 10 &&
                    0 <= jjj && jjj < 6 &&
                    !At(board_shifted, iii, jjj) &&
                    Count(board_shifted, iii, jjj) % 5) {
                  goto NEXT;
                }
              }
              color[ii][jj] = 'A' + depth;
            }
          }
        }
        Dfs(depth + 1, board | shifted);
      }
    NEXT:;
    }
  }
}

int main() {
  for (int k = 0; k < 12; ++k) {
    ull piece = pieces[k];
    int maxr;
    int maxc;
    set<ull> chocok;
    for (int r = 0; r < 2; ++r) {
      for (int d = 0; d < 4; ++d) {
        maxr = 0;
        maxc = 0;
        for (int i = 0; i < 10; ++i) {
          for (int j = 0; j < 6; ++j) {
            if (At(piece, i, j)) {
              maxr = max(maxr, i);
              maxc = max(maxc, j);
            }
          }
        }
        for (int i = 0; i + maxr < 10; ++i) {
          for (int j = 0; j + maxc < 6; ++j) {
            chocok.insert(piece << (i * 6 + j));
          }
        }
        piece = Rotate90(piece, maxr, maxc);
        swap(maxr, maxc);
      }
      piece = Reverse(piece, maxr, maxc);
    }
    for (set<ull>::iterator it = chocok.begin(); it != chocok.end(); ++it) {
      choco[k][choco_size[k]++] = *it;
    }
  }
  Dfs(0, 0);
}

一つの解はこのように表示されます。

Answer 1:
ABBHHCIIIJ
AABHCCCDIJ
AKBHHCDDIJ
AKBFFDDLEJ
KKGGFLLLEJ
KGGGFFLEEE