Constraint Satisfaction Problem (CSP) Solver in JavaScript

This challenge asks you to implement a basic Constraint Satisfaction Problem (CSP) solver in JavaScript. CSPs are a powerful framework for solving problems with a set of variables, domains of possible values for those variables, and constraints that define relationships between variables. This is useful for tasks like scheduling, map coloring, and Sudoku solving.

Problem Description

You are to implement a CSP solver that can solve a simple map coloring problem. The problem involves coloring a map with a given number of colors such that no adjacent regions have the same color.

What needs to be achieved:

The solver should take as input:

1. regions: An array of strings representing the regions of the map.
2. neighbors: An object where keys are region names (strings) and values are arrays of strings representing the neighboring regions.
3. colors: An array of strings representing the available colors.

The solver should return an object where keys are region names and values are the assigned colors, satisfying all constraints. If no solution exists, it should return null.

Key Requirements:

• The solver must use a backtracking search algorithm.
• The solver must enforce the constraint that no two adjacent regions have the same color.
• The solver should be able to handle cases where no solution exists.

Expected Behavior:

The solver should systematically explore the search space, assigning colors to regions one by one. If a conflict arises (i.e., two adjacent regions have the same color), the solver should backtrack and try a different color. If all possible color assignments have been tried and no solution is found, the solver should return null.

Edge Cases to Consider:

• Empty input: What should happen if regions is empty?
• No neighbors: What if a region has no neighbors?
• Unsolvable problem: What if the constraints are too restrictive and no solution exists?
• Regions with the same name (should be handled gracefully, ideally by throwing an error or returning null).

Examples

Example 1:

Input:
regions = ["WA", "OR", "CA", "NV", "UT", "AZ"]
neighbors = {
  "WA": ["OR"],
  "OR": ["WA", "CA", "NV"],
  "CA": ["OR", "NV", "AZ"],
  "NV": ["OR", "CA", "UT"],
  "UT": ["NV", "AZ"],
  "AZ": ["CA", "UT"]
}
colors = ["red", "green", "blue"]
Output:
{
  "WA": "red",
  "OR": "green",
  "CA": "blue",
  "NV": "red",
  "UT": "green",
  "AZ": "red"
}
Explanation: This is a valid coloring where no adjacent regions share the same color.  There are multiple valid solutions.

Example 2:

Input:
regions = ["A", "B"]
neighbors = {
  "A": ["B"],
  "B": ["A"]
}
colors = ["red"]
Output:
null
Explanation:  With only one color available, it's impossible to color adjacent regions "A" and "B" differently.

Example 3: (Edge Case - No Neighbors)

Input:
regions = ["X", "Y", "Z"]
neighbors = {
  "X": [],
  "Y": [],
  "Z": []
}
colors = ["red", "green"]
Output:
{
  "X": "red",
  "Y": "green",
  "Z": "red"
}
Explanation: Since no regions are neighbors, any color assignment is valid.

Constraints

• The number of regions will be between 1 and 10.
• The number of colors will be between 1 and 5.
• The names of regions and colors will be strings.
• The solver should complete within 5 seconds for reasonable map configurations.
• The input neighbors object will only contain valid region names as keys.

Notes

• Consider using recursion to implement the backtracking search.
• A isConsistent function can be helpful to check if a partial assignment is valid before proceeding.
• The order in which you assign colors to regions can affect performance. Consider heuristics for variable and value ordering. (Not required for a basic solution, but a good consideration for optimization).
• Error handling for invalid input (e.g., region names not present in the neighbors object) is not strictly required but is good practice.
• The solution is not necessarily unique. Any valid coloring is acceptable.