Tromino Puzzle Algorithm

tromino.cc

#include <iostream>
#include <iomanip>

class Tromino {
public:
  static int* Solve(int m, int block) {
    int width = static_cast<int> (pow(2, m));
    int *matrix = new int[width * width] {0};

    n_ = 1;
    step_ = width;
    Solve0(matrix, 0, width, block);
    return matrix;
  }

private:
  static int n_;
  static int step_;

  static void Solve0(int *matrix, int offset, int width, int block) {
    int block_quad = 0;
    block_quad += (block >= offset + (width / 2) * step_) ? 2 : 0;
    block_quad += (block % width >= (width / 2)) ? 1 : 0;

    // The left-top corner of the sub-matrix
    int quad_offset[] = {
      offset,
      offset + (width / 2),
      offset + (width / 2) * (step_),
      offset + (width / 2) * (step_ + 1)
    };

    // The central blocks would be fill with puzzle
    int center_blocks[] = {
      quad_offset[3] - 1 - step_,
      quad_offset[3] - step_,
      quad_offset[3] - 1,
      quad_offset[3]
    };

    if (width != 2) {
      for (int i = 0; i < 4; ++i)
        if (i == block_quad)
          Solve0(matrix, quad_offset[i], width / 2, block);
        else
          Solve0(matrix, quad_offset[i], width / 2, center_blocks[i]);
    }

    for (int i = 0; i < 4; ++i) {
      if (i != block_quad)
        matrix[center_blocks[i]] = n_;
    }
    ++n_;
  }
};

int Tromino::n_;
int Tromino::step_;

int main() {
  unsigned long m, block;

  while (true) {
    std::cout << "m(1~15): ";
    if (!(std::cin >> m) || m < 1 || 15 < m) {
      if (std::cin.eof()) break;
      std::cout << "Invalid m. m must be a non-zero positive integer\n\n";
      std::cin.clear();
      std::cin.ignore(INT32_MAX, '\n');
      continue;
    }

    int width = static_cast<int> (pow(2, m));
    int size = width * width;

    std::cout << "block pos(0~" << (size - 1) << "): ";
    if (!(std::cin >> block) || block < 0 || size <= block) {
      if (std::cin.eof()) break;
      std::cout << "Invalid block pos.\n\n";
      std::cin.clear();
      std::cin.ignore(INT32_MAX, '\n');
      continue;
    }

    int *matrix = Tromino::Solve(m, block);

    int max = ((width * width) - 1) / 3;
    int len = 0;
    while (++len && (max /= 10) != 0) {}

    for (int i = 0; i < width * width; ++i) {
      std::cout << std::setw(len) << matrix[i] << " ";
      if (i % width == width - 1)
        std::cout << std::endl;
    }

    std::cout << std::endl;

    delete[] matrix;
  }
  return 0;
}