160 lines
5.6 KiB
C++
160 lines
5.6 KiB
C++
#include <algorithm>
|
|
#include <cstdint>
|
|
#include <iostream>
|
|
#include <random>
|
|
#include <vector>
|
|
|
|
const std::vector<std::vector<int32_t>> F = { { 1, -1, 1, 0, 1, 1, 2, 1 }, { 0, 1, 1, -1, 1, 0, 2, 0 },
|
|
{ 1, 0, 1, 1, 1, 2, 2, 1 }, { 1, 0, 1, 1, 2, -1, 2, 0 }, { 1, -2, 1, -1, 1, 0, 2, -1 },
|
|
{ 0, 1, 1, 1, 1, 2, 2, 1 }, { 1, -1, 1, 0, 1, 1, 2, -1 }, { 1, -1, 1, 0, 2, 0, 2, 1 } };
|
|
|
|
const std::vector<std::vector<int32_t>> I = { { 0, 1, 0, 2, 0, 3, 0, 4 }, { 1, 0, 2, 0, 3, 0, 4, 0 } };
|
|
|
|
const std::vector<std::vector<int32_t>> L = { { 1, 0, 1, 1, 1, 2, 1, 3 }, { 1, 0, 2, 0, 3, -1, 3, 0 },
|
|
{ 0, 1, 0, 2, 0, 3, 1, 3 }, { 0, 1, 1, 0, 2, 0, 3, 0 }, { 0, 1, 1, 1, 2, 1, 3, 1 },
|
|
{ 0, 1, 0, 2, 0, 3, 1, 0 }, { 1, 0, 2, 0, 3, 0, 3, 1 }, { 1, -3, 1, -2, 1, -1, 1, 0 } };
|
|
|
|
const std::vector<std::vector<int32_t>> N = { { 0, 1, 1, -2, 1, -1, 1, 0 }, { 1, 0, 1, 1, 2, 1, 3, 1 },
|
|
{ 0, 1, 0, 2, 1, -1, 1, 0 }, { 1, 0, 2, 0, 2, 1, 3, 1 }, { 0, 1, 1, 1, 1, 2, 1, 3 },
|
|
{ 1, 0, 2, -1, 2, 0, 3, -1 }, { 0, 1, 0, 2, 1, 2, 1, 3 }, { 1, -1, 1, 0, 2, -1, 3, -1 } };
|
|
|
|
const std::vector<std::vector<int32_t>> P = { { 0, 1, 1, 0, 1, 1, 2, 1 }, { 0, 1, 0, 2, 1, 0, 1, 1 },
|
|
{ 1, 0, 1, 1, 2, 0, 2, 1 }, { 0, 1, 1, -1, 1, 0, 1, 1 }, { 0, 1, 1, 0, 1, 1, 1, 2 },
|
|
{ 1, -1, 1, 0, 2, -1, 2, 0 }, { 0, 1, 0, 2, 1, 1, 1, 2 }, { 0, 1, 1, 0, 1, 1, 2, 0 } };
|
|
|
|
const std::vector<std::vector<int32_t>> T = { { 0, 1, 0, 2, 1, 1, 2, 1 }, { 1, -2, 1, -1, 1, 0, 2, 0 },
|
|
{ 1, 0, 2, -1, 2, 0, 2, 1 }, { 1, 0, 1, 1, 1, 2, 2, 0 } };
|
|
|
|
const std::vector<std::vector<int32_t>> U = { { 0, 1, 0, 2, 1, 0, 1, 2 }, { 0, 1, 1, 1, 2, 0, 2, 1 },
|
|
{ 0, 2, 1, 0, 1, 1, 1, 2 }, { 0, 1, 1, 0, 2, 0, 2, 1 } };
|
|
|
|
const std::vector<std::vector<int32_t>> V = { { 1, 0, 2, 0, 2, 1, 2, 2 }, { 0, 1, 0, 2, 1, 0, 2, 0 },
|
|
{ 1, 0, 2, -2, 2, -1, 2, 0 }, { 0, 1, 0, 2, 1, 2, 2, 2 } };
|
|
|
|
const std::vector<std::vector<int32_t>> W = { { 1, 0, 1, 1, 2, 1, 2, 2 }, { 1, -1, 1, 0, 2, -2, 2, -1 },
|
|
{ 0, 1, 1, 1, 1, 2, 2, 2 }, { 0, 1, 1, -1, 1, 0, 2, -1 } };
|
|
|
|
const std::vector<std::vector<int32_t>> X = { { 1, -1, 1, 0, 1, 1, 2, 0 } };
|
|
|
|
const std::vector<std::vector<int32_t>> Y = { { 1, -2, 1, -1, 1, 0, 1, 1 }, { 1, -1, 1, 0, 2, 0, 3, 0 },
|
|
{ 0, 1, 0, 2, 0, 3, 1, 1 }, { 1, 0, 2, 0, 2, 1, 3, 0 }, { 0, 1, 0, 2, 0, 3, 1, 2 },
|
|
{ 1, 0, 1, 1, 2, 0, 3, 0 }, { 1, -1, 1, 0, 1, 1, 1, 2 }, { 1, 0, 2, -1, 2, 0, 3, 0 } };
|
|
|
|
const std::vector<std::vector<int32_t>> Z = { { 0, 1, 1, 0, 2, -1, 2, 0 }, { 1, 0, 1, 1, 1, 2, 2, 2 },
|
|
{ 0, 1, 1, 1, 2, 1, 2, 2 }, { 1, -2, 1, -1, 1, 0, 2, -2 } };
|
|
|
|
const int32_t blank_index = 12;
|
|
const int32_t nRows = 8;
|
|
const int32_t nCols = 8;
|
|
|
|
std::vector<std::vector<std::vector<int32_t>>> shapes = { F, I, L, N, P, T, U, V, W, X, Y, Z };
|
|
std::vector<char> symbols = { 'F', 'I', 'L', 'N', 'P', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '-' };
|
|
std::vector<std::vector<int32_t>> grid{nRows, std::vector<int32_t>(nCols, -1)};
|
|
std::vector<bool> placed(symbols.size() - 1, false);
|
|
|
|
std::random_device random;
|
|
std::mt19937 generator(random());
|
|
std::uniform_real_distribution<double> distribution(0.0F, 1.0F);
|
|
|
|
void display() {
|
|
for ( const std::vector<int32_t>& row : grid ) {
|
|
for ( const int32_t& index : row ) {
|
|
std::cout << symbols[index] << " ";
|
|
}
|
|
std::cout << std::endl;
|
|
}
|
|
}
|
|
|
|
void shuffle_shapes() {
|
|
uint64_t size = shapes.size();
|
|
while ( size > 1 ) {
|
|
int32_t random = static_cast<int32_t>( distribution(generator) * ( size-- ) );
|
|
|
|
const std::vector<std::vector<int32_t>> temp = shapes[random];
|
|
shapes[random] = shapes[size];
|
|
shapes[size] = temp;
|
|
|
|
const char temp_symbol = symbols[random];
|
|
symbols[random] = symbols[size];
|
|
symbols[size] = temp_symbol;
|
|
}
|
|
}
|
|
|
|
bool place_orientation(const std::vector<int32_t>& orientation,
|
|
const int32_t& row, const int32_t& col, const int32_t& shape_index) {
|
|
for ( uint64_t i = 0; i < orientation.size(); i += 2 ) {
|
|
int32_t x = col + orientation[i + 1];
|
|
int32_t y = row + orientation[i];
|
|
if ( x < 0 || x >= nCols || y < 0 || y >= nRows || grid[y][x] != -1 ) {
|
|
return false;
|
|
}
|
|
}
|
|
|
|
grid[row][col] = shape_index;
|
|
for ( uint64_t i = 0; i < orientation.size(); i += 2 ) {
|
|
grid[row + orientation[i]][col + orientation[i + 1]] = shape_index;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
void remove_orientation(const std::vector<int32_t>& oorientation, const int32_t& row, const int32_t& col) {
|
|
grid[row][col] = -1;
|
|
for ( uint64_t i = 0; i < oorientation.size(); i += 2 ) {
|
|
grid[row + oorientation[i]][col + oorientation[i + 1]] = -1;
|
|
}
|
|
}
|
|
|
|
bool solve(const int32_t& position, const uint64_t& number_placed) {
|
|
if ( number_placed == shapes.size() ) {
|
|
return true;
|
|
}
|
|
|
|
int32_t row = position / nCols;
|
|
int32_t col = position % nCols;
|
|
|
|
if ( grid[row][col] != -1 ) {
|
|
return solve(position + 1, number_placed);
|
|
}
|
|
|
|
for ( uint64_t i = 0; i < shapes.size(); ++i ) {
|
|
if ( ! placed[i] ) {
|
|
for ( const std::vector<int32_t>& orientation : shapes[i] ) {
|
|
if ( ! place_orientation(orientation, row, col, i) ) {
|
|
continue;
|
|
}
|
|
|
|
placed[i] = true;
|
|
|
|
if ( solve(position + 1, number_placed + 1) ) {
|
|
return true;
|
|
}
|
|
|
|
remove_orientation(orientation, row, col);
|
|
placed[i] = false;
|
|
}
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
int main() {
|
|
shuffle_shapes();
|
|
|
|
for ( int32_t i = 0; i < 4; ++i ) {
|
|
int32_t random_row, random_col;
|
|
do {
|
|
random_row = static_cast<int32_t>(distribution(generator) * nRows);
|
|
random_col = static_cast<int32_t>(distribution(generator) * nCols);
|
|
} while ( grid[random_row][random_col] == blank_index );
|
|
|
|
grid[random_row][random_col] = blank_index;
|
|
|
|
}
|
|
|
|
if ( solve(0, 0) ) {
|
|
display();
|
|
} else {
|
|
std::cout << "No solution found" << std::endl;
|
|
}
|
|
}
|