Skip to content

37. Sudoku Solver

Description

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

 

Example 1:

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:

 

Constraints:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit or '.'.
  • It is guaranteed that the input board has only one solution.

Solutions

Solution 1: Backtracking

We use arrays row, col, and box to record whether a number has appeared in each row, each column, and each 3x3 grid respectively. If the number i has appeared in the rth row, the cth column, and the bth 3x3 grid, then row[r][i], col[c][i], and box[b][i] are all true.

We traverse each empty space in board, enumerate the numbers v that it can fill in. If v has not appeared in the current row, the current column, and the current 3x3 grid, then we can try to fill in the number v and continue to search for the next empty space. If we search to the end and all spaces are filled, it means that a feasible solution has been found.

The time complexity is $O(9^{81})$, and the space complexity is $O(9^2)$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        def dfs(k):
            nonlocal ok
            if k == len(t):
                ok = True
                return
            i, j = t[k]
            for v in range(9):
                if row[i][v] == col[j][v] == block[i // 3][j // 3][v] == False:
                    row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True
                    board[i][j] = str(v + 1)
                    dfs(k + 1)
                    row[i][v] = col[j][v] = block[i // 3][j // 3][v] = False
                if ok:
                    return

        row = [[False] * 9 for _ in range(9)]
        col = [[False] * 9 for _ in range(9)]
        block = [[[False] * 9 for _ in range(3)] for _ in range(3)]
        t = []
        ok = False
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    t.append((i, j))
                else:
                    v = int(board[i][j]) - 1
                    row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True
        dfs(0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    private boolean ok;
    private char[][] board;
    private List<Integer> t = new ArrayList<>();
    private boolean[][] row = new boolean[9][9];
    private boolean[][] col = new boolean[9][9];
    private boolean[][][] block = new boolean[3][3][9];

    public void solveSudoku(char[][] board) {
        this.board = board;
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    t.add(i * 9 + j);
                } else {
                    int v = board[i][j] - '1';
                    row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
                }
            }
        }
        dfs(0);
    }

    private void dfs(int k) {
        if (k == t.size()) {
            ok = true;
            return;
        }
        int i = t.get(k) / 9, j = t.get(k) % 9;
        for (int v = 0; v < 9; ++v) {
            if (!row[i][v] && !col[j][v] && !block[i / 3][j / 3][v]) {
                row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
                board[i][j] = (char) (v + '1');
                dfs(k + 1);
                row[i][v] = col[j][v] = block[i / 3][j / 3][v] = false;
            }
            if (ok) {
                return;
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
using pii = pair<int, int>;

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        bool row[9][9] = {false};
        bool col[9][9] = {false};
        bool block[3][3][9] = {false};
        bool ok = false;
        vector<pii> t;
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    t.push_back({i, j});
                } else {
                    int v = board[i][j] - '1';
                    row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
                }
            }
        }
        function<void(int k)> dfs = [&](int k) {
            if (k == t.size()) {
                ok = true;
                return;
            }
            int i = t[k].first, j = t[k].second;
            for (int v = 0; v < 9; ++v) {
                if (!row[i][v] && !col[j][v] && !block[i / 3][j / 3][v]) {
                    row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
                    board[i][j] = v + '1';
                    dfs(k + 1);
                    row[i][v] = col[j][v] = block[i / 3][j / 3][v] = false;
                }
                if (ok) {
                    return;
                }
            }
        };
        dfs(0);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func solveSudoku(board [][]byte) {
    var row, col [9][9]bool
    var block [3][3][9]bool
    var t [][2]int
    ok := false
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if board[i][j] == '.' {
                t = append(t, [2]int{i, j})
            } else {
                v := int(board[i][j] - '1')
                row[i][v], col[j][v], block[i/3][j/3][v] = true, true, true
            }
        }
    }
    var dfs func(int)
    dfs = func(k int) {
        if k == len(t) {
            ok = true
            return
        }
        i, j := t[k][0], t[k][1]
        for v := 0; v < 9; v++ {
            if !row[i][v] && !col[j][v] && !block[i/3][j/3][v] {
                row[i][v], col[j][v], block[i/3][j/3][v] = true, true, true
                board[i][j] = byte(v + '1')
                dfs(k + 1)
                row[i][v], col[j][v], block[i/3][j/3][v] = false, false, false
            }
            if ok {
                return
            }
        }
    }
    dfs(0)
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
public class Solution {
    public void SolveSudoku(char[][] board) {
        this.board = new ushort?[9,9];
        for (var i = 0; i < 9; ++i)
        {
            for (var j = 0; j < 9; ++j)
            {
                if (board[i][j] != '.')
                {
                    this.board[i, j] = (ushort) (1 << (board[i][j] - '0' - 1));
                }
            }
        }

        if (SolveSudoku(0, 0))
        {
            for (var i = 0; i < 9; ++i)
            {
                for (var j = 0; j < 9; ++j)
                {
                    if (board[i][j] == '.')
                    {
                        board[i][j] = '0';
                        while (this.board[i, j].Value != 0)
                        {
                            board[i][j] = (char)(board[i][j] + 1);
                            this.board[i, j] >>= 1;
                        }
                    }
                }
            }
        }
    }

