Skip to content

Exact Algorithm, Heuristic and Metaheuristic for NP-Hard Sudoku problem using Graph Coloring in C++

Notifications You must be signed in to change notification settings

camiladuartes/Sudoku-Algorithms

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

22 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Algorithms for NP-Hard Sudoku problem using Graph Coloring

In this project, an heuristic and an exact algorithm using backtracking were implemented to solve the Sudoku problem.

For the heuristic algorithm, the Largest-First heuristic models the game on a graph and uses the Graph Coloring Problem to solve it, using the decreasing order of vertices by degree for graph coloring, iterating between them and coloring with the smallest available color.

Compilation and Running

  1. cd exact-algorithm/src/ or cd heuristic/src/ or cd meta-heuristic/src/
  2. g++ sudokuSolution.cpp
  3. ./a.out < ../../database/dataset.csv

Students:

  • Camila Duarte
  • Ranna Raabe

About

Exact Algorithm, Heuristic and Metaheuristic for NP-Hard Sudoku problem using Graph Coloring in C++

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published