Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Recursion & Backtracking

Sudoku Solver

Hard · Recursion & Backtracking · Asked at Amazon, Microsoft, Google, Uber

Fill the empty cells (.) so that every row, every column and every 3×3 box contains the digits 1–9 exactly once. If the puzzle has more than one solution, print the one found by filling the empty cells row by row, left to right, trying digits 1 to 9 in increasing order (classic backtracking).

Input

9 lines of 9 characters each (1–9 or .).

Output

The solved grid: 9 lines of 9 digits.

Constraints

Backtracking: find the next empty cell, try each digit that does not clash with its row, column and box, recurse, and undo on failure. Boolean arrays for rows/columns/boxes make the clash check O(1).

Example 1

Input

53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79

Output

534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

Example 2

Input

..395.847
.842...6.
596..4231
9..4....2
.3..91..8
845327...
...7.81..
.78.62.9.
...54...3

Output

123956847
784213965
596874231
961485372
237691458
845327619
459738126
378162594
612549783

Hints

  1. Keep three boolean tables: digit d used in row r, in column c, and in box (r/3)*3 + c/3.
  2. Fill the empty cells in row-major order. For each, try digits 1..9 that are free in its row, column and box; recurse; undo on failure.

Approach

Classic backtracking. Read the grid and mark the given digits in row, col and box tables. go(pos) (pos = 0..80) skips filled cells; for an empty cell it tries d = 1..9 in increasing order where all three tables allow it, places d, marks the tables, and recurses; if the recursion fails, it unmarks and tries the next digit. The first full grid found is printed — trying digits in increasing order makes the answer unique even if the puzzle has several solutions.

Complexity: Exponential in the number of blanks in the worst case, fast for normal puzzles · O(81) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int g[9][9];
bool rowU[9][10], colU[9][10], boxU[9][10];

bool go(int pos) {
    if (pos == 81) return true;
    int r = pos / 9, c = pos % 9, b = (r / 3) * 3 + c / 3;
    if (g[r][c]) return go(pos + 1);
    for (int d = 1; d <= 9; d++) {
        if (rowU[r][d] || colU[c][d] || boxU[b][d]) continue;
        g[r][c] = d;
        rowU[r][d] = colU[c][d] = boxU[b][d] = true;
        if (go(pos + 1)) return true;
        rowU[r][d] = colU[c][d] = boxU[b][d] = false;
        g[r][c] = 0;
    }
    return false;
}

int main() {
    for (int r = 0; r < 9; r++) {
        string line;
        cin >> line;
        for (int c = 0; c < 9; c++) {
            g[r][c] = line[c] == '.' ? 0 : line[c] - '0';
            if (g[r][c]) rowU[r][g[r][c]] = colU[c][g[r][c]] = boxU[(r / 3) * 3 + c / 3][g[r][c]] = true;
        }
    }
    go(0);
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) cout << g[r][c];
        cout << "\n";
    }
    return 0;
}

Python solution

import sys

lines = sys.stdin.read().split()
g = [[0 if ch == "." else int(ch) for ch in lines[r]] for r in range(9)]
row = [[False] * 10 for _ in range(9)]
col = [[False] * 10 for _ in range(9)]
box = [[False] * 10 for _ in range(9)]
for r in range(9):
    for c in range(9):
        d = g[r][c]
        if d:
            row[r][d] = col[c][d] = box[(r // 3) * 3 + c // 3][d] = True
empty = [(r, c) for r in range(9) for c in range(9) if g[r][c] == 0]


def go(i):
    if i == len(empty):
        return True
    r, c = empty[i]
    b = (r // 3) * 3 + c // 3
    for d in range(1, 10):
        if row[r][d] or col[c][d] or box[b][d]:
            continue
        g[r][c] = d
        row[r][d] = col[c][d] = box[b][d] = True
        if go(i + 1):
            return True
        row[r][d] = col[c][d] = box[b][d] = False
        g[r][c] = 0
    return False


go(0)
print("\n".join("".join(map(str, rw)) for rw in g))

Java solution

import java.util.*;

public class Main {
    static int[][] g = new int[9][9];
    static boolean[][] rowU = new boolean[9][10], colU = new boolean[9][10], boxU = new boolean[9][10];

    static boolean go(int pos) {
        if (pos == 81) return true;
        int r = pos / 9, c = pos % 9, b = (r / 3) * 3 + c / 3;
        if (g[r][c] != 0) return go(pos + 1);
        for (int d = 1; d <= 9; d++) {
            if (rowU[r][d] || colU[c][d] || boxU[b][d]) continue;
            g[r][c] = d;
            rowU[r][d] = colU[c][d] = boxU[b][d] = true;
            if (go(pos + 1)) return true;
            rowU[r][d] = colU[c][d] = boxU[b][d] = false;
            g[r][c] = 0;
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int r = 0; r < 9; r++) {
            String line = sc.next();
            for (int c = 0; c < 9; c++) {
                g[r][c] = line.charAt(c) == '.' ? 0 : line.charAt(c) - '0';
                if (g[r][c] != 0) rowU[r][g[r][c]] = colU[c][g[r][c]] = boxU[(r / 3) * 3 + c / 3][g[r][c]] = true;
            }
        }
        go(0);
        StringBuilder sb = new StringBuilder();
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) sb.append(g[r][c]);
            sb.append('\n');
        }
        System.out.print(sb);
    }
}

Solve Sudoku Solver online · All practice problems