patternMinor
Minimum Number of Unique Identifiers for a Grid of Cells
Viewed 0 times
uniquenumbergridminimumcellsforidentifiers
Problem
I have a grid of cells, X cells wide by Y cells high. Each cell has four corners, NW, NE, SW and SE. Each corner is shared with adjacent neighbors; i.e., a cell's SW corner is the NW corner of the cell just below it.
In any grid of (X,Y) cells, there are (X+1,Y+1) corners.
In this grid, each corner can be assigned an arbitrary identifier, giving the cell an 'address' of the format NW-NE-SW-SE
In this image below, for cell 'h' the four corners are named
What is the minimum number of unique identifiers needed to allow all cells to have a unique 'address'?
Is there a generalized algorithm or pattern one might use to calculate such a list of identifiers and to assign them to all the corners in a grid of size (XY)?
Thanks in advance!
Edited to add: My purpose in asking this question is to solve a real-world problem, which I did not originally state in my question, and further, that I don't necessarily need the theoretical or provable 'minimum set of unique symbols' but rather an algorithm that combines the properties of a) being easy to understand and implement and, b) provides fairly good answers (i.e., small, perhaps not smallest). Very subjective, I know.
In any grid of (X,Y) cells, there are (X+1,Y+1) corners.
In this grid, each corner can be assigned an arbitrary identifier, giving the cell an 'address' of the format NW-NE-SW-SE
In this image below, for cell 'h' the four corners are named
@, #, $ and %. The NE corner of cell 'g' would also share the corner name '@'. Cell 'h' would have the address @#$%What is the minimum number of unique identifiers needed to allow all cells to have a unique 'address'?
Is there a generalized algorithm or pattern one might use to calculate such a list of identifiers and to assign them to all the corners in a grid of size (XY)?
Thanks in advance!
Edited to add: My purpose in asking this question is to solve a real-world problem, which I did not originally state in my question, and further, that I don't necessarily need the theoretical or provable 'minimum set of unique symbols' but rather an algorithm that combines the properties of a) being easy to understand and implement and, b) provides fairly good answers (i.e., small, perhaps not smallest). Very subjective, I know.
Solution
This is one of the 800 possible optimal (2-colour) solutions (including reflections and rotations) to the 4x4 problem, found using an exhaustive search:
The optimality is because 16 cells require 16 distinct 4-digit labels, which exhausts the set of 4-bit patterns. The next "interesting" problem size (in the sense that a "perfect" solution might be possible) is $3^4=81$ cells (so 9x9, 27x3 or 81x1), which would exhaust all 4-digit base-3 numbers -- but this is much too large to check with a dumb brute-force search.
Larger grids can be tiled with a pattern like this, using fresh pairs of colours for each copy. It's then advantageous to use a slightly less "efficient" base pattern that contains no monochromatic cells (the optimal solution above necessarily contains a blue and a yellow monochromatic cell) -- since then you can reuse each colour with every other colour. In other words, $k$ colours permit $k \choose 2$ copies of the base pattern if it is free of monochromatic cells, rather than just $k/2$ copies.
Tiling-based solutions will in general not be optimal. I don't yet see any better way to attack the problem of finding optimal or boundedly approximate solutions other than brute force on a case-by-case basis with a SAT or ILP solver, as suggested by D.W.
The optimality is because 16 cells require 16 distinct 4-digit labels, which exhausts the set of 4-bit patterns. The next "interesting" problem size (in the sense that a "perfect" solution might be possible) is $3^4=81$ cells (so 9x9, 27x3 or 81x1), which would exhaust all 4-digit base-3 numbers -- but this is much too large to check with a dumb brute-force search.
Larger grids can be tiled with a pattern like this, using fresh pairs of colours for each copy. It's then advantageous to use a slightly less "efficient" base pattern that contains no monochromatic cells (the optimal solution above necessarily contains a blue and a yellow monochromatic cell) -- since then you can reuse each colour with every other colour. In other words, $k$ colours permit $k \choose 2$ copies of the base pattern if it is free of monochromatic cells, rather than just $k/2$ copies.
Tiling-based solutions will in general not be optimal. I don't yet see any better way to attack the problem of finding optimal or boundedly approximate solutions other than brute force on a case-by-case basis with a SAT or ILP solver, as suggested by D.W.
Context
StackExchange Computer Science Q#161087, answer score: 4
Revisions (0)
No revisions yet.