Leetcode-37 Sudoku Solver

发表于 | 分类于 | 次

Sudoku Solver

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 the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character '.'.

Note:

  • The given board contain only digits 1-9 and the character '.'.
  • You may assume that the given Sudoku puzzle will have a single unique solution.
  • The given board size is always 9x9.

解题思路

回溯法。每个空的格子都有若干选择。只要找到一个合法解就行，因此回溯过程中若找到合法解就直接返回。

复杂度分析

略。

代码

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
class Solution {
public:
	void solveSudoku(vector<vector<char>>& board) {
		backtrack(board, 0, 0);
	}

	bool backtrack(vector<vector<char>>& board, int pi, int pj) {
		if (pi == 9)
			return true;
		if (pj == 9)
			return backtrack(board, pi + 1, 0);
		if (board[pi][pj] != '.')
			return backtrack(board, pi, pj + 1);

		for (char c = '1'; c <= '9'; ++c) {
			if (isValid(board, pi, pj, c)) {
				board[pi][pj] = c;
				if (backtrack(board, pi, pj + 1)) return true;
				board[pi][pj] = '.';
			}
		}
		return false;
	}

	bool isValid(vector<vector<char>>& board, int pi, int pj, char num) {
		for (int i = 0; i < 9; ++i) {
			if (board[i][pj] == num) return false;
			if (board[pi][i] == num) return false;
			if (board[pi / 3 * 3 + i / 3][pj / 3 * 3 + i % 3] == num) return false;
		}
		return true;
	}
};