DEV Community

loading...
Cover image for Use Backtracking Algorithm to Solve Sudoku

Use Backtracking Algorithm to Solve Sudoku

Christina
Junior Developer at Interplay Learning - Feel free to contact me via LinkedIn or connect on Github, I am always happy to chat with folks from this community!
・3 min read

As promised in my recent article on how to design an algorithm, 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 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 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 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:

function sudokuSolver(matrix) {
    if (solveSudoku(matrix) === true) {
        return matrix;
    }
    return 'NO SOLUTION';
}

Now, let's get into the main logic of our algorithm:

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:

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:

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

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:

Discussion (2)

Collapse
ngochang29397 profile image
jelly • Edited

Thank you very much for the useful article
Could you please explain more about the number 3 in the code, I could not figure out where you get that number from?

Collapse
kunal__satpute profile image
Kunal Satpute

It's a 9 x 9 matrix and each boxes are 3 x 3.