Finding Domino Tilings
Time limit2sMemory limit128 MB
Count the ways to tile a fixed 8x7 numeric grid with all 28 distinct dominoes so that each domino's pair matches the covered cell values.
- Level
Medium7 of 10
- Topics
- Backtracking, Bit manipulation, DFS, Combinatorics
- Solved
- No attempts yet
Problem
Each domino has size 1×2 and consists of two 1×1 cells. Each cell contains one number from 0 to 6. There are 28 possible dominoes in total, one for each unordered pair (0,0), (0,1), ..., (6,6); the pairs (a,b) and (b,a) are the same domino.
You are given an 8×7 grid whose cells also contain numbers from 0 to 6. Cover the whole grid using all 28 dominoes exactly once. The two numbers covered by a placed domino must match the two numbers on that domino.
Dominoes may be rotated. The same domino cannot be used more than once. Count how many different placements can make the given grid.
Input
The input consists of 8 lines. Each line is a string of length 7, and every character is a digit from 0 to 6.
Output
Print the number of different domino placements that can make the given grid.