Advanced Map Coloring with Neighborhood Awareness

This project is a customizable template for solving the map coloring problem using Constraint Satisfaction Problem (CSP) techniques. It ensures that no two neighboring countries share the same color.

You can adjust the Neighborhood Distance to control how many levels of neighbors are considered.

An example of a Neighborhood Distance of 2:

• Iran → Pakistan (neighbor)
• Pakistan → China (neighbor)
• So China is treated as a second-degree neighbor of Iran.

Project Structure

File	Description
CSP.py	Defines the CSPclass and utility functions to set up and solve CSPs.
graphics.py	Provides functions to visualize colored maps.
map_generator.py	Generates the country-neighbor dictionary from a CSV file.
Solver.py	Contains CSP-solving algorithms (backtracking, heuristics).
main.py	Main script to run the program with selected parameters.

Parameters

You can control the program's behavior using these command-line arguments:

• -m, --map: Continent(s) to color. Options: Asia, Africa, America, Europe.
• -lcv, --lcv: Use the Least Constraining Value heuristic.
• -mrv, --mrv: Use the Minimum Remaining Values heuristic.
• -ac3, --arc-consistency: Apply AC-3 algorithm to maintain arc consistency.
• -ND, --Neighbourhood-distance: Set how many degrees of neighbors to consider (default is 1).

How to Run

Use the following examples to execute the program:

1. Basic run with LCV and MRV heuristics on Asia:

python main.py -m Asia -lcv -mrv

2. Add arc consistency:

python main.py -m Europe -lcv -mrv -ac3

3. Include second-degree neighbors:

python main.py -m Europe -lcv -mrv -ac3 -ND 2

Note: The countries_dataset.csv file has some mistakes in terms of neighbors especially for russia and turkey