[Model] SquareTiling

[isPANN]

Motivation

SQUARE-TILING (P250) from Garey & Johnson, A8 GP13. A classical NP-complete problem in the family of Wang tiling problems. Given a set of colored square tiles (Wang tiles) and a grid size N, the question is whether the tiles can be placed on an N x N grid such that adjacent tiles have matching edge colors. This problem bridges combinatorial graph problems and geometric/constraint satisfaction problems. It is the target of a reduction from Directed Hamiltonian Path (R194), and its infinite variant (tiling the entire plane) is famously undecidable (Berger, 1966).

Definition

Name: SquareTiling
Canonical name: Square Tiling; also: Bounded Wang Tiling, Wang Domino Problem (bounded variant), Finite Tiling
Reference: Garey & Johnson, Computers and Intractability, A8 GP13

Mathematical definition:

INSTANCE: Set C of "colors," collection T ⊆ C^4 of "tiles" (where <a,b,c,d> denotes a tile whose top, right, bottom, and left sides are colored a, b, c, and d, respectively), and a positive integer N ≤ |C|.
QUESTION: Is there a tiling of an N x N square using the tiles in T, i.e., an assignment of a tile f(i,j) in T to each ordered pair i, j, 1 ≤ i ≤ N, 1 ≤ j ≤ N, such that (1) if f(i,j) = <a,b,c,d> and f(i+1,j) = <a',b',c',d'>, then a = c' (top of lower tile matches bottom of upper tile), and (2) if f(i,j) = <a,b,c,d> and f(i,j+1) = <a',b',c',d'>, then b = d' (right of left tile matches left of right tile)?

Note: Tiles may be reused (each tile type can appear at multiple grid positions). Tiles may NOT be rotated or reflected.

Variables

• Count: N^2 (one variable per grid cell)
• Per-variable domain: {0, 1, ..., |T|-1} -- the index of the tile type placed at cell (i, j)
• Meaning: variable t_{i,j} in {0, ..., |T|-1} assigns a tile type to grid cell (i, j). The configuration is valid if for all adjacent cell pairs, the shared edge colors match: top/bottom between vertically adjacent cells, left/right between horizontally adjacent cells.

Schema (data type)

Type name: SquareTiling
Variants: none

Field	Type	Description
num_colors	usize	Number of colors
tiles	Vec<(usize, usize, usize, usize)>	Collection of tile types; each (top, right, bottom, left) is a tuple of color indices
grid_size	usize	The integer N specifying an N x N tiling grid

Notes:

• This is a feasibility (decision) problem: Value = Or.
• Key getter methods: num_colors() (= |C|), num_tiles() (= |T|), grid_size() (= N).
• Tiles are NOT rotatable -- <a,b,c,d> is distinct from <b,c,d,a>.
• The same tile type may be placed at multiple grid positions.

Complexity

• Decision complexity: NP-complete (Garey, Johnson, and Papadimitriou, 1977; transformation from Directed Hamiltonian Path).
• Best known exact algorithm: O(|T|^{N^2}) via brute-force enumeration of all tile assignments, with constraint propagation pruning in practice. No sub-exponential exact algorithm is known.
• Concrete complexity expression: "num_tiles^(grid_size^2)" (for declare_variants!)
• Special cases: When N is given in unary, the problem is NP-complete. When N is given in binary (as log N bits), the problem becomes NEXP-complete. For fixed tile sets, the bounded tiling problem can sometimes be solved in polynomial time depending on the tile structure.
• Infinite variant: Determining whether a given tile set can tile the entire plane (Z × Z) is undecidable (Berger, 1966). The periodic tiling variant (period < N) is also NP-complete.
• References:
  • M. R. Garey, D. S. Johnson, C. H. Papadimitriou (1977). Unpublished results. NP-completeness of bounded tiling via reduction from Directed Hamiltonian Path.
  • R. Berger (1966). "The Undecidability of the Domino Problem." Memoirs of the AMS, No. 66. American Mathematical Society, Providence, RI.
  • H. Wang (1961). "Proving theorems by pattern recognition II." Bell System Technical Journal, 40(1), pp. 1-41. Original formulation of Wang tiles.

Specialization

• This is a special case of: Constraint Satisfaction Problem (CSP) -- each grid cell is a variable, the tile set defines unary constraints, and color-matching defines binary constraints between adjacent cells.
• Known special cases: 1 x N tiling (reduces to path finding in a directed graph of tile adjacencies, solvable in polynomial time). Tiling with a single tile type is trivially decidable.
• Generalizations: Tiling arbitrary regions (not just squares), tiling with hexagonal tiles, tiling the infinite plane (undecidable).

Extra Remark

Full book text:

