Sudoku Solver

HardPremium

Write a function sudokuSolve that checks whether a given sudoku board is solvable. If so, the function returns true. Otherwise (i.e. there is no valid solution to the given sudoku board), it returns false.

Context:

In sudoku, the objective is to fill a 9x9 board with digits so that each column, each row, and each of the nine 3x3 sub-boards that compose the board contains all of the digits from 1 to 9. The board setter provides a partially completed board, which for a well-posed board has a unique solution.

As explained above, for this problem, it suffices to calculate whether a given sudoku board has a solution. No need to return the actual numbers that make up a solution.

A sudoku board is represented as a two-dimensional 9x9 array of the characters '1', '2', ..., '9' and the '.' character, which represents a blank space. The function should fill the blank spaces with characters such that the following rules apply:

In every row of the array, all characters '1', '2', ..., '9' appear exactly once.
In every column of the array, all characters '1', '2', ..., '9' appear exactly once.
In every 3x3 sub-board that is illustrated below, all characters '1', '2', ..., '9' appear exactly once.

A solved sudoku is a board with no blank spaces, i.e. all blank spaces are filled with characters that abide by the constraints above. If the function succeeds in solving the sudoku board, it'll return true (false, otherwise).

Example (more examples can be found here):

A typical Sudoku board

A typical Sudoku board setter

The same board with solution numbers marked in red

Be sure to write readable and efficient code, explain how your solution is built and why you chose to build it that way.

Try a brute force solution first and then optimize.

Let's restate the question. At a high level, your function should choose an empty cell and place values inside. If some placed value makes sudokuSolve(board) true, then the answer is true - otherwise, the answer is false.

If your solution is choosing the empty cell naively, consider which choice of empty cell would be best. We want to minimize work later.

Have you figured out how to identify the best choices for empty cells? The best choice is that with the fewest possible answers because in the worst case, we'll have to check sudokuSolve(board) the least number of times. You might consider writing a helper function getCandidates that gets the possible values some cell board[r][c] could be.

If you're still stuck, here's a skeleton to get you started.


function getCandidates(board, row, col):
  # What values can be placed in empty cell board[row][col] ?
 
function sudokuSolve(board):
  # For each empty cell (row, col):
  #   If (row, col) has fewer candidate values that can be placed
  #   in board[row][col]than we've seen, remember it
 
  # If there's no empty cell:
  #   return true
 
  # For candidate values v of our remembered row, col:
  #   board[row][col] = v
  #   if solve(board): 
  #     return true
    
  # return false

The main idea for the solution is using a recursive algorithm that iterates through the empty cell on the board, and on the possible candidate numbers for each empty cell, and tries to fill them, as the following code scheme:


# A helper function that returns a set of all valid
# candidates for a given cell in the board

function getCandidates(board, row, col):
    # For some empty cell board[row][col], what possible
    # characters can be placed into this cell
    # that aren't already placed in the same row,
    # column, and sub-board?

    # At the beginning, we don't have any candidates
    candidates = []

    # For each character add it to the candidate list
    # only if there's no collision, i.e. that character
    # doesn't already exist in the same row, column
    # and sub-board. Notice the top-left corner of (row, col)'s
    # sub-board is (row - row%3, col - col%3).
    for chr from '1' to '9':
        collision = false;
        for i from 0 to 8:
            if (board[row][i] == chr ||
                board[i][col] == chr ||
                board[(row - row % 3) + floor(i / 3)][(col - col % 3) + i % 3] == chr):
                    collision = true
                    break

        if (!collision):
            candidates.push(chr)

    return candidates

function sudokuSolve(board):
    # For each empty cell, consider 'newCandidates', the
    # set of possible candidate values that can
    # be placed into that cell.

    row = -1
    col = -1
    candidates = null

    for r from 0 to 8:
        for c from 0 to 8:
            if (board[r][c] == '.'):
                newCandidates = getCandidates(board, r, c)
                # Then, we want to keep the smallest
                # sized 'newCandidates', plus remember the
                # position where it was found
                if (candidates == null OR newCandidates.size() < candidates.size()):
                    candidates = newCandidates
                    row = r
                    col = c

    # If we have not found any empty cell, then
    # the whole board is filled already
    if (candidates == null):
        return true

    # For each possible value that can be placed
    # in position (row, col), let's
    # place that value and then recursively query
    # whether the board can be solved.  If it can,
    # we are done.
    for val in candidates:
        board[row][col] = val
        if (sudokuSolve(board)):
            return true
        # The tried value val didn't work so restore
        # the (row, col) cell back to '.'
        board[row][col] = '.'

    # Otherwise, there is no value that can be placed
    # into position (row, col) to make the
    # board solved
    return false

