Using Sudoku to explore backtracking Sudoku is a number-placement where the objective is to fill a square grid of size ‘n’ with numbers between 1 to ‘n’. 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 puzzle The most common Sudoku puzzles use a 9x9 grid. The grids are partially filled (with hints) to ensure a solution can be reached. And here’s the solution. Notice how each row, each column and each sub-grid have all numbers from 1 to 9. Some puzzles may even have multiple solutions. The solution to above Sudoku puzzle. One row, column and sub-grid have been highlighted. Aside: solving a Sudoku puzzle Sudoku is a logic-based puzzle. Needless to say, solving one requires a series of logical moves and might require a bit of guesswork. 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: . kristanix.com/sudokuepic/sudoku-solving-techniques Backtracking Backtracking is an algorithm for finding all (or some) of the solutions to a problem that incrementally builds candidates to the solution(s). As soon as it determines that a candidate cannot possibly lead to a valid solution, it abandons the candidate. Backtracking is all about choices and consequences. Abandoning a candidate typically results in visiting a previous stage of the problem-solving-process. This is what it means to “backtrack” — visit a previous stage and explore new possibilities from thereon. Usually, apart from the original problem and the end goal, we also have a set of constraints that the solution must satisfy. The simplest (read ‘dumbest’) implementations often use little to no “logic” or “insight” to the problem. Instead, they frantically try to find a solution by guesswork. A backtracking algorithm can be thought of as a . In this tree, the root node is the original problem, each node is a candidate and the leaf nodes are possible solution candidates. We traverse the tree depth-first from root to a leaf node to solve the problem. tree of possibilities Tree of Possibilities for a typical backtracking algorithm The tree diagram also shows 2 groups — and . Unexplored Possible Candidates Impossible Candidates UPC marks nodes that were never explored. Some of them could have been viable candidates, leading to another solution. Since we never explored them, we can never know. Problems where multiple solutions are acceptable won’t have this group. IC groups are the obvious ones. It contains nodes which have a failed candidate node as one of their ancestor nodes. None of the nodes in this group are candidate nodes and none of the leaf nodes are solution nodes. Sudoku & Backtracking We will now create a Sudoku solver using backtracking by our problem, goal and constraints in a step-by-step algorithm. encoding Problem Given a, possibly, partially filled grid of size ‘n’, completely fill the grid with number between 1 and ‘n’. Goal Goal is defined for verifying the solution. Once the goal is reached, searching terminates. A fully filled grid is a solution if: Each row has all numbers form 1 to ‘n’. Each column has all numbers form 1 to ‘n’. Each sub-grid (if any) has all numbers form 1 to ‘n’. Constraints Constraints are defined for verifying each candidate. A candidate is valid if: Each row has unique numbers form 1 to ’n’ or empty spaces. Each column has unique numbers form 1 to ‘n’ or empty spaces. Each sub-grid (if any) has unique numbers form 1 to ‘n’ or empty spaces. Termination conditions Typically, backtracking algorithms have termination conditions other than reaching goal. These help with failures in solving the problem and special cases of the problem itself. There are no empty spots left to fill and the candidate still doesn’t qualify as a the solution. There are no empty spots to begin with, i.e., the grid is already fully filled. Step-by-step algorithm Here’s how our code will “guess” at each step, all the way to the final solution: Make a list of all the empty spots. Select a spot and place a number, between 1 and ‘n’, in it and validate the candidate grid. If any of the constraints fails, . Otherwise, check if the goal is reached. abandon candidate and repeat step 2 with the next number If a solution is found, stop searching. Otherwise, repeat steps 2 to 4. Pen-paper demo . Now let’s try all this in practice with a simple 3x3 grid. Groovy A 3x3 Sudoku puzzle We start off by listing all the empty spots. If we label each cell in the grid with a pair of numbers and mark the first cell , then our empty spots will be at locations: (x,y) (1,1) (1,2) (2,2) (2,3) (3,1) (3,2) We now select the first spot to work with. Since this is a 3x3 grid, we have numbers 1 to 3 at our disposal and no sub-grids to worry about (sub-grids are only a bother for grids with squared sides, like 4, 9, 16 etc.). (1,2) Let’s place number in this spot and see if it fits. 1 Filling ‘1’ in spot (1, 2) It does. Great. We can now select the next spot on the list and do the same thing again. This time however, it fails. We already have a in this row. This means that we must — which is . (2,2) 1 abandon candidate and repeat step 2 with the next number 2 Filling 2 in spot (2, 2) One more spot is filled. Also, it might not look like it, but we did just perform backtracking on a single spot. We abandoned a candidate solution ( at spot ), visited a previous stage (empty spot ) and explored a new candidate solution (number at spot ). Huzzah! 1 (2,2) (2,2) 2 (2,2) When we move on to spot , we have another problem. As you can see, we are all out of options. None of the possible numbers fit in. This means that we must now . Only this time, we must visit spot first to fix spot . (2,3) abandon candidate and repeat step 2 with the next number (2,2) (2,3) Failure to fill spot (2, 3) We need to fill number in spot and that will resolve the issue. 3 (2,2) Backtracking to spot (2, 2) and then re-visiting spot (2, 3) We now repeat this process until with either reach the goal or we hit one of the termination conditions. Since this was a demo problem, it should be obvious that we’d arrive at the solution without any further complications. Solved 3x3 Sudoku puzzle However, consider the same grid with one small change. Replacing the in cell with a renders the grid unsolvable. Similarly, removing hints from cells and allows for multiple solutions. But since this algorithm has a single goal, it stops after the first solution is reached. 1 (3,3) 2 (2,1) (3,3) Unsolvable 3x3 puzzle (left) and Multi-solution 3x3 puzzle (right) Here’s what the looks like: tree of possibilities Tree of Possibilities for 3x3 Sudoku Implementation Enough talk. Let’s code … Disclaimer (for python-istas): The code you’re about to see is not pythonic.IMHO, it is borderline ugly. The purpose of this snippet is to explain convert the steps shown above into simple, meaningful code and not to boast the elegance of python. What next? This article aims to strengthen the concept of backtracking by drawing connections with a popular game of logic. I should tell you that Sudoku is an ‘ . As complex as it may sound, it really isn’t (not for the scope of this article): NP-complete combinatorial problem’ means that while we can verify a solution, it is rather to arrive at one. NP-complete easily difficult means that to arrive at a solution, we must perform selection and arrangement of some data — combination and permutation. Combinatorial Sample problems We can try to solve some other problems by basing our approach on our current understanding. The problem is a close enough relative to the Sudoku solver. Two more problems that rank similar are and . Binary Watch Combination Sum III Permutation Sequence There are that you can try on. However, trying to mold them into the Sudoku solver pattern might not always be trivial. It’s best to try to formulate your approach in the following pattern: a lot more problems Problem Goal Constraints Termination conditions Step-by-step algorithm
