Leetcode Question: https://leetcode.com/problems/sudoku-solver/

Let's start with why I feel so excited by the fact that I just finished the Leetcode hard problem for sudoku solver. I am a self-taught software engineer and DSA interviews used to be the bane of my existence. I once solved 0/4 questions in a span of 70 minutes for a startup I was interviewing at. I was so ashamed that I never even called the recruiter or manager back to let them know I had finished the OA. I have since spent hundreds of hours programming something every single day, and finishing a Leetcode hard that I broke my brain the first time I heard of in under 67 minutes, without ever looking at the answer, and while watching a movie g felt like a level up in a video game. Here's what I did to figure it out.

In this article I am going to assume you know the rules to Sudoku, and I will take you over my thought process that led me to the solution. From the very start I was aware of the concept of backtracking, I knew that it meant being able to step back into the past decision and change it and continue from there on when you hit a roadblock. Let's continue with this above statement as our understanding of backtracking.

On any given leetcode problem I always start with visualizing and writing my mental algorithm of solving the problem as a human. I identified my mental process to solve a sudoku problem as the following:

1. I look over the cells and at each empty spot I make a decision
2. This decision I make at this spot is to choose a number from all numbers that fit the constraints of sudoku rules.
3. I pick this number, insert it in the empty spot, and continue forward till I come across the next empty spot.
4. At this next empty spot I again calculate all valid possible choices (similar to step 2, hint: scenarios where we make the same decisions almost always point to a recursive approach) and pick the first one.
5. And we continue to the next empty spot.
6. Unless at step 4 we happen to hit a scenario where we have no valid choices to pick from. This scenario indicated that somewhere in picking numbers for our previous empty spots, we picked a number that is wrong.
7. At this point we need to go one step back and try the next possible choice for picking the value for the spot we had previously filled incorrectly. NOTE: Every time we change a value in an empty spot we create different possibilities for valid choices we can pick for the next empty spot, and when we continue making the right choices, we will eventually fill up all empty spots on our board.
8. We keep going back and forth fixing previous steps till all steps are eventually correct.
9. At this point our board is full and we can exit this cycle.

It is incredible how such a simple human task, feels incredibly complex when asked to be converted into a compilable (or interpreted 😂 ) language.

Implementing the mental algorithm in code

The skeleton solution function signature in Typsecript was the following:

function solveSudoku(board: string[][]): void

I had to modify the board in place and not return anything so I made a helper function

function backTrackSolve(board: string[][]): boolean

This function returns a boolean because I call it recursively, and on valid solutions it returns true, and when we hit a state with no valid choices for an empty spot this function returns false. This function is recursive and it's base case is to return true if the board is full. If the board is not full, we iterate over the board and at the first empty spot, we calculate all valid options that can be inserted in this empty spot. If there are no valid options we return false.

With each option from this list of valid options we branch off into a recursive call where the board is now 1 spot less empty, the next call in our call stack will now have go to the next empty step and check if we have valid values or not, if not we return false, else we iterate over every choice and created a recursive call with each, if run out of all choices and none of them lead to a solution we set the current spot back to empty and return false. This tells the caller of the function "Hey, the last value inserted led to an invalid state, try the next value". At this point we have successfully backtracked, in the sense that we have reset our current state, gone back one step and changed the previously put option for valid field, and then continued from there-on.

The code to find all valid choices lives in a separate helper function

function getValidChoices(board: string[][], row: number, col: number) {
    
    const options = ['1','2','3','4','5','6','7','8','9'];
    
    // filter from row scenario
    for(let j of board[row]) {


        if (options.includes(j)) {
            options.splice(options.indexOf(j), 1);
        }
    }
    
    //console.log(options, 'rows filtered');


    // filter from cols scenario
    for (let rowVal = 0; rowVal < board.length; rowVal++) {
        const boardVal = board[rowVal][col];
        if(options.includes(boardVal)) {
            options.splice(options.indexOf(boardVal), 1);
        }
    }
    
    //console.log(options, 'cols filtered');
    
    
    // filter from 3*3 scenario
    const innerMatrix = getInnnerMatrix(board, row, col);
    for (let i = 0; i < innerMatrix.length; i++) {
        for (let j = 0; j < innerMatrix[0].length; j++) {
           const boardVal = innerMatrix[i][j];
            if(options.includes(boardVal)) {
                options.splice(options.indexOf(boardVal), 1);
            }   
        }
    }


    return options;
}

function getInnnerMatrix(board: string[][], row: number, col: number): string[][] {
    const rowMin = Math.floor(row / 3)*3;
    const colMin = Math.floor(col / 3)*3;
    const rowMax = rowMin+3;
    const colMax = colMin+3;
    
    const innerMatrix = [];
    
    for(let i = rowMin; i < rowMax; i++) {
        const innerCol = [];
        for(let j = colMin; j < colMax; j++) {
            innerCol.push(board[i][j]);
        }
        innerMatrix.push(innerCol);
    }
    
    return innerMatrix;
}

Entire Solution in Typescript:

/**
 Do not return anything, modify board in-place instead.
 */
function solveSudoku(board: string[][]): void {
    backTrackSolve(board);
};


function backTrackSolve(board: string[][]): boolean {
    if (boardIsFull(board)) {
        return true;
    }


    for (let row = 0; row < board.length; row++) {
        for (let col = 0; col < board[0].length; col++) {
            if (board[row][col] !== ".") {
                continue;
            }
            
            const validChoices = getValidChoices(board, row, col);
            
            if (validChoices.length === 0) {
                return false;
            }


            for (let choice of validChoices) {
                board[row][col] = choice;
                if (backTrackSolve(board)) {
                    return true;
                }
            }
            
            board[row][col] = '.';
            return false;
        }
    }
    
    return false;
}


function boardIsFull(board: string[][]): boolean {
    for(let row of board) {
        if (row.some(i => i === ".")) {
            return false;
        }
    }
    return true;
}


function getValidChoices(board: string[][], row: number, col: number) {
    
    const options = ['1','2','3','4','5','6','7','8','9'];
    
    // filter from row scenario
    for(let j of board[row]) {


        if (options.includes(j)) {
            options.splice(options.indexOf(j), 1);
        }
    }
    
    //console.log(options, 'rows filtered');


    // filter from cols scenario
    for (let rowVal = 0; rowVal < board.length; rowVal++) {
        const boardVal = board[rowVal][col];
        if(options.includes(boardVal)) {
            options.splice(options.indexOf(boardVal), 1);
        }
    }
    
    //console.log(options, 'cols filtered');
    
    
    // filter from 3*3 scenario
    const innerMatrix = getInnnerMatrix(board, row, col);
    for (let i = 0; i < innerMatrix.length; i++) {
        for (let j = 0; j < innerMatrix[0].length; j++) {
           const boardVal = innerMatrix[i][j];
            if(options.includes(boardVal)) {
                options.splice(options.indexOf(boardVal), 1);
            }   
        }
    }


    return options;
}




function getInnnerMatrix(board: string[][], row: number, col: number): string[][] {
    const rowMin = Math.floor(row / 3)*3;
    const colMin = Math.floor(col / 3)*3;
    const rowMax = rowMin+3;
    const colMax = colMin+3;
    
    const innerMatrix = [];
    
    for(let i = rowMin; i < rowMax; i++) {
        const innerCol = [];
        for(let j = colMin; j < colMax; j++) {
            innerCol.push(board[i][j]);
        }
        innerMatrix.push(innerCol);
    }
    
    return innerMatrix;
}