Sudoku Solver
In this page:
Sudoku Basics
Sudoku is played on a 9x9 grid divided into nine 3x3 boxes, and a valid solution fills every cell with digits 1 through 9 such that no digit repeats in any row, column, or box. Solving it algorithmically is a direct application of backtracking over a heavily constrained grid.
Example: Sudoku Basics
#include <iostream>
using namespace std;
int main() {
cout << "A 9x9 grid split into nine 3x3 boxes, digits 1-9, no repeats in any row/col/box";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("A 9x9 grid split into nine 3x3 boxes, digits 1-9, no repeats in any row/col/box");
}
}print("A 9x9 grid split into nine 3x3 boxes, digits 1-9, no repeats in any row/col/box")#include <stdio.h>
int main() {
printf("A 9x9 grid split into nine 3x3 boxes, digits 1-9, no repeats in any row/col/box");
return 0;
}Login to try C/C++/Java code in the editor
Safe Cell
A digit is safe to place in a cell only if it doesn't already appear elsewhere in that cell's row, that cell's column, or that cell's 3x3 box — all three checks have to pass before a digit is considered valid there.
Example: Safe Cell
#include <iostream>
using namespace std;
bool isSafe(int grid[9][9], int row, int col, int num) {
for (int i = 0; i < 9; i++) if (grid[row][i] == num || grid[i][col] == num) return false;
int br = row - row % 3, bc = col - col % 3;
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
if (grid[br + i][bc + j] == num) return false;
return true;
}
int main() {
int grid[9][9] = {0};
grid[0][1] = 5;
cout << (isSafe(grid, 0, 3, 5) ? "Safe" : "Not safe");
return 0;
}public class Main {
static boolean isSafe(int[][] grid, int row, int col, int num) {
for (int i = 0; i < 9; i++) if (grid[row][i] == num || grid[i][col] == num) return false;
int br = row - row % 3, bc = col - col % 3;
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
if (grid[br + i][bc + j] == num) return false;
return true;
}
public static void main(String[] args) {
int[][] grid = new int[9][9];
grid[0][1] = 5;
System.out.println(isSafe(grid, 0, 3, 5) ? "Safe" : "Not safe");
}
}def is_safe(grid, row, col, num):
for i in range(9):
if grid[row][i] == num or grid[i][col] == num:
return False
br, bc = row - row % 3, col - col % 3
for i in range(3):
for j in range(3):
if grid[br + i][bc + j] == num:
return False
return True
grid = [[0] * 9 for _ in range(9)]
grid[0][1] = 5
print("Safe" if is_safe(grid, 0, 3, 5) else "Not safe")#include <stdio.h>
int isSafe(int grid[9][9], int row, int col, int num) {
for (int i = 0; i < 9; i++) if (grid[row][i] == num || grid[i][col] == num) return 0;
int br = row - row % 3, bc = col - col % 3;
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
if (grid[br + i][bc + j] == num) return 0;
return 1;
}
int main() {
int grid[9][9] = {0};
grid[0][1] = 5;
printf(isSafe(grid, 0, 3, 5) ? "Safe" : "Not safe");
return 0;
}Login to try C/C++/Java code in the editor
Backtracking Solver
The solver scans for the next empty cell, tries each safe digit for it, and recurses to fill the rest of the grid; if a branch leads to a state where the remaining puzzle can't be completed, it undoes the digit and tries the next one. This mirrors the general backtracking pattern of choose, recurse, undo.
Example: Backtracking Solver
#include <iostream>
using namespace std;
bool isSafe(int grid[9][9], int row, int col, int num) {
for (int i = 0; i < 9; i++) if (grid[row][i] == num || grid[i][col] == num) return false;
int br = row - row % 3, bc = col - col % 3;
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
if (grid[br + i][bc + j] == num) return false;
return true;
}
bool solve(int grid[9][9], int row, int col) {
if (row == 9) return true;
if (col == 9) return solve(grid, row + 1, 0);
if (grid[row][col] != 0) return solve(grid, row, col + 1);
for (int num = 1; num <= 9; num++) {
if (isSafe(grid, row, col, num)) {
grid[row][col] = num;
if (solve(grid, row, col + 1)) return true;
grid[row][col] = 0;
}
}
return false;
}
int main() {
int grid[9][9] = {0};
cout << (solve(grid, 0, 0) ? "Solved" : "No solution");
return 0;
}public class Main {
static boolean isSafe(int[][] grid, int row, int col, int num) {
for (int i = 0; i < 9; i++) if (grid[row][i] == num || grid[i][col] == num) return false;
int br = row - row % 3, bc = col - col % 3;
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
if (grid[br + i][bc + j] == num) return false;
return true;
}
static boolean solve(int[][] grid, int row, int col) {
if (row == 9) return true;
if (col == 9) return solve(grid, row + 1, 0);
if (grid[row][col] != 0) return solve(grid, row, col + 1);
for (int num = 1; num <= 9; num++) {
if (isSafe(grid, row, col, num)) {
grid[row][col] = num;
if (solve(grid, row, col + 1)) return true;
grid[row][col] = 0;
}
}
return false;
}
public static void main(String[] args) {
int[][] grid = new int[9][9];
System.out.println(solve(grid, 0, 0) ? "Solved" : "No solution");
}
}def is_safe(grid, row, col, num):
for i in range(9):
if grid[row][i] == num or grid[i][col] == num:
return False
br, bc = row - row % 3, col - col % 3
for i in range(3):
for j in range(3):
if grid[br + i][bc + j] == num:
return False
return True
def solve(grid, row, col):
if row == 9:
return True
if col == 9:
return solve(grid, row + 1, 0)
if grid[row][col] != 0:
return solve(grid, row, col + 1)
for num in range(1, 10):
if is_safe(grid, row, col, num):
grid[row][col] = num
if solve(grid, row, col + 1):
return True
grid[row][col] = 0
return False
grid = [[0] * 9 for _ in range(9)]
print("Solved" if solve(grid, 0, 0) else "No solution")#include <stdio.h>
int isSafe(int grid[9][9], int row, int col, int num) {
for (int i = 0; i < 9; i++) if (grid[row][i] == num || grid[i][col] == num) return 0;
int br = row - row % 3, bc = col - col % 3;
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
if (grid[br + i][bc + j] == num) return 0;
return 1;
}
int solve(int grid[9][9], int row, int col) {
if (row == 9) return 1;
if (col == 9) return solve(grid, row + 1, 0);
if (grid[row][col] != 0) return solve(grid, row, col + 1);
for (int num = 1; num <= 9; num++) {
if (isSafe(grid, row, col, num)) {
grid[row][col] = num;
if (solve(grid, row, col + 1)) return 1;
grid[row][col] = 0;
}
}
return 0;
}
int main() {
int grid[9][9] = {0};
printf(solve(grid, 0, 0) ? "Solved" : "No solution");
return 0;
}Login to try C/C++/Java code in the editor
Validation
A properly completed Sudoku grid must simultaneously satisfy uniqueness across every row, every column, and every 3x3 box — validating a finished (or partially finished) grid means running these same three checks everywhere rather than trusting that the solver got it right.
Example: Validation
#include <iostream>
using namespace std;
bool rowHasDuplicate(int row[9]) {
bool seen[10] = {false};
for (int i = 0; i < 9; i++) {
if (row[i] != 0) {
if (seen[row[i]]) return true;
seen[row[i]] = true;
}
}
return false;
}
int main() {
int row[9] = {5, 3, 0, 0, 7, 0, 0, 0, 5};
cout << (rowHasDuplicate(row) ? "Invalid row" : "Valid row");
return 0;
}public class Main {
static boolean rowHasDuplicate(int[] row) {
boolean[] seen = new boolean[10];
for (int v : row) {
if (v != 0) {
if (seen[v]) return true;
seen[v] = true;
}
}
return false;
}
public static void main(String[] args) {
int[] row = {5, 3, 0, 0, 7, 0, 0, 0, 5};
System.out.println(rowHasDuplicate(row) ? "Invalid row" : "Valid row");
}
}def row_has_duplicate(row):
seen = set()
for v in row:
if v != 0:
if v in seen:
return True
seen.add(v)
return False
row = [5, 3, 0, 0, 7, 0, 0, 0, 5]
print("Invalid row" if row_has_duplicate(row) else "Valid row")#include <stdio.h>
int rowHasDuplicate(int row[9]) {
int seen[10] = {0};
for (int i = 0; i < 9; i++) {
if (row[i] != 0) {
if (seen[row[i]]) return 1;
seen[row[i]] = 1;
}
}
return 0;
}
int main() {
int row[9] = {5, 3, 0, 0, 7, 0, 0, 0, 5};
printf(rowHasDuplicate(row) ? "Invalid row" : "Valid row");
return 0;
}Login to try C/C++/Java code in the editor
Practice
Sudoku ties together three ideas from earlier in this course: recursive backtracking to try and undo choices, constraint checking to prune invalid branches early, and careful bookkeeping to track which digits are already used in each row, column, and box.
Example: Practice
#include <iostream>
using namespace std;
int main() {
cout << "Sudoku combines backtracking, constraint checking, and pruning to fill the grid";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Sudoku combines backtracking, constraint checking, and pruning to fill the grid");
}
}print("Sudoku combines backtracking, constraint checking, and pruning to fill the grid")#include <stdio.h>
int main() {
printf("Sudoku combines backtracking, constraint checking, and pruning to fill the grid");
return 0;
}Login to try C/C++/Java code in the editor
🔒
Chapter Quiz — Complete all 7 topics to unlock
0/7 topics done
Complete these topics first: