This project aims at building an android app which can efficiently solve any sudoku board using algorithmic techniques like depth-first search and backtracking.
The Sudoku Solver app uses an optimized depth-first search and backtracking algorithm to solve a given Sudoku puzzle. The algorithm works by maintaining a stack of boards representing the current state of the puzzle. The first board in the stack is the initial state of the puzzle. Every board is a node in the generated solution tree(implemented using a stack).
The algorithm starts by selecting the first empty cell in the top board of the stack. It then tries all possible values that can be placed in that cell. If value(s) are found that do not violate any of the Sudoku rules, new boards are created with those value(s) in the respective selected cell(s), and the new board(s) are added to the top of the stack. The algorithm then proceeds to the next empty cell and repeats the process. Everytime a board is analyzed, it will be removed from the stack, irrespective of whether or not it generated any child boards. The process is then repeated on the current first element of the stack.
If the algorithm reaches a point where all elements have been removed from the stack and no filled/solved configuration is achieved, an error message is displayed.
Basic Dart implementation of approach:
static SudokuBoard depthFirstSolve(SudokuBoard root) {
List<SudokuBoard> solutionSet = [root];
while (solutionSet.isNotEmpty) {
SudokuBoard target =
solutionSet[0]; //target sudoku board for all operations.
if (target.isBoardFilled()) {
return target;
}
solutionSet.removeAt(0);
solutionSet.insertAll(0, target.stepInto());
}
//return empty sudoku board when solving is not possible
return SudokuBoard.empty();
}The app has three screens: a welcome screen, an input screen, and a solution screen.
The welcome screen is the first screen that the user sees when they open the app. It contains a welcome message and a button that takes the user to the input screen.
The input screen allows the user to enter the initial values of a Sudoku puzzle. The user can input the values using the number panel provided at the bottom of the input screen. Once the user has entered the values, they can click the "Solve" button to find the solution to the puzzle. If the puzzle is unsolvable, the app will display an error message.
The solution screen displays the solution to the Sudoku puzzle, along with a button to take the user back to the input page to solve another puzzle.