The importance of backtracking for developpers

Definition

Backtracking is a method used in all programming languages to explore all possible outcomes of a problems.
It can be applied to solve problems like finding paths in a labyrinth, solving the N-Queens problem, Sudoku, and more.

Why is it useful?

Why is backtracking valuable for developers?
Imagine a situation where there are numerous possible outcomes to explore. Do we have the time to check every possibility manually? Obviously not.
We might think of creating a large loop to go through all potential solutions. But can every machine's capacity handle such extensive work? Again, no.

This is where backtracking comes in handy. With this concept, we systematically try each possible solution. If a solution doesn't work, we go back and try another one, continuing until we meet the conditions for success that we’ve defined.

Analogy

Take Sudoku as an example:
Each row must contain numbers from 1 to 9.
Each column must contain numbers from 1 to 9.
Each of the 9 sub-grids (3*3) must contain numbers from 1 to 9.

When solving a Sudoku puzzle, there are empty spaces to fill. To solve it:

1. We create a function to check if a number meets all the rules.
2. After verifying if we can place a number, we proceed to check the possibilities for the remaining empty spaces.
3. If placing a number leads to an invalid solution later, we backtrack, try another number, and repeat the process.

This continues until all spaces are correctly filled and the puzzle is solved.

Principal Steps of Backtracking

1. Choice: Identify all possible solutions for each step and check them one by one.
2. Constraint: Verify if a solution is valid based on the rules.
3. Objective: Determine if a solution satisfies all conditions.
4. Step Back: Backtrack when a solution fails and explore other options.

Example Code: Solving Sudoku with Backtracking with JavaScript

//We start with a partially filled Sudoku board (for empty cells) and we want to find the possible numbers that can be used to fill the board


const board = [
    ["5", "3", ".", "6", "7", "8", "9", "1", "2"],
    ["6", "7", "2", "1", "9", "5", "3", "4", "8"],
    ["1", "9", "8", "3", "4", "2", "5", "6", "7"],
    ["8", "5", "9", "7", "6", "1", "4", "2", "3"],
    ["4", "2", "6", "8", ".", "3", "7", "9", "1"],
    ["7", "1", "3", "9", "2", "4", "8", "5", "6"],
    ["9", "6", "1", "5", "3", "7", "2", "8", "4"],
    ["2", "8", "7", "4", "1", "9", "6", "3", "5"],
    ["3", "4", "5", "2", "8", "6", "1", ".", "9"]
];
//'.' represents an empty cell


// Possible numbers for Sudoku
const possibleNumbers = ["1", "2", "3", "4", "5", "6", "7", "8", "9"];

// Function to check if placing a number is valid
function isValid(number, row, col, board) {
    // Check row and column
    for (let i = 0; i < board.length; i++) {
        if (board[row][i] === number || board[i][col] === number) {
            return false;
        }
    }

    // Check the 3x3 sub-grid
    let startRow = Math.floor(row / 3) * 3;
    let startCol = Math.floor(col / 3) * 3;

    for (let i = startRow; i < startRow + 3; i++) {
        for (let j = startCol; j < startCol + 3; j++) {
            if (board[i][j] === number) {
                return false;
            }
        }
    }

    return true; // The number is valid for this position
}

// Function to solve the Sudoku board
function solveSudoku(board) {
    const emptySpaces = [];

    // Find all empty spaces on the board
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if (board[i][j] === ".") {
                emptySpaces.push({ row: i, col: j });
            }
        }
    }

    // Recursive function to fill empty spaces
    function recurse(emptySpaceIndex) {
        if (emptySpaceIndex >= emptySpaces.length) {
            return true; // All spaces filled successfully
        }

        const { row, col } = emptySpaces[emptySpaceIndex];

        for (let i = 0; i < possibleNumbers.length; i++) {
            const num = possibleNumbers[i];
            if (isValid(num, row, col, board)) {
                board[row][col] = num; // Place the number

                if (recurse(emptySpaceIndex + 1)) {
                    return true; // Solution found
                }

                // Backtrack if placing the number doesn't lead to a solution
                board[row][col] = ".";
            }
        }

        return false; // No valid number found for this position
    }

    recurse(0); // Start solving from the first empty space
    return board;
}

// Solve the Sudoku puzzle
solveSudoku(board);
console.log(board);

Key Points

Backtracking systematically explores all possibilities while adhering to constraints.
It is especially useful for solving constraint-based problems like Sudoku, N-Queens, and more.
The recursive nature of backtracking allows us to step back and try alternate paths when a solution fails.

I hope you are satisfied with my article. I'll be there answering all questions you may have.
If you're satisfied, just leave a ♥️ (It actually means a lot)

For image:Image by storyset on Freepik

Comments

[Wéri Boni]

Here's the output you will get.
[
['5', '3', '4', '6', '7', '8', '9', '1', '2'],
['6', '7', '2', '1', '9', '5', '3', '4', '8'],
['1', '9', '8', '3', '4', '2', '5', '6', '7'],
['8', '5', '9', '7', '6', '1', '4', '2', '3'],
['4', '2', '6', '8', '5', '3', '7', '9', '1'],
['7', '1', '3', '9', '2', '4', '8', '5', '6'],
['9', '6', '1', '5', '3', '7', '2', '8', '4'],
['2', '8', '7', '4', '1', '9', '6', '3', '5'],
['3', '4', '5', '2', '8', '6', '1', '7', '9']
]