Determining the time and space complexity of this problem is tricky. Technically, because the size of the sudoku board is fixed, the asymptotic behavior of our algorithm is capped and therefore both are constant. However, in practice, it is clear that the runtime of our solution can be heavily optimized (for example, by selecting the empty cell to test that has the fewest possible candidates).

def get_candidates(board, row, col):
    candidates = []

    for chr in '123456789':
        collision = False
        for i in range(9):
            if (board[row][i] == chr or
                board[i][col] == chr or
                board[(row - row % 3) + i // 3][(col - col % 3) + i % 3] == chr):
                collision = True
                break

        if not collision:
            candidates.append(chr)

    return candidates

def sudoku_solve(board):
    row, col, candidates = -1, -1, None

    for r in range(9):
        for c in range(9):
            if board[r][c] == '.':
                new_candidates = get_candidates(board, r, c)
                if candidates is None or len(new_candidates) < len(candidates):
                    candidates = new_candidates
                    row, col = r, c

    if candidates is None:
        return True

    for val in candidates:
        board[row][col] = val
        if sudoku_solve(board):
            return True
        board[row][col] = '.'

    return False

Community solutions

💬 Community guidelines

Stay on topic. Use this section for submitting solutions and providing feedback to others.
Be inclusive. Exponent is a diverse community. Please respect others' opinions and beliefs.

How would you answer? Submit your response below and get feedback from the community.

Divya R.805

March 20, 2025

static boolean sudokuSolve(char[][] board) { return sudokuSolve(board, 0, 0); } static boolean sudokuSolve(char[][] board, int r, int c) { if(c>=board[0].length) { r=r+1; c=0; } if(r>=board.length) return true; if(board[r][c]=='.') { for(int num=1; num<=9; num++) { board[r][c]=(char)('0' + num); if(isValidPosition(board, r, c)) { if(sudokuSolve(board, r, c+1)) return true; } board[r][c]='.'; } } else { return sudokuSolve(board, r, c+1); } return false; } static boolean isValidPosition(char[][] board, int r, int c) { int number=board[r][c]; //col check for(int i=0; i<board[0].length; i++) { if(i!=c && board[r][i]==board[r][c]) return false; } //row check for(int i=0; i<board.length; i++) { if(i!=r && board[i][c]==board[r][c]) return false; } //square check int startRow=(r/3)*3; int startCol=(c/3)*3; for(int i=startRow; i<startRow+3; i++) { for(int j=startCol; j<startCol+3; j++) { if(i!=r && j!=c && board[i][j]==board[r][c]) return false; } } return true; }

Jordan C.

Coach

102

May 26, 2025

Using backtracking...

Python

from typing import List

def sudoku_solve(board: List[List[str]]) -> bool:
    """
    Using backtracking
    
    Args:
        board: 9x9 grid where '.' represents empty cells and '1'-'9' represent filled cells
        
    Returns:
        True if the board is solvable, otherwise False
    """
    
    def is_valid(board, row, col, num):
        # Check row - no duplicate in the same row
        for j in range(9):
            if board[row][j] == num:
                return False
        
        # Check column - no duplicate in the same column
        for i in range(9):
            if board[i][col] == num:
                return False
        
        # Check 3x3 box - no duplicate in the same 3x3 subgrid
        box_row = (row // 3) * 3
        box_col = (col // 3) * 3
        
        for i in range(box_row, box_row + 3):
            for j in range(box_col, box_col + 3):
                if board[i][j] == num:
                    return False
        
        return True
    
    def solve(board):
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    # valid digits 1-9
                    for num in '123456789':
                        if is_valid(board, i, j, num):
                            board[i][j] = num
                            
                            if solve(board):
                                return True

                            board[i][j] = '.'
                    
                    return False
        
        return True
    
    board_copy = [row[:] for row in board]
    
    for i in range(9):
        for j in range(9):
            if board_copy[i][j] != '.':
                temp = board_copy[i][j]
                board_copy[i][j] = '.'
                if not is_valid(board_copy, i, j, temp):
                    return False
                board_copy[i][j] = temp
    
    return solve(board_copy)


board = [
    [".", ".", ".", "7", ".", ".", "3", ".", "1"],
    ["3", ".", ".", "9", ".", ".", ".", ".", "."],
    [".", "4", ".", "3", "1", ".", "2", ".", "."],
    [".", "6", ".", "4", ".", ".", "5", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", "1", ".", ".", "8", ".", "4", "."],
    [".", ".", "6", ".", "2", "1", ".", "5", "."],
    [".", ".", ".", ".", ".", "9", ".", ".", "8"],
    ["8", ".", "5", ".", ".", "4", ".", ".", "."]
]

print(sudoku_solve(board))

Aman M.402

September 25, 2025

C++

#include <iostream> // include input/output stream
#include <vector>   // include vector library

using namespace std; // use standard namespace

// Helper function to check if placing num at (row, col) is valid
bool isValid(vector<vector<char>>& board, int row, int col, char num) {
    // check row
    for (int i = 0; i < 9; i++) { // loop through columns
        if (board[row][i] == num) // if num already in row
            return false; // not valid
    }
    // check column
    for (int i = 0; i < 9; i++) { // loop through rows
        if (board[i][col] == num) // if num already in column
            return false; // not valid
    }
    // check 3x3 box
    int startRow = row - row % 3; // get starting row of box
    int startCol = col - col % 3; // get starting col of box
    for (int i = 0; i < 3; i++) { // loop through box rows
        for (int j = 0; j < 3; j++) { // loop through box cols
            if (board[startRow + i][startCol + j] == num) // if num in box
                return false; // not valid
        }
    }
    return true; // valid placement
}

// Backtracking function to solve the board
bool solve(vector<vector<char>>& board) {
    for (int row = 0; row < 9; row++) { // loop through rows
        for (int col = 0; col < 9; col++) { // loop through columns
            if (board[row][col] == '.') { // if cell is empty
                for (char num = '1'; num <= '9'; num++) { // try all numbers
                    if (isValid(board, row, col, num)) { // if valid
                        board[row][col] = num; // place number
                        if (solve(board)) // recursively solve rest
                            return true; // if solved, return true
                        board[row][col] = '.'; // backtrack
                    }
                }
                return false; // if no number fits, return false
            }
        }
    }
    return true; // all cells filled, board is solvable
}

// Main function to check if board is solvable
bool sudokuSolve(const vector<vector<char>>& board) {
    vector<vector<char>> copy = board; // make a copy to avoid modifying input
    return solve(copy); // try to solve and return result
}



// comment out main() before running tests
int main() {
    // debug your code below
    vector<vector<char>> board = {
        {'.', '.', '.', '7', '.', '.', '3', '.', '1'},
        {'3', '.', '.', '9', '.', '.', '.', '.', '.'},
        {'.', '4', '.', '3', '1', '.', '2', '.', '.'},
        {'.', '6', '.', '4', '.', '.', '5', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '1', '.', '.', '8', '.', '4', '.'},
        {'.', '.', '6', '.', '2', '1', '.', '5', '.'},
        {'.', '.', '.', '.', '.', '9', '.', '.', '8'},
        {'8', '.', '5', '.', '.', '4', '.', '.', '.'}
    };

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

zeek

Member

190

January 9, 2026

It seems like the tests are broken for Java. There are no expected values for all the tests.

See community answers

Next Lesson

ML Engineer Introduction

ML System Design Questions

Overview

Mock Interviews & Practice Questions

ML Concepts Questions

Overview

Model & Algorithm Fundamentals

Mock Interviews

ML Coding Questions

Overview

Mock Interviews & Practice Questions

Software Engineering Coding Questions

Overview

Fast Track

Time & Space Complexity

Coding Patterns

Arrays

Hash Tables

Searching & Sorting

String Manipulation

Graphs

Trees

Stacks & Queues

Linked Lists

Heaps

Recursion & Backtracking

Dynamic Programming

Behavioral Interviews: A Practical Guide for Engineers

Fast Track (Start Here)

Theory

Tactics

Mock Interviews & Analyses

Practice

ML Engineer Introduction

ML System Design Questions

Overview

Mock Interviews & Practice Questions

ML Concepts Questions

Overview

Model & Algorithm Fundamentals

Mock Interviews

ML Coding Questions

Overview

Mock Interviews & Practice Questions

Software Engineering Coding Questions

Overview

Fast Track

Time & Space Complexity

Coding Patterns

Arrays

Hash Tables

Searching & Sorting

String Manipulation

Graphs

Trees

Stacks & Queues

Linked Lists

Heaps

Recursion & Backtracking

Dynamic Programming

Behavioral Interviews: A Practical Guide for Engineers

Fast Track (Start Here)

Theory

Tactics

Mock Interviews & Analyses

Practice

Sudoku Solver