Backtracking Algorithm to Solve Sudoku Puzzle in JavaScript

I believe that the best way to improve your skills is by actually building something new and make a use of what you learn. But, searching for a project to start with, is not always an easy task! It might take a lot of time, and as a result, you will feel bored before you even start.

In this article, I’m sharing with you one of the projects that I did when I first started to learn JavaScript. At that point, I was looking for a project to practice things I’ve already learned while keeping it challenging a little bit.

Backtracking

Let’s start with a simple explanation according to Wikipedia:

"Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, that incrementally builds candidates to the solutions…"

It sounds like the perfect fit for solving a Sudoku Puzzle!

Backtracking algorithm doesn’t always have great performance, but its simplicity and elegance makes it one of my favorites. In backtracking, you stop evaluating a possibility as soon as you recognize that it cannot be a valid solution for the problem. It’s all about knowing when to stop and step back to explore other possible solutions and see if it leads to a valid one.

Let's Start

Create a new directory to begin the project and navigate to that directory.

Define The Input

in order to make things easy and clear, we will start with two dimensional array as the initial board.

var board = [
    [0, 5, 1, 3, 6, 2, 7, 0, 0],
    [0, 4, 0, 0, 5, 8, 0, 0, 0],
    [0, 0, 0, 4, 0, 0, 0, 2, 5],
    [0, 8, 0, 0, 0, 0, 9, 0, 3],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [7, 0, 5, 0, 0, 0, 0, 8, 0],
    [1, 2, 0, 0, 0, 9, 0, 0, 0],
    [0, 0, 0, 2, 8, 0, 0, 6, 0],
    [0, 0, 8, 5, 3, 4, 2, 9, 0]
];

Find Next Empty Position

Let’s start with creating a function that takes the Sudoku board as an input, iterates over it searching for the first empty position (first position with value zero). When empty position is found, the function returns an array of two cells that contains the row and column of the empty position.

In case the board is full and there is no empty position, the function will return [-1,-1].

function nextEmptySpot(board) {
    for (var i=0; i<9 i++) {
        for( var j=0; j<9; j++) {
            if (board[i][j] === 0)
                return [i, j];
        }
    }
    return [-1, -1];
}

Check the Row, Column, and 3×3 Square

As we all know, Each row, column and square needs to be filled out with the numbers 1–9, without repeating any numbers within the row, column or square.

In this section, we will create several functions that will help us in order to insure that the solution is valid at any point.

Check Row function takes the board as an argument, the row that we would like to check and the new value that we want to add to this row. It iterates over the requested row and returns false in case this row already contains this value. Otherwise it returns true which means that this row is valid.

function checkRow(board, row, value) {
    for (var i=0; i<board[row].length; i++) {
        if (board[row][i] === value) {
            return false;
        }
    }

    return true;
}

in the same way, we can build the Check Column function.

function checkColumn(board, column, value) {
    for(var i=0; i<board.length; i++) {
        if (board[i][column] === value) {
            return false;
        }
    }

    return true;
}

Finally, let’s create the Check Square function. It takes the following arguments: the board, the row and column of the specific cell and the new value that we want to add to the board.

In order to get the first cell of the square, we divide the row by 3 and convert it to the largest integer less that or equal to the result, by using Math.floor(), and then, we multiply this number with 3 in order to get the most upper row of the square. We can do the same in order to get the most left column of the required square.

Now, let’s iterate over the square and check if the value is already exist, if yes, return false, otherwise, return true.

function checkSquare(board, row, column, value){
    const boxRow = Math.floor(row / 3) * 3;
    const boxCol = Math.floor(column / 3) * 3;

    for (var r=0; r<3; r++) {
        for (var c=0; c<3; c++) {
            if (board[boxRow + r][boxCol + c] === value)
                return false;
        }
    }

    return true;
}

Now we have all functions we need in order to test all possible conflicts. Let’s wrap it up and put it all together into one function:

function checkValue(board, row, column, value) {
    if (checkRow(board, row, value) &&
        checkColumn(board, column, value) &&
        checkSquare(board, row, column, value)) {
            return true;
    }
    
    return false;
}

At this point, we have everything we need to solve a Sudoku Puzzle, Let’s do it!

Find The Solution

This is the most important and challenging function in this project, here we need to make a use of Backtracking and think how we should find the solution.

Essentially, we need to go through every empty position, try every possible number from 1 to 9 and check if it is valid, if the answer is yes, we should use it and continue. In case there is no valid number that we can use, we should reset this position to zero and step back to try different possibilities. This should continue till we have no more empty positions to fill, that’s mean the board is full.

function solve(board) {
    let emptySpot = nextEmptySpot(board);
    let row = emptySpot[0];
    let col = emptySpot[1];

    // there is no more empty spots
    if (row === -1){
        return board;
    }

    for (let num = 1; num<=9; num++){
        if (checkValue(board, row, col, num)) {
            board[row][col] = num;
            solve(board);
        }
    }

    if (nextEmptySpot(board)[0] !== -1) {
        board[row][col] = 0;
    }

    return board;
}

We are DONE!

What's Next?

At this point, we can think about several ideas to improve our little Sudoku Solver Project. For example, we can be a little more smarter when checking the valid values. We can also think about handling the case of having no solution for the puzzle.

One more idea would be to create an interface to enter the initial Sudoku board, like a command line tool or web app. I think that building a web app would be a great idea and excellent practice.