Sudoku Solver in Java using Backtracking Algorithm

By Pallav Goswami

This is an implementation of the Sudoku Solver using a Backtracking Algorithm. It takes an unsolved Sudoku board as input and returns the solution.

OVERVIEW

The SudokuSolver class contains the main method to solve a 9x9 Sudoku puzzle using a backtracking algorithm. The solve method recursively checks and assigns a number from 1 to 9 to the empty cells of the board until a solution is found. The isSafe method checks whether the number to be assigned in a cell is valid or not by checking the row, column, and box constraints of the Sudoku puzzle.

PRE-REQUISITES

1) JDK

2) Any IDE that can run Java code

3) Knowledge of Backtracking and its working.

CODE STRUCTURE

The program uses backtracking to solve a 9x9 Sudoku puzzle. The program first creates a 2D array to represent the puzzle, with 0 representing empty cells. It then recursively tries to fill in each empty cell with a number from 1 to 9, checking at each step whether the number is safe to place in that cell by checking the row, column, and 3x3 box called a grid in sudoku terms. If the puzzle is successfully solved, it is displayed to the user.

ALGORITHM

1) Start from the top left corner of the Sudoku Board.

2) Find the first empty cell (0) and set the row and column values.

3) Check each number (1 to 9) if it can be placed in the cell.

4) If it can be placed then set the cell and move to the next empty cell.

5) If no number can be placed then backtrack and try a different number.

6) Repeat until Sudoku Board is filled.

METHODS/FUNCTIONS

1) The solve method implements the backtracking algorithm to solve the Sudoku board.

2) The isSafe method checks if a number can be placed in a cell according to Sudoku rules.

3) The display method prints the solved Sudoku board to the console.

4) The main method initializes the Sudoku board and calls the solve method to solve the board. The resultant board is displayed if it is solvable, otherwise "Cannot Be Solved" message is displayed.

CONCLUSION

The SudokuSolver code provides an implementation to solve a 9x9 Sudoku puzzle using a backtracking algorithm. The solve method uses the isSafe method to check the validity of each assignment and backtracks if no valid assignment is possible. The program can be extended to solve Sudoku puzzles of different sizes by changing the size of the board in the code.

RESULTS

UNSOLVED SUDOKU BOARD

SOLVED SUDOKU BOARD