Latest news about Bitcoin and all cryptocurrencies. Your daily crypto news habit.
Sudoku
Sudoku is a number-placement puzzle 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â.
The most common Sudoku puzzles use a 9x9 grid. The grids are partially filled (with hints) to ensure a solution can be reached.
An unsolved 9x9 Sudoku puzzle. The bold numbers are the hints.
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 tree of possibilities. 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 for a typical backtracking algorithm
The tree diagram also shows 2 groupsâââUnexplored Possible Candidates and 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 encoding our problem, goal and constraints in a step-by-step algorithm.
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, abandon candidate and repeat step 2 with the next number. Otherwise, check if the goal is reached.
- If a solution is found, stop searching. Otherwise, repeat steps 2 to 4.
Pen-paper demo
Groovy. Now letâs try all this in practice with a simple 3x3Â grid.
We start off by listing all the empty spots. If we label each cell in the grid with a pair of numbers (x,y) and mark the first cell (1,1), then our empty spots will be at locations:
(1,2) (2,2) (2,3) (3,1) (3,2)
We now select the first spot (1,2) 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.).
Letâs place number 1 in this spot and see if it fits.
Filling â1â in spot (1, 2)
It does. Great. We can now select the next spot on the list (2,2) and do the same thing again. This time however, it fails. We already have a 1 in this row. This means that we must abandon candidate and repeat step 2 with the next numberâââwhich is 2.
Huzzah! 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 (1 at spot (2,2)), visited a previous stage (empty spot (2,2)) and explored a new candidate solution (number 2 at spot (2,2)).
When we move on to spot (2,3), 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 abandon candidate and repeat step 2 with the next number. Only this time, we must visit spot (2,2) first to fix spot (2,3).
We need to fill number 3 in spot (2,2) and that will resolve the issue.
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.
However, consider the same grid with one small change. Replacing the 1 in cell (3,3) with a 2 renders the grid unsolvable. Similarly, removing hints from cells (2,1) and (3,3) allows for multiple solutions. But since this algorithm has a single goal, it stops after the first solution is reached.
Unsolvable 3x3 puzzle (left) and Multi-solution 3x3 puzzle (right)
Hereâs what the tree of possibilities looks like:
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 âNP-complete combinatorial problemâ. As complex as it may sound, it really isnât (not for the scope of this article):
- NP-complete means that while we can easily verify a solution, it is rather difficult to arrive at one.
- Combinatorial means that to arrive at a solution, we must perform selection and arrangement of some dataâââcombination and permutation.
Sample problems
We can try to solve some other problems by basing our approach on our current understanding.
The Binary Watch problem is a close enough relative to the Sudoku solver. Two more problems that rank similar are Combination Sum III and Permutation Sequence.
There are a lot more problems 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:
- Problem
- Goal
- Constraints
- Termination conditions
- Step-by-step algorithm
Sudoku and Backtracking was originally published in Hacker Noon on Medium, where people are continuing the conversation by highlighting and responding to this story.
Disclaimer
The views and opinions expressed in this article are solely those of the authors and do not reflect the views of Bitcoin Insider. Every investment and trading move involves risk - this is especially true for cryptocurrencies given their volatility. We strongly advise our readers to conduct their own research when making a decision.