INSTANCE: Set C of "colors," collection T ⊆ C4 of "tiles" (where <a,b,c,d> denotes a tile whose top, right, bottom, and left sides are colored a,b,c, and d, respectively), and a positive integer N ≤ |C|.
QUESTION: Is there a tiling of an N×N square using the tiles in T, i.e., an assignment of a tile A(i,j) ∈ T to each ordered pair i,j, 1 ≤ i ≤ N, 1 ≤ j ≤ N, such that (1) if f(i,j) = <a,b,c,d> and f(i+1,j) = <a',b',c',d'>, then a = c', and (2) if f(i,j) = <a,b,c,d> and f(i,j+1) = <a',b',c',d'>, then b = d'?

Reference: [Garey, Johnson, and Papadimitriou, 1977]. Transformation from DIRECTED HAMILTONIAN PATH.
Comment: Variant in which we ask if T can be used to tile the entire plane (Z×Z) "periodically" with period less than N is also NP-complete. In general, the problem of whether a set of tiles can be used to tile the plane is undecidable [Berger, 1966], as is the problem of whether a set of tiles can be used to tile the plane periodically.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all |T|^{N^2} tile assignments; check color-matching constraints for all adjacent pairs.)
• It can be solved by reducing to integer programming. (Binary variables x_{i,j,t} = 1 if tile type t is placed at cell (i,j). Constraints: exactly one tile per cell, and for each adjacent pair, the shared edge colors must match. Companion rule issue to be filed separately.)
• Other: Backtracking with arc consistency / constraint propagation.

Example Instance

Input:
Colors: C = {0, 1, 2} (3 colors)
Tiles (top, right, bottom, left):

• t0 = <0, 1, 2, 0>
• t1 = <0, 0, 2, 1>
• t2 = <2, 1, 0, 0>
• t3 = <2, 0, 0, 1>

Grid size: N = 2 (2 × 2 grid)

Valid tiling:

| (1,1)=t0 | (1,2)=t1 |
| (2,1)=t2 | (2,2)=t3 |

Check constraints:

• Horizontal (1,1)-(1,2): right of t0 = 1, left of t1 = 1. ✓
• Horizontal (2,1)-(2,2): right of t2 = 1, left of t3 = 1. ✓
• Vertical (1,1)-(2,1): bottom of t0 = 2, top of t2 = 2. ✓
• Vertical (1,2)-(2,2): bottom of t1 = 2, top of t3 = 2. ✓

Answer: YES — a valid 2 × 2 tiling exists. There are 16 valid tilings in total out of 256 possible assignments.

Note: The tile set is designed so that row 1 tiles (t0, t1) have top=0 and bottom=2, while row 2 tiles (t2, t3) have top=2 and bottom=0, ensuring vertical compatibility. Horizontal compatibility is ensured by the right/left color pairs: tiles with right=1 must neighbor tiles with left=1, and tiles with right=0 must neighbor tiles with left=0.

Negative example:
Keep only tiles t0 = <0, 1, 2, 0> and t2 = <2, 1, 0, 0> from the positive example.

Both tiles have right = 1 but left = 0. For horizontal adjacency, the right side of one tile must match the left side of its neighbor. Since right = 1 ≠ 0 = left for both tiles, no two tiles can be placed side by side. Exhaustive search over all 2^4 = 16 possible assignments confirms no valid 2 × 2 tiling exists. Answer: NO.

Python validation script

from itertools import product

def check_tiling(tiles, n):
    count = 0
    for assignment in product(range(len(tiles)), repeat=n*n):
        grid = [[assignment[i*n+j] for j in range(n)] for i in range(n)]
        valid = True
        for i in range(n):
            for j in range(n):
                t = tiles[grid[i][j]]
                if j+1 < n:
                    t_right = tiles[grid[i][j+1]]
                    if t[1] != t_right[3]: valid = False; break
                if i+1 < n:
                    t_below = tiles[grid[i+1][j]]
                    if t[2] != t_below[0]: valid = False; break
            if not valid: break
        if valid: count += 1
    return count

# Positive: 4 tiles, N=2
tiles_pos = [(0,1,2,0), (0,0,2,1), (2,1,0,0), (2,0,0,1)]
assert check_tiling(tiles_pos, 2) == 16
print("Positive: 16 valid tilings (correct)")

# Negative: only t0 and t2
tiles_neg = [(0,1,2,0), (2,1,0,0)]
assert check_tiling(tiles_neg, 2) == 0
print("Negative: 0 valid tilings (correct)")

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but ILP solvability claimed without companion [Rule] issue link
Non-trivial	✅ Pass	Distinct feasibility constraints (colored tile matching on grid) unlike any existing problem
Correctness	⚠️ Warn	"Furer, 2008" NEXP-completeness reference could not be verified; no specific best-known algorithm cited
Well-written	❌ Fail	Multiple failed example attempts left in body; missing companion issue link; no concrete complexity expression for declare_variants!

Overall: 1 passed, 2 warnings, 1 failed

---

Usefulness

Problem novelty: SquareTiling does not exist in the codebase (verified via pred show). The problem is clearly distinct from all 126 existing problem types — it deals with colored square tile placement under adjacency constraints, which is structurally different from any graph, formula, set, or algebraic problem currently implemented.

