Skip to content

Instantly share code, notes, and snippets.

@shirohana
Created October 25, 2016 05:20
Show Gist options
  • Save shirohana/094ea82fa73c3bf2e3ae097aba940dc7 to your computer and use it in GitHub Desktop.
Save shirohana/094ea82fa73c3bf2e3ae097aba940dc7 to your computer and use it in GitHub Desktop.
Tromino Puzzle Algorithm
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment