Use Backtracking Algorithm to Solve Sudoku
Tags: javascript, webdev, beginners, algorithms
Published: 2020-09-04 00:34:36

As promised in my recent article on [how to design an algorithm](https://dev.to/christinamcmahon/how-to-design-an-algorithm-2g9c), I am here to take a closer look at another popular technique for algorithm design called backtracking. 

**Backtracking** is a useful algorithm for solving problems with [recursion](https://dev.to/christinamcmahon/recursion-explained-with-examples-4k1m) by building a solution incrementally. Generally speaking, backtracking involves starting with a possible solution and if it doesn't work, you backtrack and try another solution until you find something that works. Backtracking is particularly helpful when solving [constraint satisfaction problems](https://en.wikipedia.org/wiki/Constraint_satisfaction_problem) such as crosswords, verbal arithmetic, and Sudoku.

In general, backtracking algorithms can be applied to the following three types of problems:
1. Decision problems to find a feasible solution to a problem
2. Optimization problems to find the best solution to a problem
3. Enumeration problems to find a set of feasible solutions to a problem

In this article, I will be demonstrating the backtracking strategy by solving a popular problem known as the Sudoku Solver. 

# Sudoku Solver
As a [Sudoku](https://en.wikipedia.org/wiki/Sudoku) fan myself, I was excited to dive into this problem. The backtracking algorithm for this problem will try to place each number in each row and column until it is solved. Let's start with the main method:

```javascript
function sudokuSolver(matrix) {
    if (solveSudoku(matrix) === true) {
        return matrix;
    }
    return 'NO SOLUTION';
}
```
Now, let's get into the main logic of our algorithm:
```javascript
const UNASSIGNED = 0;

function solveSudoku(matrix) {
    let row = 0;
    let col = 0;
    let checkBlankSpaces = false;

    /* verify if sudoku is already solved and if not solved,
    get next "blank" space position */ 
    for (row = 0; row < matrix.length; row++) {
        for (col = 0; col < matrix[row].length; col++) {
            if (matrix[row][col] === UNASSIGNED) {
                checkBlankSpaces = true;
                break;
            }
        }
        if (checkBlankSpaces === true) {
            break;
        }
    }
    // no more "blank" spaces means the puzzle is solved
    if (checkBlankSpaces === false) {
        return true;
    }

    // try to fill "blank" space with correct num
    for (let num = 1; num <= 9; num++) {
        /* isSafe checks that num isn't already present 
        in the row, column, or 3x3 box (see below) */ 
        if (isSafe(matrix, row, col, num)) {
            matrix[row][col] = num;

            if (solveSudoku(matrix)) {
                return true;
            }

            /* if num is placed in incorrect position, 
            mark as "blank" again then backtrack with 
            a different num */ 
            matrix[row][col] = UNASSIGNED;
        }
    }
    return false;
}
```
Next, let's take a closer look at some helper methods:
```javascript
function isSafe(matrix, row, col, num) {
    return (
        !usedInRow(matrix, row, num) && 
        !usedInCol(matrix, col, num) && 
        !usedInBox(matrix, row - (row % 3), col - (col % 3), num)
    );
}

function usedInRow(matrix, row, num) {
    for (let col = 0; col < matrix.length; col++) {
        if (matrix[row][col] === num) {
            return true;
        }
    }
    return false;
}

function usedInCol(matrix, col, num) {
    for (let row = 0; row < matrix.length; row++) {
        if (matrix[row][col] === num) {
            return true;
        }
    }
    return false;
}

function usedInBox(matrix, boxStartRow, boxStartCol, num) {
    for (let row = 0; row < 3; row++) {
        for (let col = 0; col < 3; col++) {
            if (matrix[row + boxStartRow][col + boxStartCol] === num) {
                return true;
            }
        }
    }
    return false;
}
```
Lastly, let's put our algorithm to the test:
```javascript
const sudokuGrid = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0], 
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
];

console.log(sudokuSolver(sudokuGrid));
```
Here's our sudoku example being solved by backtracking:

![sudoku being solved by backtracking](https://dev-to-uploads.s3.amazonaws.com/i/kz1eyj7su1bvg9qis43w.gif)
# Conclusion
I had a lot of fun with this article and hope that you found it helpful for getting a basic understanding of backtracking. Here are some additional resources:
- [Overview of Backtracking](https://en.wikipedia.org/wiki/Backtracking) from Wikipedia
- [Video Explanation of Backtracking](https://www.youtube.com/watch?v=gBC_Fd8EE8A) by V. Anton Spraul