Skip to content

This repository includes a study that aims to handle the map coloring problem with backtracking paradigm. Detailed info in ReadMe

License

Notifications You must be signed in to change notification settings

asrinoztin/map_coloring_with_backtracking

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

6 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Introduction

The goal of the project is to use a backtracking search algorithm to color the map of the continent of South America. The main goal is to color the countries so that two adjacent countries shouldn't share the same color. To do this, we can only use a maximum of four different colors (blue, green, red, and yellow). The m-coloring problem, the backtracking algorithm, the benefits of include the neighbors as a dictionary in the code, and the code explanation will all be covered in this project report.

M-coloring Problem

One of the graph coloring problems is the m-coloring problem. The challenge is to use m colors at maximum to evenly distribute the vertices of a network so that no two neighboring vertices share the same color. Since the m-coloring problem is a NP-complete problem, no algorithm with polynomial time complexity can solve it for all kinds of inputs.

Backtracking Algorithm

Backtracking is a generic algorithmic method that involves examining all possible combinations in order to find a solution to a problem. The backtracking algorithm tries to put together a solution and discards the incomplete ones as soon as it sees they can't be finished to a valid one as expected.

Constraint Satisfaction Problems

Task: Color each country Variables: {Argentina, Bolivia, Brazil, Chile, Colombia, Ecuador, Falkland Islands, Guyana, Paraguay, Peru, Suriname, Uruguay, Venezuela} Fields: {blue, red, green, yellow} Restrictions: Adjacent countries must be in different colors

Output

145997912-7c15a792-2396-4508-974b-56f949a9362c

About

This repository includes a study that aims to handle the map coloring problem with backtracking paradigm. Detailed info in ReadMe

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages