Pentomino tiling: Difference between revisions
Content deleted Content added
Dialects of BASIC moved to the BASIC section. |
New post. |
||
Line 541:
U Y U T Z Z Z V
U U U T Z V V V</pre>
=={{header|C++}}==
<syntaxhighlight lang="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;
}
}
</syntaxhighlight>
{{ out }}
<pre>
Y Y Y Y X V V V
U Y U X X X - V
U U U T X W W V
I T T T W W F -
I L Z T W F F F
I L Z Z Z F P P
I L N N Z - P P
I L L N N N - P
</pre>
=={{header|Go}}==
|