Java
Java copied to clipboard
Add sudoku solver
Description
This PR adds a Sudoku Solver implementation using the Backtracking algorithm as requested in issue #6929.
Changes
-
Added
SudokuSolver.javainsrc/main/java/com/thealgorithms/backtracking/- Implements backtracking algorithm to solve 9×9 Sudoku puzzles
- Includes
isValid()method to verify Sudoku constraints (row, column, 3×3 subgrid) - Includes
solveSudoku()method with recursive backtracking logic - Includes
printBoard()helper method for formatted output - Provides example usage in
main()method
-
Added
SudokuSolverTest.javainsrc/test/java/com/thealgorithms/backtracking/- Tests solvable Sudoku puzzle with expected solution verification
- Tests unsolvable Sudoku puzzle (invalid constraints)
- Tests already solved Sudoku
- Tests empty Sudoku board
- Tests difficult Sudoku puzzle with fewer clues
Algorithm Details
- Approach: Depth-first search with backtracking
- Time Complexity: O(9^m) where m is the number of empty cells
- Space Complexity: O(m) for the recursion stack
- Reference: https://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Backtracking
Testing
✅ All new tests pass: mvn test -Dtest=SudokuSolverTest
✅ Verified with multiple Sudoku puzzles
✅ Code follows repository formatting standards
✅ Includes proper documentation and comments
Checklist
- [x] I have read CONTRIBUTING.md.
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL