problemreductions/models/misc/
square_tiling.rs

1//! Square Tiling (Wang Tiling) problem implementation.
2//!
3//! Given a set C of colors, a collection T of tiles (each with four colored edges:
4//! top, right, bottom, left), and a positive integer N, determine whether there
5//! exists a tiling of an N x N grid using tiles from T such that adjacent tiles
6//! have matching edge colors. Tiles may be reused but not rotated or reflected.
7
8use crate::registry::{FieldInfo, ProblemSchemaEntry};
9use crate::traits::Problem;
10use crate::types::Or;
11use serde::de::Error as _;
12use serde::{Deserialize, Deserializer, Serialize};
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "SquareTiling",
17        display_name: "Square Tiling",
18        aliases: &["WangTiling"],
19        dimensions: &[],
20        category: crate::registry::ProblemCategory::Misc,
21        module_path: module_path!(),
22        description: "Place colored square tiles on an N x N grid with matching edge colors",
23        fields: &[
24            FieldInfo { name: "num_colors", type_name: "usize", description: "Number of colors" },
25            FieldInfo { name: "tiles", type_name: "Vec<(usize, usize, usize, usize)>", description: "Collection of tile types (top, right, bottom, left)" },
26            FieldInfo { name: "grid_size", type_name: "usize", description: "Grid dimension N for N x N tiling" },
27        ],
28    }
29}
30
31/// A tile with four colored edges: (top, right, bottom, left).
32/// Each color is an index in `0..num_colors`.
33pub type Tile = (usize, usize, usize, usize);
34
35#[derive(Debug, Clone, Serialize)]
36pub struct SquareTiling {
37    num_colors: usize,
38    tiles: Vec<Tile>,
39    grid_size: usize,
40}
41
42impl SquareTiling {
43    fn validate_inputs(
44        num_colors: usize,
45        tiles: &[Tile],
46        grid_size: usize,
47    ) -> Result<(), crate::registry::ConstructionError> {
48        if num_colors == 0 {
49            return Err("SquareTiling requires at least one color"
50                .to_string()
51                .into());
52        }
53        if tiles.is_empty() {
54            return Err("SquareTiling requires at least one tile".to_string().into());
55        }
56        if grid_size == 0 {
57            return Err("SquareTiling requires grid_size >= 1".to_string().into());
58        }
59        for (i, &(top, right, bottom, left)) in tiles.iter().enumerate() {
60            if top >= num_colors
61                || right >= num_colors
62                || bottom >= num_colors
63                || left >= num_colors
64            {
65                return Err(
66                    format!("Tile {} has color(s) out of range 0..{}", i, num_colors).into(),
67                );
68            }
69        }
70        Ok(())
71    }
72
73    /// Create a new `SquareTiling` instance, returning an error if inputs are invalid.
74    pub fn try_new(
75        num_colors: usize,
76        tiles: Vec<Tile>,
77        grid_size: usize,
78    ) -> Result<Self, crate::registry::ConstructionError> {
79        Self::validate_inputs(num_colors, &tiles, grid_size)?;
80        Ok(Self {
81            num_colors,
82            tiles,
83            grid_size,
84        })
85    }
86
87    /// Create a new `SquareTiling` instance.
88    ///
89    /// # Panics
90    ///
91    /// Panics if `num_colors` is 0, `tiles` is empty, `grid_size` is 0,
92    /// or any tile color is out of range.
93    pub fn new(num_colors: usize, tiles: Vec<Tile>, grid_size: usize) -> Self {
94        Self::try_new(num_colors, tiles, grid_size).unwrap_or_else(|message| panic!("{message}"))
95    }
96
97    /// Number of colors.
98    pub fn num_colors(&self) -> usize {
99        self.num_colors
100    }
101
102    /// Number of tile types.
103    pub fn num_tiles(&self) -> usize {
104        self.tiles.len()
105    }
106
107    /// Grid dimension N (for N x N grid).
108    pub fn grid_size(&self) -> usize {
109        self.grid_size
110    }
111
112    /// The collection of tile types.
113    pub fn tiles(&self) -> &[Tile] {
114        &self.tiles
115    }
116
117    /// Check whether a configuration represents a valid tiling.
118    ///
119    /// The configuration is a flat array of tile indices of length `grid_size^2`,
120    /// laid out in row-major order: position `i * grid_size + j` corresponds
121    /// to grid cell `(i, j)` (row i, column j).
122    fn is_valid_tiling(&self, config: &[usize]) -> bool {
123        let n = self.grid_size;
124        if config.len() != n * n {
125            return false;
126        }
127
128        // Check all tile indices are valid
129        for &tile_idx in config {
130            if tile_idx >= self.tiles.len() {
131                return false;
132            }
133        }
134
135        // Check horizontal adjacency: right of (i,j) must match left of (i,j+1)
136        for i in 0..n {
137            for j in 0..n - 1 {
138                let left_tile = self.tiles[config[i * n + j]];
139                let right_tile = self.tiles[config[i * n + j + 1]];
140                if left_tile.1 != right_tile.3 {
141                    return false;
142                }
143            }
144        }
145
146        // Check vertical adjacency: bottom of (i,j) must match top of (i+1,j)
147        for i in 0..n - 1 {
148            for j in 0..n {
149                let upper_tile = self.tiles[config[i * n + j]];
150                let lower_tile = self.tiles[config[(i + 1) * n + j]];
151                if upper_tile.2 != lower_tile.0 {
152                    return false;
153                }
154            }
155        }
156
157        true
158    }
159}
160
161#[derive(Deserialize)]
162struct SquareTilingData {
163    num_colors: usize,
164    tiles: Vec<Tile>,
165    grid_size: usize,
166}
167
168impl<'de> Deserialize<'de> for SquareTiling {
169    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
170    where
171        D: Deserializer<'de>,
172    {
173        let data = SquareTilingData::deserialize(deserializer)?;
174        Self::try_new(data.num_colors, data.tiles, data.grid_size).map_err(D::Error::custom)
175    }
176}
177
178impl Problem for SquareTiling {
179    const NAME: &'static str = "SquareTiling";
180    type Solution = Vec<usize>;
181    type Value = Or;
182
183    crate::problem_parameters![
184        ("grid_size", grid_size),
185        ("num_colors", num_colors),
186        ("num_tiles", num_tiles),
187    ];
188
189    fn variant() -> Vec<(&'static str, &'static str)> {
190        crate::variant_params![]
191    }
192
193    fn evaluate(&self, config: &Self::Solution) -> Result<Or, crate::traits::EvaluationError> {
194        let n = self.grid_size;
195        if config.len() != n * n {
196            return Err(crate::traits::EvaluationError::InvalidConfiguration(
197                "tiling representation length does not match the grid".into(),
198            ));
199        }
200        if config.iter().any(|&tile| tile >= self.tiles.len()) {
201            return Err(crate::traits::EvaluationError::InvalidConfiguration(
202                "tiling contains an out-of-range tile".into(),
203            ));
204        }
205        Ok(Or(self.is_valid_tiling(config)))
206    }
207}
208
209impl crate::solvers::BruteForceProblem for SquareTiling {
210    fn dimensions(&self) -> Vec<usize> {
211        vec![self.tiles.len(); self.grid_size * self.grid_size]
212    }
213}
214
215crate::declare_variants! {
216    default SquareTiling => "num_tiles^(grid_size^2)",
217}
218
219crate::register_brute_force! {
220    SquareTiling,
221}
222
223#[cfg(feature = "example-db")]
224pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
225    vec![crate::example_db::specs::ModelExampleSpec {
226        id: "square_tiling",
227        instance: Box::new(SquareTiling::new(
228            3,
229            vec![(0, 1, 2, 0), (0, 0, 2, 1), (2, 1, 0, 0), (2, 0, 0, 1)],
230            2,
231        )),
232        optimal_config: serde_json::json!(vec![0, 1, 2, 3]),
233        optimal_value: serde_json::json!(true),
234    }]
235}
236
237#[cfg(test)]
238#[path = "../../unit_tests/models/misc/square_tiling.rs"]
239mod tests;
problemreductions/models/misc/square_tiling.rs

problemreductions/models/misc/
square_tiling.rs
