Skip to content

Latest commit

 

History

History
30 lines (22 loc) · 1.31 KB

README.md

File metadata and controls

30 lines (22 loc) · 1.31 KB

Graph Coloring Problem

Program created as a university project to learn how backtracking and forward checking algorithms works and how to program them.
It's a problem which may classified as Constraint Satisfaction Problem (CSP).
Two algorithms mention above are use to solve this type of problems.

What's the problem?

Coloring each node (point) with a different color than its neighbors

More info

Preview

alt text

Program generates graph with selected number of nodes (points).
Then using given algorithm try to find out all solutions and present one of them.
There is also heuristic which change how algorithm works.
When it turns off then algorithm jumps randomly between nodes.
When it turns on then next node is with the lease avaiable colors to choose.

Color Pool

alt text alt text

Maximum 7 colors. Obviously adding more colors makes there is a lot of more solutions and it may affect performance