The Sudoku Solver project aims to solve Sudoku puzzles of varying difficulty levels using the AC-3 (Arc Consistency) algorithm and the Backtracking algorithm. This project includes implementations for solving easy, medium, and hard Sudoku puzzles.
- Sudoku Puzzle Representation: 9x9 grid representation of Sudoku puzzles.
- AC-3 Algorithm: Enforces arc consistency to reduce the search space before applying the backtracking algorithm.
- Backtracking Algorithm: A depth-first search algorithm to find the solution by exploring possible assignments and backtracking when a conflict is found.
- Puzzle Difficulties: Includes easy, medium, and hard Sudoku puzzles with pre-defined boards.
- AC-3 Algorithm
- Backtracking Algorithm
The AC-3 algorithm (Arc Consistency Algorithm #3) is used to simplify the problem by enforcing arc consistency. It systematically removes values from the domains of variables that cannot satisfy the constraints with their neighbors, reducing the problem space for the backtracking algorithm.
The backtracking algorithm is a recursive depth-first search algorithm. It attempts to build a solution incrementally by assigning values to variables and backtracking whenever an inconsistency is detected.