Search⌘ K
Home
Courses
Decode the Coding Interview in JavaScript: Real-World Examples

Sudoku Solver

Explore how to solve Sudoku puzzles by filling empty cells using backtracking and constraint programming in JavaScript. Understand how to check rows, columns, and 3x3 sub-boxes to place digits correctly. This lesson guides you through the step-by-step algorithm, helping you build a solver that backtracks when a placement fails, enabling you to handle complex Sudoku scenarios efficiently.

We'll cover the following...

Description

Write a program to solve Sudoku by filling the empty cells. We will be given a 2D array representing a Sudoku puzzle. For a correct solution each of the digits 1-9 must only occur once in each:

  • Row
  • Column
  • Nine 3x3 sub-boxes of the grid

Let us take a look at an example:

To solve the puzzle, we will only fill the empty cells. Empty cells are represented by a ‘.’. The array will be passed by reference, so we will not need to return it after solving the puzzle.

Coding exercise

Javascript (babel-node)
function solveSudoku(board) {
    // Write your code here
    
    return ''
}
Sudoku solver exercise

Solution

While solving Sudoku, we will have to take care of two things. First, we place a number at an empty place. The number must not be present in that row, column, or sub-box. So, we will use constrained programming to keep track of which number we can place in a box and which not. Second, let us assume that we have filled a few empty places but, the choice of numbers was not optimal, ...