Java icon indicating copy to clipboard operation
Java copied to clipboard

Add sudoku solver

Open Raghu0703 opened this issue 2 weeks ago • 0 comments

Description

This PR adds a Sudoku Solver implementation using the Backtracking algorithm as requested in issue #6929.

Changes

  • Added SudokuSolver.java in src/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.java in src/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

Raghu0703 avatar Nov 24 '25 08:11 Raghu0703