Grid logic
| Paradigm(s) | Constraint solving |
|---|---|
| Designed by | User:Hakerh400 |
| Appeared in | 2024 |
| Computational class | Bounded storage machine |
| Major implementations | Implemented |
| File extension(s) | .txt |
Grid logic is an esolang invented by User:Hakerh400 in 2024.
Overview
Source code consists of a rectangular grid of squares (tiles). Each tile contains at most one of the following 5 entities:
Entities can be rotated (4 different rotations for the leftmost three of them, 2 different rotations for the remaining two entities).
The interpreter tries to color each tile in the grid with red or blue. Each entity imposes constraints regarding the color of its tile. Here are the constraints (assuming they are rotated like on the image above):
- The first (leftmost) entity from the image must have the same color as the entity below
- The second entity from the image must have the same color as the entity two tiles below
- The third entity must have the opposite color of the entity below
- The fourth entity must be blue iff both the entities above and below it are blue
- The fifth entity must be red iff both the entities above and below it are red
The grid is toroidal, meaning that it wraps around (both horizontally and vertically). For example, if there is V in the top left corner, it will have the same color as the tile in the bottom left corner.
The output is either a properly colored grid, or an indication that the grid cannot be colored according to the rules. If there are multiple solutions, the interpreter is free to choose one of them.
Examples
Example 1
In this example a 3x3 grid is used. This image depicts the unique solution. The tile below T must be the same color as the tile on the left of T, and it must be different from T. If we assume that T is red, then the tile on the left of T must also be red, but it breaks the fourth entity rule. Therefore, T must be blue, and the two tiles on the left of T must be red.
Example 2
This is similar to Example 1, but demonstrates the use of the second type of entities.
Example 3
This grid has no solution. The T in the top row forces the top left corner to be red. The T in the bottom row forces the bottom left corner to be blue. But the entities in those two corners must have the same color.
Example 4
Example 5
Example 6
This has no solution because there is a T above a V (in the leftmost column).
Example 7
This also has no solution, but it is more complicated to prove.
Example 8
This has no solution because of the rightmost entity in the third row. Removing this entity makes the grid solvable, as can be seen in Example 9.
Example 9
The same grid from Example 8, but without the problematic entity.
Example 10
Example 11
Example 12
No solution.
Example 13
Example 14
Example 15
The smallest grid size is 1x1 (width and height must be nonnegative integers). Every entity except T, when placed in the 1x1 grid, makes exactly two possible solutions. T makes the grid unsolvable because it wraps around and asserts that its own tile color must be different from itself. See also Example 38.
Example 16
This has exactly two solutions, the other solution being the inverted colors. See Example 39.
Example 17
Any colors can be assigned to the tiles. So 4 solutions in total.
Example 18
Example 19
Example 20
No solution because of the 2x2 square in the bottom left corner. See Example 39.
Example 21
Example 22
Example 23
Example 24
Example 25
Example 26
Example 27
No solution because of the upside-down V and upside-down T (decond column from the right).
Example 28
Interpreter is free to choose any valid solution. In this case, the solver decided to color the bottom right corner blue, but there is also a solution in which the bottom right corner is red (although other tiles must change their color).
Example 29
Example 30
Example 31
No solution because of T above V, but in this case they wrap around (second column from the left).
Example 32
Example 33
Example 34
Example 35
Example 36
Example 37
Example 38
It wraps around two times, effectively asserting that it has the same color as itself. This has two solutions. See also Example 15.
Example 39
Similar to Example 16 and Example 20. Unlike in Example 20, this one has a solution.
Example 40
A large example.
Complexity class
The interpreter is NP-complete.
Implementation
- Implementation (also requires this)