Deduce position from logic clues
MathWorksSoftware Engineer · Online Assessment
Last updated
This question evaluates the ability to model and reason about constraint-satisfaction on a 2D grid, including logical inference with directional and adjacency relations, combinatorial placement constraints, and determination of uniqueness.
You are given a set of locations L laid out on a 2D grid (rows and columns) and a list of relational clues of the forms: (
- X is north/south/east/west of Y; (
- X is adjacent/not-adjacent to Y; (
- X cannot be in row r or column c; (
- Exactly one of {A, B, C} is adjacent to D. Assume the clues are consistent and determine the unique location (row, column) of a target person P or report that no unique solution exists. Design an algorithm to solve this constraint-satisfaction problem, describe the data structures you will use, analyze time/space complexity, and provide pseudocode.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.