Skip to content

Using CSP algorithm with Forward Checking for solving Sudoku Puzzle

License

Notifications You must be signed in to change notification settings

cocolico14/Sudoku-Solver

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

7 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Sudoku-Solver

Using CSP algorithm with Forward Checking for solving Sudoku Puzzle


Documentation

Variable Class :

  • For holding data of each variable such as its Value and Domain.

State Class:

  • For holding data of each state.

ProblemTree Class:

  • Search through all available digit (the domain of variable) for the next empty spot in the table.

A naive approach is to only check the first empty spot in table if there is no value in its domain then it backtracks

But with Forward Checking it checks the next empty spot after the first one, if the variable we had chosen for the first empty spot left us with no choice for the second blank spot then it backtracks


Example

The table that has been shown in the beginning is solvable

Then the example below is not solvable because there are two 7 in the first region of the table

There is no solution


Author

License

This project is licensed under the MIT License - see the LICENSE file for details