Solution
Dominoes on the Full Chessboard
Show the problem again
In how many ways can a standard 8 × 8 chessboard be tiled by 32 dominoes, each covering two edge-adjacent squares? Tilings related by a rotation or reflection of the board count as different. Give the exact integer.
Worked solution
**Answer: 12,988,816.** A transfer-matrix count works column by column: record which cells of the next column are already occupied by horizontal dominoes poking in from the left (a 2^8-state profile), and fill each column with vertical dominoes and new horizontal ones. Running this dynamic program across 8 columns and requiring an empty profile at the end gives 12,988,816. The elegant route is Kasteleyn's theorem: the number of perfect matchings of a planar grid is a Pfaffian, which evaluates in closed form. For a 2m × 2n board, T = ∏_{j=1..m} ∏_{k=1..n} (4cos²(jπ/(2m+1)) + 4cos²(kπ/(2n+1))). With m = n = 4 the sixteen factors multiply to 12,988,816 = 2^4 × 17^2 × 53^2. (Sanity checks of the method: the same formula gives 2 for a 2 × 2 board, 36 for 4 × 4, and 6,728 for 6 × 6.)
Source: Computed independently by M. E. Fisher and H. N. V. Temperley (1961) and by P. W. Kasteleyn (1961). Statement written for AxiomIQ.