Backtracking is a technique used for problem solving where the algorithm follows a brute-force approach. Unlike Dynamic programming, which looks for the optimal solution, backtracking is used when there are multiple solutions to the problem and all of them need to be found.
Backtracking uses a recursive calling function to find a solution in a step-by-step manner. Each problem has a unique set of constraints which are checked after every step. If the currently found solution holds good with the constraints, then the program continues to the next stage. Otherwise, the program performs an undo operation where the last update is undone, and the next feasible solution for the is found.
So, backtracking algorithm can be seen as trying to find a path to the solution with small barriers where the problem can backtrack if there is no feasible solution for the problem.
Solving a Sudoku Board.
The regular Sudoku board is made up of a partially filled 9 x 9 grid of cells. To find the solution, one must fill each empty cell with a number between 1 and 9 such that the row, its respective column and subgrid contains exactly one instance of the digit.
Approach: Brute Force vs. Backtracking
A general approach to solving the puzzle would be to employ a Brute Force algorithm. This algorithm would be responsible for generating all the board, regardless of whether they are correct or no. This means that the algorithm is tasked with a task of generating a large number of digits for each board and this results in a combinational explosion as the size of the board increases.
Instead of this, I employed the technique of backtracking to solve the problem. The algorithm selects an empty cell and generates a number for this cell. It then proceeds to check whether this number belongs to the cell and doesn't break the board. If the number is proven to be in the right position, the algorithm continues by looking for the next empty cell to fill. If the number is proven to be wrong for the position, the algorithm removes this number and tries the next digit. Hence, it performs backtracking and results in much lesser computation than the general brute force approach.
Writing Code!
Finding An Empty Cell
The 9 x 9 Sudoku board is stored as 2-dimensional list. The empty cells are filled with the number '0' while the rest of the cells are filled with their numbers.
The algorithm starts by finding an empty cell to fill. It does this by looping through cells in every row and column. When the cell has the value of 0, it is said to be empty and the function find_empty returns the respective co-ordinates in the form of a tuple with format (row,column).
Check Validity
Once an empty cell is found, it is to be filled with a number between 1 and 9. The number should fit all the constraints of the problem and to check for it's validity, the function check_validity performs a series of checks.
It first checks to make sure that the inserted number is unique to that that respective row and column.
After this, the sub-grid that contains the current cell is checked. This is a 3 x 3 grid and must contain unique numbers between 1 and 9. To get the starting corner of the sub-grid, the row and column positions are divided by 3 and the floor value of this is retrieved. They are divided by 3 as the board is seen as a 3 x 3 grid of sub-grids. With the starting position of the sub-grid, the rows and columns of that subgrid are tested for validity of the numbers.
Only if the number passes all the constraints, then the function returns True. Otherwise, it returns False, prompting the algorithm to test the next number.
Solving Board
This is the entry point of the program. After finding an empty cell, it finds a valid number to fit that cell. After assigning the valid number to that cell, it continues to find the next empty cell by recursively calling the function.
Everytime that the function finds out that the new number breaks the board, it backtracks and looks for a new solution.
Finally, once the solution is found, the board can be printed. In this way, backtracking can be used to find the solution to a Sudoku Board.
Solving a Peg Solitaire Board.
The Game
Peg Solitaire is a board game involving a single player moving pegs on a board with holes. It is famously called as Brainvita in India. There are many variants of the board, but this post focuses on solving the English Solitaire Board.
To start, the board is entirely filled with pegs, except for the central hole. The objective of the game is to move the pegs around and ending up with the central hole being the only one occupied with a peg. The game has a few valid moves which need to be followed to achieve the goal. A valid move is to jump a peg either up,down,left or right only. The peg is made to jump over an adjacent peg into a hole two positions away and then remove the peg that it jumped over of.
The working of the solver.
The main task in solving the board would be to find the next move and make sure that it is legal. Incase of a bad move, the algorithm should be able to undo the most recent moves, essentially, backtracking.
Finding the next move
The everytime that a move is made, the program is able to know how many pegs are left on the board. Since the total number of pegs that can be on the board are 32, the value of self.pegs constantly updated as moves are made and undone. The legal directions are stored in the list self.directions and the this is traversed when searching for the next legal move.
While searching for the next move, the algorithm considers a matrix of dimension 3x2, cur_move. Based on the direction of movement, the row or column of that matrix is updated by calling update_move. In this, the corrent peg's position is always pointed at by cur_move[0][0]. Based on the current direction, the changes that occur to the matrix:
- "up" or "down"
- The row is updated as the peg is moving in a vertical direction and the col remains the same.
- "right" or "left"
- The col is updated as the peg is moving in a horizontal direction and the row remains the same.
Updating Board and checking for Legality
With each move that is made, the value of self.pegs is decremented as the move results in the removal of a peg form the board. When the legality of this move is found to be bad, the move is reversed by calling undo_move which returns the board to its previous state and also increments self.pegs to account for this change.
Thank You!
With this, I was able to implement backtracking technique to solve these puzzles easily. This shows that the technique is very efficient in solving techniques and substituting it for some scenraios where brute-force would take way too long. This concludes the post. As usual, the entire code to both implementations can be found on my Github repository.
References
Tech With Tim
Backtracking to solve Peg Solitaire.
Peg Solitaire Solver In Java