Constraint-Satisfaction on a 2D Grid with Relational Clues

Context

You are given a rectangular grid with R rows and C columns. A set of named entities (people) must each occupy exactly one distinct grid cell. A set of relational clues constrain where entities may be placed. Your goal is to determine whether the location (row, column) of a particular target person P is uniquely determined by the clues. If so, return that unique location; otherwise report that no unique solution exists.

Assumptions and definitions:

• Rows are indexed 1..R (1 is the northernmost/top row) and columns 1..C (1 is the westernmost/left column).
• A cell is identified by (r, c).
• Adjacency means 4-neighborhood: two cells are adjacent if their Manhattan distance is 1 (i.e., share a side).
• Directional relation "X is north of Y" means same column and row(X) < row(Y); similarly for south (>), east (same row, col(X) > col(Y)), west (<).
• All entities occupy distinct cells unless otherwise stated.

Clue Types

You may receive any combination of the following clues:

1. Directional: X is north/south/east/west of Y
2. Adjacency: X is adjacent/not-adjacent to Y
3. Unary bans: X cannot be in row r or column c
4. Exactly-one adjacency: Exactly one of {A, B, C} is adjacent to D

Clues are guaranteed to be mutually consistent (at least one full placement exists), but may or may not uniquely determine P's location.

Task

Design an algorithm to:

• Determine the unique location (row, column) of target P if implied by the clues; otherwise report that no unique solution exists.
• Describe data structures you will use.
• Analyze time and space complexity.
• Provide clear pseudocode.

Input (conceptual): R, C; set of entities E; target P ∈ E; list of clues of the types above.

Output: Either the unique (row, column) for P, or a statement that P is not uniquely determined.