# 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)