File Domino.h

↰ Parent directory (ADS/complexity)

The square tiling (DOMINO LIMITATO) of chapter 18: n x n squares to cover with copies of m oriented tiles, each split by its diagonals into four colored quarters, never rotated, the tile d = D[ 0 ] in the corner ( 0 , 0 ), and touching sides of the same color.

Definition (`ADS/complexity/Domino.h`)

Program Listing for File Domino.h

Detailed Description

The square ( i , j ) is the column i and the row j from the bottom left; a tile is left of the one in ( i + 1 , j ) and below the one in ( i , j + 1 ).

legalTiling() is the certificate, O( n^2 ); squareTiling() the enumeration by backtrack of the m^{n^2 - 1} coverings, pruned at the first wrong side. linearTiling() solves the linear tiling, a strip 1 x n, in polynomial time: by the reduction of the text, the tiles are the nodes of a graph with ( d_u , d_v ) when the right side of d_u has the color of the left side of d_v, and a strip is a walk of n - 1 edges from d, which exists if and only if a cycle is reachable from d or the longest path from d, in the acyclic part, has n - 1 edges; O( m^2 ) time.

The contracts [see File Contract.h]: a covering returned by squareTiling() is checked by legalTiling(); the certificate and the linear tiling accept any input. The operations are defined in Domino.tpp.