Pentomino tiling: Difference between revisions

=={{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>