Skip to content

Frown00/csp

Repository files navigation

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