DEV Community

Cover image for Use Backtracking Algorithm to Solve Sudoku
Christina
Christina

Posted on

Use Backtracking Algorithm to Solve Sudoku

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';
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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));
Enter fullscreen mode Exit fullscreen mode

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:

Oldest comments (3)

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.

Collapse
 
jerrygithub profile image
jerryGitHub

Thanks for the article
It would have been better if you displayed a complete listing of a working program, not in your language which resembles C
Best wishes, Jerry