明治チョコレートパズルを解くプログラムを書いてみた

www.hanayamatoys.co.jp

問題

以下のブロックを6*11のグリッドにぴったり入るように置いてください。

答え

コード

ライセンスはMITです

#include <cstring>

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits>
#include <iterator>

using std::vector;
using std::string;

namespace {

const int kWidth  = 6;
const int kHeight = 11;
const int kNumBlocks = 11;
const int kNumPiece = 6;
const int kBlockX[kNumBlocks][kNumPiece] = {
  { 0, 1, 0, 0, 1, 2 },
  { 0, 0, 1, 0, 1, 2 },
  { 1, 2, 0, 1, 1, 2 },
  { 0, 1, 2, 2, 3, 2 },
  { 1, 0, 1, 2, 3, 4 },
  { 1, 3, 0, 1, 2, 3 },
  { 0, 1, 3, 1, 2, 3 },
  { 0, 1, 2, 3, 4, 4 },
  { 0, 1, 1, 2, 3, 4 },
  { 0, 1, 2, 1, 2, 3 },
  { 1, 0, 1, 2, 3, 1 },
};
const int kBlockY[kNumBlocks][kNumPiece] = {
  { 0, 0, 1, 2, 2, 2 },
  { 0, 1, 1, 2, 2, 2 },
  { 0, 0, 1, 1, 2, 2 },
  { 0, 0, 0, 1, 1, 2 },
  { 0, 1, 1, 1, 1, 1 },
  { 0, 0, 1, 1, 1, 1 },
  { 0, 0, 0, 1, 1, 1 },
  { 0, 0, 0, 0, 0, 1 },
  { 0, 0, 1, 1, 1, 1 },
  { 0, 0, 0, 1, 1, 1 },
  { 0, 1, 1, 1, 1, 2 },
};

class Block {
 public:
  Block(const int id) : x_(kNumPiece), y_(kNumPiece) {
    for(int i = 0; i < kNumPiece; i++) {
      x_[i] = kBlockX[id][i];
      y_[i] = kBlockY[id][i];
    }
  }

  int x(const int i) const {
    return x_[i];
  }
  int y(const int i) const {
    return y_[i];
  }

  void Rotate(const int num_rot);
  void Show();

  int SearchXMin() const {
    return *std::min_element(x_.cbegin(), x_.cend());
  }

  int SearchXMax() const {
    return *std::max_element(x_.cbegin(), x_.cend());
  }

  int SearchYMin() const {
    return *std::min_element(y_.cbegin(), y_.cend());
  }

  int SearchYMax() const {
    return *std::max_element(y_.cbegin(), y_.cend());
  }

 private:
  vector<int> x_;
  vector<int> y_;
  void Rotate();
};

std::ostream &operator <<(std::ostream& os, const Block &b) {
  const int xmax = b.SearchXMax();
  const int ymax = b.SearchYMax();

  vector<string> vs(ymax + 1, string(xmax + 1, ' '));
  for(int i = 0; i < kNumPiece; i++) {
    vs[b.y(i)][b.x(i)] = 'x';
  }

  for(int i = 0; i < static_cast<int>(vs.size()); i++) {
    os << vs[i];
    if(i != static_cast<int>(vs.size()) - 1) {
      os << std::endl;
    }
  }

  return os;
}

void Block::Show() {
  std::cerr << *this << std::endl;
  std::cerr << "--" << std::endl;
}

void Block::Rotate() {
  for(int i = 0; i < kNumPiece; i++) {
    int nx =  1 * y_[i];
    int ny = -1 * x_[i];
    x_[i] = nx;
    y_[i] = ny;
  }
}

void Block::Rotate(const int num_rot) {
  for(int i = 0; i < num_rot; i++) {
    Rotate();
  }

  const int xmin = SearchXMin();
  const int ymin = SearchYMin();

  for(int i = 0; i < kNumPiece; i++) {
    x_[i] -= xmin;
    y_[i] -= ymin;
  }
}

bool used[kNumBlocks];
int field[kHeight][kWidth];

bool TryPut(int id, int rot) {
  Block b(id);
  b.Rotate(rot);

  int ymin_field = std::numeric_limits<int>::max();
  int xmin_field = std::numeric_limits<int>::max();
  for(int y = 0; y < kHeight; y++) {
    for(int x = 0; x < kWidth; x++) {
      if(field[y][x] == 0) {
        ymin_field = y;
        xmin_field = x;
        goto exit;
      }
    }
  }
exit:

  int ymin_block = std::numeric_limits<int>::max();
  int xmin_block = std::numeric_limits<int>::max();
  for(int i = 0; i < kNumPiece; i++) {
    if(b.y(i) < ymin_block) {
      ymin_block = b.y(i);
      xmin_block = b.x(i);
    }

    if(b.y(i) == ymin_block && b.x(i) < xmin_block) {
      ymin_block = b.y(i);
      xmin_block = b.x(i);
    }
  }
  
  for(int i = 0; i < kNumPiece; i++) {
    int pos_x = b.x(i) - xmin_block + xmin_field;
    int pos_y = b.y(i) - ymin_block + ymin_field;
    if(!(0 <= pos_x && pos_x < kWidth && 0 <= pos_y && pos_y < kHeight)) {
      return false;
    }
    if(field[pos_y][pos_x] != 0) return false;
  }

  for(int i = 0; i < kNumPiece; i++) {
    int pos_x = b.x(i) - xmin_block + xmin_field;
    int pos_y = b.y(i) - ymin_block + ymin_field;
    field[pos_y][pos_x] = id + 1;
  }

  return true;
}

void Remove(int id) {
  for(int y = 0; y < kHeight; y++) {
    for(int x = 0; x < kWidth; x++) {
      if(field[y][x] == id + 1) {
        field[y][x] = 0;
      }
    }
  }
}

void Perm(const int pos, const int end) {
  if(pos == 0) {
    memset(used, 0, sizeof(used));
    memset(field, 0, sizeof(field));
  }

  if(pos == end) {
    // 結果を表示
    for(int y = 0; y < kHeight; y++) {
      for(int x = 0; x < kWidth; x++) {
        std::cout << std::hex << field[y][x];
      }
      std::cout << std::endl;
    }
    std::cout << "--" << std::endl;

    return;
  }

  for(int i = 0; i < end; i++) {
    if(used[i] == false) {
      used[i] = true;

      // 置けるなら、次のブロックを置く
      for(int r = 0; r < 4; r++) {
        if(TryPut(i, r)) {
          Perm(pos + 1, end);
          Remove(i);
        }
      }

      // 状態を戻す
      used[i] = false;
    }
  }
}

} // namespace

int main() {
  Perm(0, kNumBlocks);
}