WorksComputer Science
Counting Square Tilings with a Fixed Set of Polyominoes Is #EXP-Complete
Abstract
An important question in counting complexity is whether exact counting can remain hard under restrictions that make feasibility easy. Tilings of squares by a fixed family of polyominoes provide a stringent test of this question, since tileability is polynomial-time decidable and the only varying input is a binary-encoded side length. We prove that there exists a fixed finite family of connected polyominoes for which counting translation-only square tilings is #EXP-complete under polynomial-time metric reductions, while the counting function belongs to #E. The resulting separation reveals that solution multiplicities can retain computational information that feasibility alone cannot capture. The proof develops a two-stage numerical isolation technique that combines a boundary-amplified Wang system with a rigid geometric compiler to recover accepting-computation counts while controlling all noncanonical tilings.
Introduction
Feasibility and exact counting can have sharply different computational complexity. This difference is particularly revealing for problems whose inputs leave little freedom to encode computation. Polyomino tilings provide a classical geometric setting for investigating this issue, since the choice of permitted pieces and the shape of the region offer two distinct sources of variation. Restricting these sources in turn brings into focus how much computational information can remain in the number of tilings even when feasibility is easy to determine.
Classical results illustrate how the representation of a tiling instance affects its complexity. Domino tilings admit efficient counting algorithms based on Pfaffian methods [8], while more general tiling problems exhibit substantial computational hardness [12]. Pak and Yang [16] proved that counting tilings of simply connected regions by a fixed finite family of rectangles is #P-complete. Thus, fixing the pieces still leaves the boundary of the input region available to encode computation. A stronger restriction is to require every region to be an ordinary square, leaving its side length as the only varying parameter.
For a fixed finite family of polyominoes, let be the number of tilings of the square using translations of pieces in . With given in binary, bits can describe a square containing cells. The central question is whether this restricted input can still yield a #EXP-complete counting function. This fixed-family square-counting problem was formulated by Pak [14 Conjecture 1.7]. Moreover, the tileability of an rectangle can be decided in time for every fixed family of tiles [14 Theorem 1.9]. The setting therefore offers a stringent test of whether solution counts can retain computational information beyond what feasibility reveals.
Our main theorem answers this question affirmatively. Here counts accepting paths of nondeterministic machines running in time on inputs of length , and denotes the subclass with time bound . Hardness is understood under polynomial-time metric reductions [10], which recover the source count by polynomial-time postprocessing of a target count given in binary.
Theorem 1.1 (Main theorem). There exists a fixed finite family of nonempty connected polyominoes such that counting translation-only tilings of the square, with given in binary, is -complete under polynomial-time metric reductions. The counting function belongs to .
The upper bound follows by canonically encoding a tiling and checking it in time exponential in the bit length of . The central challenge is hardness. The count for an unmodified square includes every tiling admitted by its fixed pieces, not just configurations representing an encoded computation. Recovering the desired accepting-path count therefore requires control over the aggregate contribution of all these configurations. The proof achieves this by numerical isolation, arranging for the intended computation histories to contribute a common multiplicative factor while the entire remaining contribution is smaller than that factor. Integer division then recovers the target count exactly. This principle is implemented at two successive levels.
The first level uses a fixed Wang-tile system to encode accepting computations. Local edge-matching rules have long been used to simulate computation [20, 4, 17], and fixed translationally invariant systems with binary-encoded dimensions provide related examples of computational hardness [6, 1]. A fixed-Wang-square counting result was also reported by Mennen and Pak [15]. In the present construction, a scanner reconstructs a machine’s initial configuration from the binary side length, and a Wang tableau records its accepting branches. A boundary amplifier gives the intended full-frame histories a dominant multiplicity, while a bound on all other boundary modes allows their contribution to be separated arithmetically. Crucially, the same construction bounds the number of open Wang tilings of any rectangle exponentially in its perimeter, providing the control needed by the geometric stage.
The second level realizes the Wang system using a fixed family of connected polyominoes. Geometric encodings of local matching rules provide a starting point [5, 13]; here the central issue is preserving exact counts over all geometric tilings. Each Wang tile is represented by a carrier whose interior cavity records its identity and whose interfaces encode matching data. Local rigidity aligns the carriers on a common macrogrid, and the open-interface structure partitions the grid into rectangles. This gives an exact decomposition of the polyomino tiling count into contributions from rectangular dissections. The single-block configuration carries the Wang count, whereas every nontrivial dissection loses interface-label multiplicity along its seams. Bounds on seam length, the number of dissections, and the Wang counts within their blocks together make the total noncanonical contribution strictly smaller than one unit after normalization. A second integer division therefore extracts the Wang count.
Composing the two numerical readouts gives the required polynomial-time metric reduction. More broadly, numerical isolation combines a dominant term encoding accepting computations with global combinatorial bounds on the remaining configurations. Together with rigid geometric compilation, this provides a route to exact counting hardness in other succinctly specified systems with fixed local rules.
Preliminaries
The tiling conventions, counting complexity classes, metric reductions, and machine notation are specified below.
All regions are subsets of ; a finite set is 4-connected if its grid-adjacency graph is connected.
Let denote the canonical binary representation of , with . For , write , with . Rectangles of positive width and height are denoted by .
If , a -tiling of a finite region is a finite set of placements whose translates are pairwise disjoint and have union . Only translations are allowed. The empty region has one empty tiling.
A Wang system is a finite set of labelled tile types, each carrying north, east, south, and west colours. Distinct tile types are allowed to carry the same four colours. An open Wang tiling of a finite rectangle assigns a tile type to each cell, matches colours on internal edges, and imposes no condition on colours exposed along the geometric boundary. This type-level convention is important in § 7, where the geometric compiler preserves tile identity even when four edge colours coincide.
The class is used in its standard complexity-theoretic sense: it consists of total functions equal to the number of accepting paths of a nondeterministic Turing machine that halts within steps for some polynomial . Likewise, denotes nondeterministic time . The linear-exponential counting subclass is denoted by . All counting functions in this paper are total: malformed or noncanonical binary strings receive value zero.
Proposition 2.1 (Fixed-family square counts lie in ). For every fixed finite family of finite polyominoes, the function belongs to .
Proof. Let . A tiling of has at most placements. Encode the placements in a canonical lexicographic order, recording for each one its fixed tile type and its anchor coordinates. Because is fixed, the resulting witness has bits, which is . A deterministic verifier checks containment, pairwise consistency, and exact coverage in time polynomial in this witness length. The canonical ordering gives one accepting witness per tiling. Since , both witness generation and verification take time.
A polynomial-time metric reduction from to is a pair of polynomial-time functions and satisfying for every , where the integer argument of is given in binary. Thus the running time of is measured in . This is Krentel’s metric-reduction model [10]. For a counting function , write for its support language.
For a one-tape machine with tape alphabet , state set , and sentinel symbol , a cell is either or . A legal extended configuration of height is a word on indices with sentinel cells at , exactly one head cell at an index in , and plain cells elsewhere. A labelled arrow is a tuple , with ; an arrow is inapplicable if its requested move would enter a sentinel. Distinct labelled arrows count as distinct computation branches even when they induce the same tape update.
Proof strategy
The hardness proof proceeds through two numerical readouts. The first uses a fixed nondeterministic machine whose accepting-path count is -complete. A polynomial-time map encodes $x as a positive binary side length . The Wang construction of § 4–§ 5 has a total open-square tiling count . For all sufficiently large encoded side lengths, its full boundary class contributes a fixed multiple of , while the other boundary classes contribute a remainder satisfying
The full boundary frame has independently labelled sites. Every proper boundary mode has fewer such sites, and the number of compatible tableaux can be controlled by a perimeter-scale bound. Division by therefore retrieves the accepting-path count, with the finitely many exceptional inputs handled by a fixed table.
The second readout is geometric. § 7 represents the fixed Wang system by connected polyominoes with a constant macrocell pitch and possible labels on each open interface. The total number of macrogrid adjacencies gives the canonical one-block contribution . All other geometric tilings are classified by rectangular partitions, whose seams reduce the number of available labels. Denoting their aggregate contribution by , the geometric counting identity yields
This second inequality follows from a lower bound on seam length, an exponential bound on the number of rectangular partitions, and the perimeter bound for open Wang rectangles. The exact geometric interfaces are defined in § 7, where Figure 2 and Figure 3 accompany their respective counting arguments.
Figure 2. A connected carrier and the geometry of a matching interface. The interior cavity records the identity of the simulated Wang tile. A fixed and a variable dent–bump pair encode the state of an open interface. Matching addresses force agreement of the adjacent local data.
Figure 3. One-block and nontrivial rectangular decompositions of the macrogrid. Each closed adjacency on an internal seam removes one independent interface-label choice. The canonical one-block term therefore has the maximum interface multiplicity, while other decompositions are bounded by their seam length.
Together, these identities describe how the accepting-path count is encoded first in the open Wang-square count and then in the translation-only polyomino-square count. The first numerical readout separates the intended computation histories from other Wang boundary modes, while the second separates the canonical one-block contribution from all other polyomino tilings. Applied in reverse order, the two floor divisions recover the original accepting-path count. § 8 and § 9 establish the bit-complexity bounds required for the resulting metric reductions.
Encoding an Exponential-Time Counting Computation
The hardness reduction begins with a fixed counting machine whose initial configuration can be reconstructed from the square’s side length. Parsimonious simulation and polynomial padding provide a universal accepting-path counter. A self-delimiting encoding then places its input in the binary side length; the final bounds ensure that the encoded computation can be recovered and completed within the available tableau.
Theorem 3.1 (Computation encoded by the side length). There are a fixed one-head nondeterministic Turing machine , a counting function that is -complete under parsimonious reductions, and a polynomial-time injective map with the following property. Let be the number of accepting length- branches of from the initial configuration determined by the binary digits of . Then, for every ,
On encoded side lengths , the parser, input preparation, and simulation reach an accepting or rejecting stay-sink within steps. Both stay-sinks have unique continuations.
Proof. We first normalize an arbitrary #EXP counting machine without changing its path count. Let the source machine be fixed and suppose that, on inputs of length , every branch halts within steps for a polynomial . Enlarging if necessary, assume . A finite transition list is encoded self-delimitingly by unary indices for states and letters and fixed unary codes for the three head movements. The decoding procedure is deterministic and polynomial in the code length.
For later use, suppose a source pair has at most outgoing arrows. Its choice can be replaced by a complete binary tree of depth
Leaves representing unused choices enter a rejecting sink. Accepting and rejecting sinks each have one stay-arrow on every tape letter. A selected original arrow determines one tree path, so the conversion is bijective on labelled computation paths.
For a machine with tapes, store all tapes in one contiguous block, recording a letter and a head bit for each simulated tape. After steps the block length is at most . A scan, rewrite, and head-bit update costs at most . Summation for gives
for a constant depending only on the fixed source machine, after enlarging it to cover finitely many small inputs. Applying the binary-tree replacement above to each nondeterministic choice has constant depth, so the fully converted one-tape binary machine halts within steps for some polynomial depending only on the source machine. All work inserted between nondeterministic choices is deterministic, so the path count is unchanged.
The fixed machine parses strings of the form
where the unary block is padding. It converts the decoded transition list once and simulates the resulting binary machine on for exactly simulated steps, where is the total input length. Missing transitions have already been redirected to the rejecting sink, and after the simulated-step budget any branch that has not reached a stay-sink is sent deterministically to the rejecting stay-sink. A simulated tape block has length at most , so one simulated step costs at most for . Including parsing, the running time is at most . The inequality is checked directly for ; for , . Set . Thus reaches a stay-sink within steps.
Let count the paths in the accepting sink at that time. A binary clock of bits makes a genuinely halting simulator. Its tape length is at most ; hence its running time is at most
For hardness, let and apply the preceding conversions to a fixed machine computing . Let be its transition code before the binary-tree conversion, and let be a polynomial such that the converted machine halts within steps on every input of length . Choose a fixed constant large enough to cover the delimiters and code, and define the parsimonious source map
Its output length is polynomial in and satisfies . Hence the -step universal simulation outlasts every converted computation. Once the simulated machine reaches an accepting or rejecting stay-sink, the continuation is unique, so accepting paths are preserved bijectively. Thus for every , and is #EXP-complete under parsimonious polynomial-time reductions. Notice that itself is computable by a nondeterministic machine in linear-exponential time; the polynomial padding in is what allows hardness for the full standard #EXP class.
Moreover, if , the function counting accepting paths of a nondeterministic -time machine deciding belongs to #EXP and has support exactly . Parsimonious completeness therefore implies that the support language is NEXP-hard.
For , define the self-delimiting word and its numerical value by
Its length is . Reading from the least significant end, count the terminal zero run, cross its following separator 1, and count the next zero run of length . The next separator 1 is then checked and skipped before reading the preceding bits as ; the remaining leading bit must be 1, with no further bits. Checking that the first run has length recovers uniquely. The procedure scans only polynomially many bits and proves injectivity and polynomial-time decodability.
Since ,
Writing , we have , and therefore
Also , giving . Binary branching further gives .
We next define . Its alphabet contains that of , the sentinel #s, delimiters markL, markR, and finitely many parser letters. At its start pair it has exactly two arrows. The null arrow enters the accepting stay-sink. The real arrow enters a deterministic parser.
Write for the initial configuration specified by the binary digits of . On , the sentinels occupy . The head is at index 1, on the least significant bit. For , index stores one if the -th bit of is one, zero if it is zero below the leading bit, and work above the leading bit. The inequalities (for ) and show that the two omitted high bits are zero and that the leading bit remains inside the sentinel interval. At , the omitted bit at position 2 is one.
The parser reads terminal zeros, the two separators, and the candidate , and checks . It then inspects the cell immediately north of the recovered leading one. A work accepts the high-zero continuation; a bit letter or sentinel rejects. Thus a successful parse occurs exactly when .
After a successful parse, the machine writes markL, then blanks, a copy of , another blanks, and markR. It restores parser scratch and starts on the copied bit letters. The head cannot reach either mark during steps. The copy remains between the sentinels because
The parser takes at most steps, the copy at most , and the simulation at most . For , the first term is at most , the second at most , and the third at most . Hence the real computation enters a sink by time . No transition enters a sentinel, and the remaining steps are uniquely supplied by the appropriate stay-sink.
The null branch contributes one accepting path for every . On a coded side, real accepting branches are in bijection with accepting paths of ; off-code, the parser enters the rejecting sink. This proves the branch-count formula and all remaining assertions.
Counting Paths with Wang Tile Tableaux
Each step of the size-encoded machine is represented by one column of Wang tiles. The local rules record the unique head and its labelled transition, yielding a bijection between accepting branches and tableaux with prescribed boundaries. A separate count of successor columns under arbitrary boundary data provides the perimeter estimate needed in the geometric construction.
Let be a finite one-tape machine with state set , tape alphabet , accepting state , sentinel , and labelled-arrow set . Put
Theorem 4.1 (Wang tableau for counting computation paths). For every fixed one-head Turing machine , there exists a finite Wang system with the following properties. For any legal initial configuration of height and any time horizon , accepting labelled-arrow branches of length correspond bijectively to -tilings of a -by- rectangle with prescribed initial, accepting, and sentinel boundary data. Distinct labelled arrows yield distinct tableaux.
Furthermore, writing for the number of possible tape-cell symbols and for the number of labelled arrows, a prescribed east-boundary colour word of height has at most vertically matching successor columns. The number of open -square tableaux therefore satisfies
Proof. For an old radius-one word , define its local update under an applicable arrow when , the two neighbours are tape cells, and a left or right movement does not enter a sentinel. The updated triple is
where and . For a window whose head is immediately south or north of its centre, let and perform the corresponding incoming-head update at the centre.
Horizontal colours are symbols for . A candidate tile carries two order-bit chains, one for the old word and one for the new word. Write their south/north values as and , both in . For the old chain we require when the old centre is not a head and when it is a head; the new chain satisfies the analogous rule with the new centre. Thus each chain is nondecreasing and can jump only once, at its unique head. Vertical colours have the form , where both 's are pairs of cell symbols, are the old- and new-chain values on that horizontal boundary, and . The south colour stores , and the north colour stores .
A candidate tile contains old and new triples , these four order bits, and south and north tokens. It is admitted in exactly one of four cases. H. The old centre is a head. The south token is , the north token is an applicable arrow , and .
A. The old south neighbour is the head. The south token is , the north token is , and the new centre is .
B. The old north neighbour is the head. Both tokens are , and the new centre equals for at least one arrow having the source displayed by that head. This is an existence condition on the tile datum: if several labelled arrows witness the same resulting datum , they do not create duplicate tile types in Case B.
Q. The old triple has no head. Both tokens are , and the new centre equals the old centre.
Both triples are required to contain at most one head. The east and west colours are and . The south vertical colour stores the two southern old and new symbols, the lower order bits, and the south token; the north colour stores the two northern symbols, the upper bits, and the north token. The inventory is finite and has the asserted cardinality. For the conditioned tableau used in the bijection, choose the south sentinel colour with both reconstructed symbol pairs equal to sentinels, both order-chain values equal to zero, and empty token; choose the north sentinel colour analogously with both order-chain values equal to one and empty token.
Vertical matching overlaps consecutive symbol pairs and identifies the corresponding boundary bits. Hence a matching column reconstructs unique extended old and new words on indices , together with one old order chain and one new order chain. Each chain is constant except for a possible 0-to-1 jump at a head centre, so it certifies at most one head. When its prescribed south boundary value is zero and north boundary value is one, it certifies exactly one head. Sentinel vertical colours additionally force the two bottom and two top symbols to be plain(#s), so every certified head lies strictly between them.
At the unique old head, Case H chooses one arrow and places its label on the north edge. Vertical matching passes that token to the Case A tile. The overlap with simultaneously fixes the Case B centre for the same arrow. Every window at distance at least two is Case Q and preserves its centre. Thus the old word and the one arrow determine the entire visible new word. This proves that the neighbouring windows make no independent choice. Because the token is the labelled arrow itself, two same-effect arrows give different vertical colours.
Time runs from east to west. Fixing the east boundary to the radius-one windows of determines the first old word. Horizontal matching identifies each column’s new word with the next column’s old word. The sentinel colours make every word a legal configuration, and the accepting west-colour set requires the final unique head to have state . Conversely, a branch determines all triples, bits, and tokens and hence one tiling. These constructions are inverse.
For the open-column bound, fix its old-word triples. A column is encoded injectively by the two south-boundary order bits (one for each chain), the four new endpoint and ghost symbols, and four token slots containing the exterior tokens and the possible visible-head token. The old word together with its chosen south-boundary bit fixes the old order chain. Cases H–Q, the new south-boundary bit, and the recorded endpoint data recover the new word, its order chain, and every token. Therefore the number of columns is at most . The east boundary of an open -square has at most words. Scanning columns westward gives
Lemma 4.2 records the complete boundary-data reconstruction behind this estimate. The identity condition in Case Q is essential for the perimeter bound: without equality of old and new centres, a zero-head column would have exponentially many successor words, and iteration would give an area-exponential rather than perimeter-exponential bound. Finally, is undefined for a move onto a sentinel, which proves sentinel consistency.
Lemma 4.2 (Reconstruction of open successor columns). Fix the east-colour word of a vertically matching column in the Wang tableau constructed above. Such a column is uniquely determined by at most two initial order bits, four new endpoint or ghost symbols, and four arrow-token slots. In particular, its number of possible completions is at most , independently of the column height.
Proof. The east colours determine all old radius-one windows. Their overlaps fix the old symbols throughout the column and the old endpoint data that they expose. Each vertically matched order-bit chain is nondecreasing, and its only permitted change is the transition from 0 to 1 at a head centre. Hence the old chain is fixed by its south bit and its old symbols. The new chain is similarly fixed once its south bit and the new symbols have been recovered.
The reconstruction of the new centres is local except at the old head, whose uniqueness follows from the old order chain. All possible arrangements are covered by the following cases. If an old head is strictly inside the visible column, Case H fixes its outgoing labelled arrow by the recorded head token; the neighbouring Case A and Case B rules implement the unique resulting update, while Case Q leaves all more distant centres unchanged. If a head touches the first or last visible radius-one window, its possible influence is confined to the boundary row and is recorded in the endpoint or ghost symbols and exterior token slots. If no old head is visible, Case Q fixes every centre whose old window is free of a head; only those bounded boundary windows that may involve an exterior head require the recorded boundary symbols. In every case, there is no independent choice at each additional interior row.
The overlap constraints then recover the new radius-one windows, the vertical colour data, and the order chains. The arrow token at a visible head records the actual labelled transition, so distinct same-effect arrows are counted separately. Conversely, in Case B, different arrow witnesses giving an identical local tile datum are identified as a single tile type. Thus two completing columns with the same prescribed east word and the same bounded boundary data coincide tile by tile. There are at most choices for the two initial order bits, choices for the four endpoint and ghost symbols, and choices for the token slots, proving the bound.
Counting Open-Square Wang Tilings
The tableau correspondence in the preceding section uses prescribed boundary data, while the target counting problem has open boundaries. A side-activity amplifier assigns a dominant multiplicity to the intended boundary class. Coupling it to a ripple counter and an edge scanner recovers the initial configuration from the side length, and the same construction supplies a uniform bound for all remaining boundary classes. The resulting perimeter estimate for arbitrary rectangles will be used in the geometric compiler.
Theorem 5.1 (Boundary amplification). For every integer , there is a fixed Wang system with four side-activity tracks such that, on an open -square for , the all-active boundary class has exactly tilings and each proper side-activity class has at most tilings. A private-colour dummy tile can be adjoined, contributing exactly one additional tiling.
Proof. Choose pairwise distinct atomic labels
and , , , for . Horizontal colours are distinct symbols ; vertical colours are distinct symbols .
A tile carries booleans and indices . Adjacent active sides on the same tile must use one common . Its colours are
where
Inactive indices do not occur in any colour and are normalized to 1.
No east colour contains in its first coordinate. Hence a -active tile can occur only on the geometric west side. The three symmetric assertions follow for . Along the west side, the north and south colours carry either or ; since these differ, activity is constant down the whole side. The other three chain coordinates give the same all-or-none conclusion.
For , let be the active-side set and write its indicator bits as . The number of distinct active sites is . According to the active sides, this takes one of the six values , , , , , and . A choice of one at each such site determines a unique tiling. Horizontal matching follows because an internal left tile is not -active, an internal right tile is not -active, and the north and south chain coordinates agree along their rows. Vertical matching is symmetric. Conversely, dead colours expose every . Hence the side class has exactly tilings. Summation over the sixteen subsets gives the displayed formula.
When , the single tile lies on all four sides. The activity inventories contribute , , , , , and for zero sides, one side, adjacent pairs, opposite pairs, triples, and all four sides, respectively. Their sum is .
The west-only set contains the inactive tile and the purely west-active tiles. It has one constant inactive tiling and active-west tilings. Finally, a private-colour tile cannot meet an amplifier tile. Connectedness of the square grid therefore makes its mode constant and adds exactly one tiling.
A raw product of four independent wires would give full frames. The shared- rule removes one duplicate index at each corner and gives the required .
We use a four-tile ripple counter. Its tile indexed by input bit and carry has west colour , south colour , east colour , and north colour . West and south boundary words determine a unique tiling. With west bits zero and south carries one, column represents , the east boundary represents the side length, and the top carries are zero.
Theorem 5.2 (Fixed open-square Wang counter). There are a fixed unweighted Wang tile set and positive constants and such that, for every , the total number of open -tilings of the -square has the decomposition
where the residual count satisfies
Proof. Apply Theorem 4.1 to . Its tableau track contributes at most open -square patterns. The ripple track contributes .
We define the scanner in full. Let
Its vertical colours are
so . There is one idle tile with private colour scanIdle on every side. For every , there is a marked tile with west colour scanIdle, east colour scanDead, south colour , and north colour . No west colour equals scanDead. Thus marked tiles occur only in the east column. Vertical colours prevent a marked tile from meeting an idle tile vertically, so either the scanner is entirely idle or its east column is entirely marked. Its open count satisfies . The uncoupled counter, tableau, and scanner product therefore has at most open tilings.
For and a mode , define
Write and . The relation first requires , and then exactly one of the following clauses.
Bot.
Mid.
PreTop.
Top.
No clause has south phase cap, and no clause has north phase bot. Define . The lookahead and mode are scanner-colour coordinates, not amplifier activity bits.
Take the product of the amplifier at , the ripple counter, the tableau, and the scanner. Retain a product tile only when the following cell-local couplings hold.
A west-active amplifier cell has ripple west colour , an accepting tableau west colour, and an idle scanner.
An east-active cell has a marked scanner tile, reads its ripple east bit , satisfies , and has tableau east colour .
A south-active cell has ripple south colour and tableau south sentinel colour. At the southeast corner its scanner south colour is .
A north-active cell has ripple north colour C and tableau north sentinel colour. At the northeast corner its scanner south colour has phase top, centre plain(#s), lookahead lh1, and mode modeHigh.
Every non-east-active cell uses the idle scanner.
Adjoin a single all-private-colour dummy tile. Figure 1 summarizes the boundary data in the full-frame class and the role of the unique marked scanner column.
Figure 1. Full-frame boundary coupling and east-edge scanning at the Wang level. In panel (a), the west, south, and north sides carry the fixed ripple/tableau data , , , , and , , respectively. The dots mark the shared-corner amplifier -sites, and the shaded east column receives the ripple bits . Time in the one-head tableau runs from east to west. Panel (b) isolates one scanner step: adjacent scanner states , , together with , satisfy LegalScan and determine Emit, which is exported as the tableau east colour. Over the full marked column, these emitted colours are exactly the radius-one windows of .
In a full frame, the amplifier forces all four active sides. The ripple boundary conditions give the unique incrementing counter and put the bits of on the east edge. The scanner diode confines marked tiles to that edge. The bottom constraint forces Bot at row zero. The top constraint forces Top at row ; since no legal tile has south phase cap, no earlier Top is possible. Row is therefore PreTop. Its required bit is zero because the omitted bit vanishes for . All intervening rows are Mid.
For , the -th binary digit of is , with the least significant digit at . The mode is now unique by downward recursion. At height ,
This follows directly from ModeOut, starting with the high mode at the top. Therefore a zero above the leading one is emitted as workb, a lower zero as zerob, and a one as oneb. Bot installs the start head at index 1, while PreTop and Top install the two sentinels. PreTop explicitly checks the omitted bit ; the ripple word already supplies the second omitted bit , so Top does not read it. The overlap equation gives
The tableau bijection of Theorem 4.1 then identifies its tilings with accepting branches of . Independently, the amplifier supplies one per one of its boundary sites. This proves the full-frame bijection.
For a proper side set, Theorem 5.1 gives at most amplifier tilings. Dropping every coupling permits at most computational-track tilings, including every open scanner, counter, and tableau defect. Thus each proper class has at most tilings. The private dummy colour cannot meet a product colour on the connected square grid, so it contributes one isolated tiling. Summing the fifteen proper classes proves the junk estimate.
Theorem 5.3 (Perimeter bound on arbitrary rectangles). Let count open -tilings of . There is a fixed integer such that
One may take
The bound also applies when or .
Proof. The dummy colour again gives one isolated constant tiling. Dropping all couplings bounds every other tiling by the product of four independent track counts.
The ripple track is determined by west bits and south carries, so it has exactly tilings. For the tableau track, there are east words and at most westward column extensions. Since ,
The scanner is either idle or has one marked east column, giving . For the amplifier, dead colours and chain colours still force an all-or-none subset of the four geometric sides. Charge one independent for every active side cell before imposing shared-corner equalities. A chosen side set therefore has at most tilings, and summing sixteen sets gives . This charging remains valid when opposite sides occupy the same physical row or column. In particular, for , west and east indices may remain independent; for , the exact inventory is below .
Multiplying the four bounds and absorbing the factor 16 into the exponent yields
Rectangular Decompositions of the Macrogrid
Closed interfaces in the geometric realization may divide the macrogrid into several components. The analysis requires two combinatorial facts: every nontrivial rectangular dissection has a sufficiently long seam and a controlled number of possible seam configurations, and the saturation condition enforced by the carrier interfaces makes each connected component a filled rectangle. Together, these facts classify the resulting tilings and control the multiplicity of nontrivial decompositions.
Theorem 6.1 (Rectangular-dissection bound). Let a rectangular dissection of be a partition into at least two nonempty discrete rectangles. A seam pair is a pair of adjacent cells in different blocks, and its seam segment is their common unit side. Form the seam graph whose vertices are
seam segments and whose edges join segments sharing an endpoint. If is the number of seam pairs, then:
;
every connected component of the seam graph contains at least segments;
for fixed , the number of rectangular dissections with seam pairs is at most .
Proof. Every internal side of a rectangular block consists of seam segments, and every seam segment lies on an internal side of both adjacent blocks.
Let be the number of blocks meeting column , and the number meeting row . Each column is partitioned into intervals, while each row is partitioned into intervals. Hence
If every , the first sum is at least . Otherwise some block contains a whole column. Such a rectangular block has height ; unless it is the entire square, one of its vertical sides is internal and contributes seams. The entire-square case is excluded by nontriviality. This proves .
Consider the internal sides of one block in cyclic order. Adjacent internal sides share a corner and therefore belong to the same seam component. If its internal sides do not all lie in one component, then it has either one internal side or two opposite internal sides. In either case every such side has length . Thus each block satisfies the dichotomy:
every internal side has length , or all its internal sides lie in one seam component.
Suppose a seam component has fewer than segments. Any block incident with must satisfy the second alternative and hence has all internal sides in . A neighbouring block is incident along one of these sides and has the same property. The adjacency graph of blocks is connected, since a row-then-column cell path between two blocks crosses a sequence of neighbouring blocks. Therefore every block is incident with , and every seam belongs to . This would give , a contradiction.
A dissection is determined by its seam set: delete the seam adjacencies from the cell grid, and the connected components are precisely its rectangular blocks. It remains to count possible seam sets.
Let be the connected sets of unit grid segments with endpoints in . Double every edge of such a set. The resulting connected even-degree multigraph has an Euler tour of length . An initial endpoint and the sequence of four possible unit steps determine the segment set, giving . The elementary inequality holds for all .
An admissible seam set with segments is a disjoint union of connected components of sizes , where each and . Thus . For each ordered size tuple, . The number of ordered positive compositions, allowing every , is at most : for fixed , partial sums give at most choices, and there are at most choices of . Consequently, there are at most admissible seam sets, and hence at most this many dissections.
We next isolate the local graph principle used by the geometric compiler. Fix and , and write . Define
Let
For a tiling , open the macro-edge between two adjacent macrocells when one placement contains adjacent physical cells on its two sides. This gives a spanning subgraph of the -square index grid.
A grid subgraph is saturated when, in every 2-by-2 index square, two consecutive present edges force all four edges.
Theorem 6.2 (Saturation and rectangular macroblocks). The following assertions hold.
Every connected component of a saturated index graph is a filled combinatorial rectangle: all internal horizontal and vertical index adjacencies of the rectangle are present.
The macrocells are nonempty, pairwise disjoint, and partition .
If every prototile is 4-connected, then the macrocells met by one placement lie in a single component of .
If is saturated, its components induce a partition of the physical square into nonempty discrete rectangles. If there is more than one component, this is a rectangular dissection. No closed macro-adjacency lies inside one component.
Let be the maximum -diameter of a prototile. If saturation fails in a 2-by-2 macro-window , every placement meeting the window is contained in its -neighbourhood of radius . Those placements determine the four offending edge bits, and has width and height at most
Proof. Let be a connected component of a saturated index graph. Choose a filled combinatorial rectangle
of maximum cardinality. Suppose an edge of leaves its north side at . Let be the set of for which the vertical edge from to is present. If and , the vertical edge at and the filled horizontal edge below it are consecutive sides of a 2-by-2 square. Saturation supplies the upper horizontal edge and the vertical edge at . The symmetric argument propagates left. Hence , and the full added row is filled. This contradicts maximality. Coordinate swaps and reflections treat the other three sides. Therefore .
The sequence is strictly increasing. Its endpoint increments are , its interior increments are , and when its sole increment is . The induced coordinate intervals therefore partition , proving the macrocell assertion.
Let a 4-connected placement meet two macrocells. A cell path inside the placement crosses between either the same macrocell or two adjacent macrocells. Every genuine crossing witnesses an open macro-edge. The visited index cells thus form a walk in , proving containment in one component.
Under saturation, each component is a filled index rectangle. The union of its consecutive coordinate intervals is , a nonempty discrete rectangle. Components partition the index grid, so these unions partition the physical square. Filledness says every internal adjacency is open; conversely a closed adjacency separates components.
Finally, if a placement meets , every one of its cells lies within -distance of the meeting cell. It is therefore contained in . A macrocell side length is at most , so the two-by-two window has width and height at most twice that quantity; thickening adds . The placements meeting the window contain every possible witness for its four open bits, so they determine the saturation failure.
The Polyomino Construction
The fixed Wang system is realized geometrically by a family of connected polyominoes. Each carrier stores the Wang tile identity in an interior cavity and encodes its edge colours and opening data in boundary registers. The proof establishes unique macrogrid anchoring and an exact correspondence between tilings and rectangular Wang-tiled blocks. The dissection estimates then isolate the contribution of the single-block configuration.
Let , , and for write for its west, east, south, and north colours. Let be its horizontal and vertical colour sets, of cardinalities and . Fix bijections
Define
For , a horizontal colour , and , put
and define analogously using . Every code lies in , strictly below , and the four arguments are recovered from it.
Let
For an opening vector , let whenever . Starting with , delete . On each open side also perform the following dent-and-bump operation:
| side | dent | bump |
Table 1.
Denote the resulting support by , and let consist of and every such carrier. Figure 2 shows the tile-specific cavity and the reciprocal interface registers.
Lemma 7.1 (Local geometric rigidity). Every carrier satisfies the following two properties.
In any relative row or column of the body square , no three consecutive body cells are all absent from the carrier.
Relative rows and columns 1 and 2, and each three-by-three corner of , are intact.
Proof. The interior cavity is contained in a two-by-two box and removes at most two consecutive cells from any row or column. Every side dent removes a single boundary cell. On any fixed body row, boundary dents can occur only at the two extreme columns; on any fixed body column, they can occur only at the two extreme rows. The variable dent coordinates lie in , the fixed coordinate is , and the cavity lies in the strip . If a boundary dent shares a row or column with the cavity, at least fifteen occupied body cells separate them. Hence neither the cavity nor any combination of boundary dents creates three consecutive missing body cells. The same coordinate separations place every cavity and dent away from relative rows and columns 1, 2 and away from all three-by-three body corners.
For , let denote the set of rectangular partitions of the index square , including the one-block partition. For , let be its number of seam adjacencies, and for a block let denote its width and height.
Theorem 7.2 (Geometric compilation and counting identity). The fixed translation-only family has the following properties.
Every carrier is 4-connected, has area , lies in , and the map is injective on unlabelled supports. The plug is 4-connected of area 3.
For every , every -tiling of has exactly one carrier anchored at each , .
Adjacent anchored carriers are disjoint exactly when their reciprocal opening bits agree and, whenever the common opening bit is one, the corresponding perpendicular opening bits, Wang colours, and amplifier labels also agree. Diagonal carriers are disjoint, and outer opening bits vanish.
For every , after the anchored carriers are placed, the residual set is the disjoint union of the translated cavities. Each cavity has one plug placement, and no additional carrier fits.
For every , tilings of are in bijection with a partition , an open -tiling of every block, and one label in on every open macro-edge.
Let . Then
For this equals . For , the nontrivial-partition contribution satisfies
and consequently
Proof. The coding maps are injective because their residues modulo four recover the two perpendicular bits, while quotient and remainder by recover the colour and label. The cavity lies in the interior strip , far from every edge feature. Each open side deletes one cell and adds one cell, so a carrier has area .
First delete the entire two-by-two box containing the cavity from the inner rectangle ; the remainder is 4-connected. Reinsert the southwest cell of that box, which is the unique cell of the box not removed by the L-shaped cavity. It is adjacent to the surrounding remainder and therefore preserves 4-connectivity. Every undeleted boundary cell attaches inward. Each bump attaches to an undeleted boundary cell because all variable code positions lie below . Hence every carrier is 4-connected.
The cell uniquely minimizes in every carrier. Equality up to translation therefore forces equal origins. The presence or absence of the four side features recovers , the interior cavity recovers , and on every open side the variable address—carried by the dent on the west and south sides and by the bump on the east and north sides—recovers its label. This proves injectivity. It also proves the identity test for equal-colour Wang tiles.
We establish anchoring by row-major induction, increasing first and, within a fixed macro-row , increasing . The repeated rigidity input is Lemma 7.1: an anchored carrier cannot expose three consecutive body cells in one row or column, and the first two body rows and columns and all three-by-three body corners are intact.
Let be the next macro-corner. A translate of covering has origin , , or . At the outer boundary one of its cells leaves the square. Otherwise it overlaps the intact cell of the lower carrier, the intact cell of the left carrier, or an intact corner cell. Hence the placement covering is a carrier.
Write its origin as . The intact body corners and containment in imply . Because the carrier covers and its relative support is contained in , its origin satisfies
If , then and the new carrier’s intact relative row lies inside the already anchored macro-row . By the horizontal-origin bounds, its length- body interval meets at least one anchored macrocell of that row in three consecutive positions. Those three positions are occupied by the new carrier, while the no-three-gap property prevents the anchored carrier from omitting all three; hence the two placements overlap. If , again . The intact cells with relative coordinates of the new carrier lie on the top row of the carrier directly below. On that top row the only possible boundary omission is the single north dent, and the corner cells are intact, so at least one of these three cells is already occupied. Both cases are impossible.
If , the corner must be the south bump, so . For , the body leaves the square. For , its body overlaps the left carrier throughout
In particular, belongs to both carriers: it is outside both cavities and all possible dents. Thus . With fixed, if then necessarily , and the new carrier’s intact relative column 1 meets the already anchored carrier immediately to the left in at least three consecutive vertical body positions. The no-three-gap property forces an overlap. If , the new carrier’s intact southwest corner overlaps the left carrier’s intact southeast corner. Finally, if , covering would require a relative cell with first coordinate at height zero, whereas the only such cell is the west bump at height . Hence , and therefore . Induction anchors exactly one carrier at every macro-origin. Table 1 records the exhaustive alternatives and their overlap certificates.
| Placement covering | Exclusion or surviving case |
| Plug at | Crosses the lower boundary or overlaps the intact lower carrier. |
| Plug at | Crosses the left boundary or overlaps the intact left carrier. |
| Plug at | Crosses the boundary or overlaps an intact previously occupied corner. |
| Carrier with | Its intact body row 1 forces three consecutive occupied cells in the preceding macro-row, contradicting the no-three-gap property. |
| Carrier with | Three intact south body cells meet the occupied top row below, where at most one north dent is absent. |
| Carrier with | This requires the south bump at . It crosses the boundary if ; otherwise it overlaps at . |
| Carrier with , | Its intact body column 1 overlaps the anchored macro-column to the left in three consecutive cells. |
| Carrier with , | The new southwest corner overlaps the left carrier’s intact southeast corner. |
| Carrier with , | Covering would require a cell at relative coordinate , whereas the only west bump is at height . |
| Carrier at | The unique surviving anchored position. |
Table 1 (PDF p. 19). Exhaustive alternatives at the next row-major macro-corner . Here denotes the origin of a carrier that covers . Each rejected placement either crosses the physical boundary or overlaps a previously anchored carrier.
Consider two horizontal neighbours. If the left east bit and right west bit differ, the existing bump overlaps an undeleted body cell of the neighbour. Hence they agree. If both are open, the left east bump can avoid overlap only by occupying the right west dent, so
Injectivity yields equality of the perpendicular bits, Wang colours, and labels. The fixed bump at height reciprocally fills the left east dent. If both sides are closed, the adjacent body columns are disjoint. The vertical argument is identical with .
An open outer side would place a bump outside the square, so outer bits vanish. Diagonal support boxes meet in four cells around a macro-corner. The lower-left carrier occupies only its northeast body corner among those four; the upper-right carrier occupies only its southwest body corner. The other two cells cannot be bumps because variable coordinates are at most , while the fixed bump coordinate is . Thus diagonal carriers are disjoint. Boxes separated by two macro-pitches are disjoint.
All exchanged dents are filled by reciprocal bumps, and closed interfaces leave no holes. The uncovered cells are therefore precisely the translated cavities. They are mutually separated, 4-connected, and have area three. Any remaining placement lies in one residual component. A carrier is too large, while a plug fitting a three-cell component must equal it. The translation is uniquely the cavity origin.
Set and . A macro-edge is open exactly when the reciprocal carrier bits on that interface are one; plugs lie strictly inside one macrocell. We verify saturation on one orientation, the others following by symmetry. Suppose the bottom horizontal edge and the left vertical edge of a 2-by-2 macro-square are open. The open bottom edge equates the north bits of its two incident carriers. Since the bottom-left north bit is one (the left vertical interface is open), the bottom-right north bit is also one; reciprocal-bit equality then makes the right vertical interface open. That open right interface equates the west bits of its two incident carriers. The bottom-right west bit is one (the bottom interface is open), so the top-right west bit is one; reciprocal-bit equality then makes the top horizontal interface open. Thus two consecutive open edges force all four.
Theorem Theorem 6.2 makes the opening components filled rectangles. The carrier identities on an open edge give Wang-colour matching inside each component, and the common label supplies one element of . Conversely, a rectangular partition, an open Wang tiling on every block, and edge labels determine all carrier records. The interface rules give disjointness, the diagonal check handles corner contacts, and the unique plugs fill the cavities. These maps are inverse: a physical tiling determines the partition, the Wang tile identities and the interface labels, and conversely these data prescribe all carrier placements and the unique cavity plugs. An all-closed singleton still has one distinct carrier for every , because is recorded by its cavity.
There are index-grid edges. A partition with seam edges has open edges, proving the exact sum.
For every rectangular partition, , because block perimeters count the outer boundary once and each seam twice. Figure 3 contrasts the canonical one-block term with a representative nontrivial rectangular partition and identifies the seam parameter that drives the suppression estimate below.
The bijection in Theorem 7.2 assigns every geometric tiling to exactly one partition .
The unique one-block partition is the canonical term; every other tiling appears in exactly one nontrivial partition. For a fixed , the exact sum above already includes all open Wang tilings inside every block and all amplifier-label choices on every open macro-edge. Grouping the remaining partitions by their seam count therefore accounts for every noncanonical tiling exactly once. The two estimates below then bound, respectively, how many such partitions have a given and how large the complete internal Wang contribution of each partition can be.
For a nontrivial partition, Theorem 6.1 gives and at most dissections with seams. By Theorem 5.3 and the block-perimeter identity,
Writing for the sum of the nontrivial-partition terms, the exhaustive partition bijection now yields
where the second inequality uses and . This sum includes every noncanonical tiling through its unique rectangular partition. For this is at most . The one-block term is , so the normalized error is strictly below one and the floor identity follows. For , there is only the singleton partition and .
In particular, the identity cavity distinguishes Wang tile types even when their four edge colours coincide. For consecutive register values, the cavity positions are respectively
Recovering the Wang Count
The boundary-amplified Wang system separates the desired computation histories from the other open-boundary configurations by counting multiplicity. A bound on the remaining configurations makes the accepting-path count recoverable by integer division. The section also verifies the bit complexity of this readout, establishing metric completeness for the fixed Wang counter.
Define the total Wang-counting function by for , and set it to zero on all other strings.
Theorem 8.1 (Metric completeness of the Wang count). The function has the following properties.
.
For ,
.
Let be the least integer at least two satisfying , and let . Then
.
The exceptional set is finite. There is a polynomial-time finite-table function agreeing with on this set.
The instance map and the postprocessor
form a polynomial-time one-query metric reduction from to . The exponentiation is stopped once its value exceeds . On exceptional inputs the postprocessor ignores .
is -complete under polynomial-time metric reductions.
Proof. An open -tiling of an -square has a unique encoding by fixed-length tile labels. A deterministic verifier checks all horizontal and vertical adjacencies in time. On a binary input of length , , so guessing the labels and checking them takes time. Malformed strings and zero are rejected deterministically. This proves membership.
For , Theorem 3.1 gives , and Theorem 5.2 gives
This proves substitution.
Since , . For ,
When , both terms are below , proving the strict threshold estimate.
The lower bound tends to infinity with , so only finitely many strings lie below the fixed threshold. Their values define a finite hard-coded table . A lookup in a fixed table is polynomial-time. This existence claim does not require the threshold to be below .
For a nonexceptional input, put and . The substitution and threshold estimates give
Therefore
The exceptional branch is correct by the table.
It remains to justify the running time of the postprocessor. If , the second branch of returns zero immediately. Assume henceforth that , let , and let . Fix with . If , then , and the quotient is zero. Otherwise , and exponentiation by squaring computes using integers of at most bits. Division is polynomial in . No loop iterates in unary.
Thus is a polynomial-time metric reduction. The function is parsimoniously -complete by Theorem 3.1; composing its parsimonious reductions with this metric reduction proves hardness of .
For any sufficiently long , the nonexceptional postprocessor sends to zero because . Hence positivity of its second argument is not preserved.
Completeness of the Square-Tiling Count
The main theorem follows by composing the Wang-level readout with the geometric counting identity. The geometric postprocessor outputs an integer no larger than its input, so the two reductions compose in polynomial bit time. The general membership bound supplies the matching upper bound.
Proof of Theorem 1.1. Every member of is a nonempty finite 4-connected set by Theorem 7.2. Proposition 2.1 applies to this fixed family and gives the stronger membership . On the canonical input , this count includes the unique empty tiling of , while malformed strings receive value zero by definition.
For , the sets and coincide, as do their open Wang matching rules; hence . Theorem 7.2 gives
for every , including under .
Define the instance map by
It checks canonical binary syntax and, on a valid positive input, multiplies by the fixed constant , so it is polynomial-time. Define when is malformed or equals . For with , let and choose the fixed integer satisfying . If , set . If and , set . For , let . If , then , so set . Otherwise , and exponentiation by squaring computes the divisor, giving . All intermediate integers have at most bits. Computing the divisor and quotient is therefore polynomial in , without iterating in unary. This proves that is a total polynomial-time map.
For with , the geometric floor identity established above gives
On every other , both sides are zero. Hence is a one-query metric reduction.
The postprocessor satisfies . To make the composition explicit, combine the reduction of Theorem 8.1 with the geometric reduction by setting
Because the intermediate value has no more bits than , the composed postprocessor runs in time polynomial in . Hence metric-reduces to . Since is parsimoniously -complete, is -hard under polynomial-time metric reductions. Together with membership, it is complete.
This completes the proof.
Conclusion and Discussion
We prove that counting translation-only tilings of an square by a fixed finite family of connected polyominoes is #EXP-complete under polynomial-time metric reductions. Together with the efficient tileability criterion for fixed polyomino families [14], this establishes a sharp separation between feasibility and exact counting when the entire input is a binary side length. The proof shows that a binary side length can select an accepting-path count within a fixed Wang system and that this numerical information survives an ordinary geometric realization as an exact count, extending classical computation-to-tiling encodings to the fixed-square setting. The decisive step is a global counting guarantee obtained by combining a perimeter bound for open Wang rectangles with a seam bound for nontrivial rectangular dissections. Their combination places the total normalized contribution of all noncanonical configurations below one, so integer division recovers the intended count exactly. A companion Lean 4 formalization of the completeness result is available [11].
Future directions include simplifying the fixed polyomino family and extending numerical isolation to other succinct counting problems. More broadly, combining geometric rigidity with global counting bounds may provide a reusable approach to proving counting hardness under fixed local constraints.
AI Methodology
OpenAI’s ChatGPT was used to improve the language and clarity of the manuscript. A GPT-based multi-agent system assisted in reviewing the mathematical proofs and organizing the arguments into a Lean 4 formalization, particularly for the constructions and correctness proofs in § 3–§ 9.
References
- [1]Dorit Aharonov and Sandy Irani. Translationally invariant constraint optimization problems. In 38th Computational Complexity Conference (CCC 2023), LIPIcs 264, article 23, 2023. https://doi.org/10.4230/LIPIcs.CCC.2023.23.
- [4]Robert Berger. The Undecidability of the Domino Problem. Memoirs of the American Mathematical Society, No. 66, 1966. https://doi.org/10.1090/memo/0066.
- [5]Erik D. Demaine and Martin L. Demaine. Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity. Graphs and Combinatorics, 23(Suppl.):195–208, 2007. https://erikdemaine.org/papers/Jigsaw_GC/.DOI
- [6]Daniel Gottesman and Sandy Irani. The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems. Theory of Computing, 9(2):31–116, 2013. https://doi.org/10.4086/toc.2013.v009a002.
- [8][Kas61] P. W. Kasteleyn. The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice. Physica, 27(12):1209–1225, 1961. https://doi.org/10.1016/0031-8914(61)90063-5.
- [10][Kre88] Mark W. Krentel. The complexity of optimization problems. Journal of Computer and System Sciences, 36(3):490–509, 1988. https://doi.org/10.1016/0022-0000(88)90039-6.
- [11][Che26] Qiyu Chen. Pak’s fixed-polyomino square-counting theorem: Lean 4 formalization. Source repository, 2026. https://github.com/canghaimeng/PakFixedPolyomino.
- [12][MR01] Christopher Moore and John Michael Robson. Hard tiling problems with simple tiles. Discrete & Computational Geometry, 26(4):573–590, 2001. https://doi.org/10.1007/s00454-001-0047-6.
- [13][Oll09] Nicolas Ollinger. Tiling the plane with a fixed number of polyominoes. In Language and Automata Theory and Applications (LATA 2009), pages 638–647, 2009. https://doi.org/10.1007/978-3-642-00982-2_54.
- [14][Pak18] Igor Pak. Complexity problems in enumerative combinatorics. In Proceedings of the International Congress of Mathematicians (ICM 2018), volume 3, pages 3139–3166, 2018. https://arxiv.org/abs/1803.06636.
- [15][Pak20] Igor Pak. Counting with tiles. Lecture slides, Journée-séminaire de combinatoire, Paris Nord, June 2, 2020. https://lipn.fr/~cb/Seminaires/Slides/pak2020.pdf.
- [16][PY13] Igor Pak and Jed Yang. Tiling simply connected regions with rectangles. Journal of Combinatorial Theory, Series A, 120(7):1804–1816, 2013. https://doi.org/10.1016/j.jcta.2013.06.008.
- [17][Rob71] Raphael M. Robinson. Undecidability and nonperiodicity for tilings of the plane. Inventiones Mathematicae, 12:177–209, 1971.DOI
- [20][Wan61] Hao Wang. Proving theorems by pattern recognition—II. Bell System Technical Journal, 40(1):1–41, 1961. https://doi.org/10.1002/j.1538-7305.1961.tb03975.x.