Planned reductions: The issue mentions a reduction from Directed Hamiltonian Path (G&J R194), which connects it to the existing graph. HamiltonianPath exists in the codebase.

ILP solvability: The issue checks "It can be solved by reducing to integer programming" and describes a natural ILP formulation (binary variables x_{i,j,t}). However, per project conventions, when direct ILP solving is claimed, the issue must link a companion [Rule] SquareTiling to ILP issue. No such link is provided. Warn.

Motivation: Present and substantive — bridges combinatorial and geometric constraint satisfaction problems, references Wang tiling literature.

Non-trivial

SquareTiling has genuinely distinct feasibility constraints from all existing problems. The core structure — placing colored tiles on a grid with edge-color matching — is not a repackaging of any graph coloring, satisfiability, or constraint problem already in the codebase. While it is related to CSP, it has its own specific input structure (tile set, grid size, color matching). Pass.

Correctness

Verified references:

• Berger (1966): "The Undecidability of the Domino Problem," Memoirs of the AMS, No. 66. Confirmed — this is a foundational result showing that tiling the infinite plane with Wang tiles is undecidable.
• Wang (1961): "Proving theorems by pattern recognition II," Bell System Technical Journal, 40(1), pp. 1-41. Confirmed — original formulation of Wang tiles.
• Garey, Johnson, and Papadimitriou (1977): NP-completeness of bounded tiling via reduction from Directed Hamiltonian Path. Confirmed — this result is well-established in the literature (also presented in Lewis & Papadimitriou, "Elements of the Theory of Computation," 1981).

Unverified reference:

• Furer, 2008: The claim that "When N is given in binary (as log N bits), the problem becomes NEXP-complete (Furer, 2008)" could not be verified. Multiple web searches for a Furer 2008 paper on NEXP-completeness of bounded Wang tiling returned no matching publication. Martin Furer's publication record around 2008 focuses on integer multiplication algorithms, not tiling problems. The NEXP-completeness result for binary-encoded tiling is known in the literature but the attribution to "Furer, 2008" appears incorrect. Warn — the specific citation needs correction or replacement.

Complexity claim: The issue states "O*(|T|^{N^2}) worst case via backtracking with constraint propagation" which is just the brute-force bound. No specific best-known exact algorithm is cited with author/year/citation. For declare_variants!, the project requires a concrete complexity expression referencing getter methods (e.g., num_tiles^(grid_size^2)). This is acceptable as a bound but the issue should explicitly state this is the brute-force complexity and note whether any better algorithm is known.

Well-written

Failed items:

1. Example quality — failed attempts left in body: The example section contains three failed tiling attempts before arriving at a working example. The first attempt explicitly says "FAIL" and the issue author works through multiple iterations. While the final example is correct and well-verified, the failed attempts should be removed — the issue body should present only the clean, working example. This makes the issue hard to read and would produce a confusing paper entry.

2. Missing companion issue link: The "How to solve" section checks ILP solvability but does not link a [Rule] SquareTiling to ILP companion issue, as required by the template.

3. No concrete complexity expression: The Complexity section describes the search space informally as |T|^{N^2} but does not provide a concrete expression in terms of getter method names (e.g., num_tiles^(grid_size^2)) suitable for declare_variants!.

4. Missing clearly labeled Expected Outcome: The example embeds the answer ("Answer: YES") but does not follow the template format for Expected Outcome with a clear justification section.

Passing items:

• Definition is mathematically well-formed and matches the G&J text
• Variables section correctly identifies N^2 variables with domain {0,...,|T|-1}
• Schema is reasonable with appropriate fields
• Symbol usage is mostly consistent across sections
• The final worked example (with 3 colors, 4 tiles, N=2) is correct and exercises the core structure

Recommendations

• Remove the three failed example attempts and keep only the final working 3-color, 4-tile example
• Correct or remove the "Furer, 2008" NEXP-completeness citation — find the actual source or note this as an aside without a specific citation
• Add a concrete complexity expression: num_tiles^(grid_size^2) for the brute-force bound
• Create and link a companion [Rule] SquareTiling to ILP issue if direct ILP solving is intended
• Add a clearly labeled "Expected Outcome" subsection to the example

[isPANN]

Fix-issue changelog

• Example section: Removed 3 failed tiling attempts; kept only the clean working example (3 colors, 4 tiles, N=2, 16 valid tilings).
• Negative example: Replaced broken negative (removing t3 still leaves 2 valid tilings) with correct one: keep only t0 and t2 (both have right=1 but left=0, so horizontal adjacency always fails; verified 0 tilings).
• Complexity: Added concrete expression "num_tiles^(grid_size^2)" for declare_variants!.
• Furer citation: Removed incorrect "Furer, 2008" attribution for NEXP-completeness; kept the claim without the unverifiable citation.
• ILP: Added note that companion rule issue to be filed separately.
• Added Python validation script verifying both examples.

Applied by /fix-issue.