    private ushort?[,] board;

    private bool ValidateHorizontalRule(int row)
    {
        ushort temp = 0;
        for (var i = 0; i < 9; ++i)
        {
            if (board[row, i].HasValue)
            {
                if ((temp | board[row, i].Value) == temp)
                {
                    return false;
                }
                temp |= board[row, i].Value;
            }
        }
        return true;
    }

    private bool ValidateVerticalRule(int column)
    {
        ushort temp = 0;
        for (var i = 0; i < 9; ++i)
        {
            if (board[i, column].HasValue)
            {
                if ((temp | board[i, column].Value) == temp)
                {
                    return false;
                }
                temp |= board[i, column].Value;
            }
        }
        return true;
    }

    private bool ValidateBlockRule(int row, int column)
    {
        var startRow = row / 3 * 3;
        var startColumn = column / 3 * 3;
        ushort temp = 0;
        for (var i = startRow; i < startRow + 3; ++i)
        {
            for (var j = startColumn; j < startColumn + 3; ++j)
            {
                if (board[i, j].HasValue)
                {
                    if ((temp | board[i, j].Value) == temp)
                    {
                        return false;
                    }
                    temp |= board[i, j].Value;
                }
            }
        }
        return true;
    }

    private bool SolveSudoku(int i, int j)
    {
        while (true)
        {
            if (j == 9)
            {
                ++i;
                j = 0;
            }
            if (i == 9)
            {
                return true;
            }
            if (board[i, j].HasValue)
            {
                ++j;
            }
            else
            {
                break;
            }
        }

        ushort stop = 1 << 9;
        for (ushort t = 1; t != stop; t <<= 1)
        {
            board[i, j] = t;
            if (ValidateHorizontalRule(i) && ValidateVerticalRule(j) && ValidateBlockRule(i, j))
            {
                if (SolveSudoku(i, j + 1))
                {
                    return true;
                }
            }
        }
        board[i, j] = null;
        return false;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution {
    /**
     * @param string[][] $board
     * @return bool
     */

    public function solveSudoku(&$board) {
        if (isSolved($board)) {
            return true;
        }

        $emptyCell = findEmptyCell($board);
        $row = $emptyCell[0];
        $col = $emptyCell[1];

        for ($num = 1; $num <= 9; $num++) {
            if (isValid($board, $row, $col, $num)) {
                $board[$row][$col] = (string) $num;
                if ($this->solveSudoku($board)) {
                    return true;
                }
                $board[$row][$col] = '.';
            }
        }
        return false;
    }
}

function isSolved($board) {
    foreach ($board as $row) {
        if (in_array('.', $row)) {
            return false;
        }
    }
    return true;
}

function findEmptyCell($board) {
    for ($row = 0; $row < 9; $row++) {
        for ($col = 0; $col < 9; $col++) {
            if ($board[$row][$col] === '.') {
                return [$row, $col];
            }
        }
    }

    return null;
}

function isValid($board, $row, $col, $num) {
    for ($i = 0; $i < 9; $i++) {
        if ($board[$row][$i] == $num) {
            return false;
        }
    }

    for ($i = 0; $i < 9; $i++) {
        if ($board[$i][$col] == $num) {
            return false;
        }
    }

    $startRow = floor($row / 3) * 3;
    $endCol = floor($col / 3) * 3;

    for ($i = 0; $i < 3; $i++) {
        for ($j = 0; $j < 3; $j++) {
            if ($board[$startRow + $i][$endCol + $j] == $num) {
                return false;
            }
        }
    }

    return true;
}

Comments