Typically, backtracking algorithms have termination conditions other than reaching goal. A candidate is valid if:Įach row has unique numbers form 1 to ’n’ or empty spaces.Įach column has unique numbers form 1 to ‘n’ or empty spaces.Įach sub-grid (if any) has unique numbers form 1 to ‘n’ or empty spaces. A fully filled grid is a solution if:Įach column has all numbers form 1 to ‘n’.Įach sub-grid (if any) has all numbers form 1 to ‘n’.Ĭonstraints are defined for verifying each candidate. Once the goal is reached, searching terminates. Goal is defined for verifying the solution. ![]() Given a, possibly, partially filled grid of size ‘n’, completely fill the grid with number between 1 and ‘n’. We will now create a Sudoku solver using backtracking by encoding our problem, goal and constraints in a step-by-step algorithm. None of the nodes in this group are candidate nodes and none of the leaf nodes are solution nodes. It contains nodes which have a failed candidate node as one of their ancestor nodes. Problems where multiple solutions are acceptable won’t have this group. Since we never explored them, we can never know. Some of them could have been viable candidates, leading to another solution. UPC marks nodes that were never explored. The tree diagram also shows 2 groups - Unexplored Possible Candidates and Impossible Candidates. Tree of Possibilities for a typical backtracking algorithm We traverse the tree depth-first from root to a leaf node to solve the problem. In this tree, the root node is the original problem, each node is a candidate and the leaf nodes are possible solution candidates. Instead, they frantically try to find a solution by guesswork.Ī backtracking algorithm can be thought of as a tree of possibilities. The simplest (read ‘dumbest’) implementations often use little to no “logic” or “insight” to the problem. Usually, apart from the original problem and the end goal, we also have a set of constraints that the solution must satisfy. This is what it means to “backtrack” - visit a previous stage and explore new possibilities from thereon. Backtracking is all about choices and consequences.Ībandoning a candidate typically results in visiting a previous stage of the problem-solving-process. As soon as it determines that a candidate cannot possibly lead to a valid solution, it abandons the candidate. ![]() Backtrackingīacktracking is an algorithm for finding all (or some) of the solutions to a problem that incrementally builds candidates to the solution(s). Since this isn’t an article to explore how to solve a Sudoku puzzle, I’ll just a leave a link to one that helped me getting started: /sudokuepic/sudoku-solving-techniques. Needless to say, solving one requires a series of logical moves and might require a bit of guesswork. One row, column and sub-grid have been highlighted. Some puzzles may even have multiple solutions. Notice how each row, each column and each sub-grid have all numbers from 1 to 9. The bold numbers are the hints.Īnd here’s the solution. The grids are partially filled (with hints) to ensure a solution can be reached.Īn unsolved 9x9 Sudoku puzzle. The most common Sudoku puzzles use a 9x9 grid. The numbers must be placed so that each column, each row, and each of the sub-grids (if any) contains all of the numbers from 1 to ‘n’. Sudoku is a number-placement puzzle where the objective is to fill a square grid of size ‘n’ with numbers between 1 to ‘n’.
0 Comments
Leave a Reply. |