A domino tiling of a grid is a tiling of the grid using domino pieces. Below is a C++ program to count the number of possible tilings of a grid of a given size.
The program constructs the board row by row, representing each row as a string. In each row, d
represents the top half of a domino pointing downwards, u
represent the bottom half of a domino pointing upwards, r
represents the left half of a domino pointing to the right, and l
represents the right half of a domino pointing to the left.
#include <iostream>
#include <vector>
#include <map>
using namespace std;
class DominoTilingCounter {
int height, width;
bool done;
int tilingCount;
map<string, vector<string>> dictionary;
vector<string> firstRow(int width) {
vector<string> prev;
prev.push_back("d");
prev.push_back("r");
for (int col = 1; col < width; col++) {
vector<string> next;
while (!prev.empty()) {
string candidate = prev.back();
prev.pop_back();
switch (candidate.back()) {
case 'd':
case 'l':
next.push_back(candidate + 'd');
if (col != width - 1)
next.push_back(candidate + 'r');
break;
case 'r':
next.push_back(candidate + 'l');
break;
}
}
prev = next;
}
return prev;
}
vector<string> nextRows(const string& row) {
if (dictionary.find(row) != dictionary.end())
return dictionary[row];
vector<string> prev;
if (row.front() == 'd')
prev.push_back("u");
else {
prev.push_back("d");
if(row.length() > 1)
prev.push_back("r");
}
for (int col = 1; col < row.length(); col++) {
vector<string> next;
while (!prev.empty()) {
string candidate = prev.back();
prev.pop_back();
switch (row[col]) {
case 'd':
if (candidate[col - 1] != 'r')
next.push_back(candidate + 'u');
break;
case 'u':
case 'r':
case 'l':
if (candidate[col - 1] == 'r')
next.push_back(candidate + 'l');
else {
next.push_back(candidate + 'd');
if (col != row.length() - 1)
next.push_back(candidate + 'r');
}
}
}
prev = next;
}
return prev;
}
int countTiling(int height, int width, const string& previousRow, int currentRow) {
if (currentRow == height) {
for (char cell : previousRow)
if (cell == 'd')
return 0;
return 1;
}
int count = 0;
vector<string> rows;
if (currentRow == 0)
rows = firstRow(width);
else
rows = nextRows(previousRow);
for (string row : rows)
count += countTiling(height, width, row, currentRow + 1);
return count;
}
public:
DominoTilingCounter(int height, int width) : height(height), width(width) {
if (height <= 0 || width <= 0 || height * width % 2) {
tilingCount = 0;
done = true;
}
}
int count() {
if (!done) {
tilingCount = countTiling(height, width, "", 0);
done = true;
}
return tilingCount;
}
};
int main() {
DominoTilingCounter tc(4, 7);
cout << tc.count() << endl;
return 0;
}