如果对回溯法理论还不清楚的同学，可以先看这个视频视频来了！！带你学透回溯算法（理论篇）
37. 解数独
编写一个程序，通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。
一个数独。
答案被标成红色。
提示：
- 给定的数独序列只包含数字 1-9 和字符 '.' 。
- 你可以假设给定的数独只有唯一解。
- 给定数独永远是 9x9 形式的。
思路
棋盘搜索问题可以使用回溯法暴力搜索，只不过这次我们要做的是二维递归。
怎么做二维递归呢？
大家已经跟着「代码随想录」刷过了如下回溯法题目，例如：77.组合（组合问题），131.分割回文串（分割问题），78.子集（子集问题），46.全排列（排列问题），以及51.N皇后（N皇后问题），其实这些题目都是一维递归。
如果以上这几道题目没有做过的话，不建议上来就做这道题哈！
N皇后问题是因为每一行每一列只放一个皇后，只需要一层for循环遍历一行，递归来遍历列，然后一行一列确定皇后的唯一位置。
本题就不一样了，本题中棋盘的每一个位置都要放一个数字（而N皇后是一行只放一个皇后），并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。
因为这个树形结构太大了，我抽取一部分，如图所示：
回溯三部曲
- 递归函数以及参数
递归函数的返回值需要是bool类型，为什么呢？
因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用bool返回值。
代码如下：
bool backtracking(vector<vector<char>>& board)
- 递归终止条件
本题递归不用终止条件，解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回。
不用终止条件会不会死循环？
递归的下一层的棋盘一定比上一层的棋盘多一个数，等数填满了棋盘自然就终止（填满当然好了，说明找到结果了），所以不需要终止条件！
那么有没有永远填不满的情况呢？
这个问题我在递归单层搜索逻辑里再来讲！
- 递归单层搜索逻辑
在树形图中可以看出我们需要的是一个二维的递归 （一行一列）
一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！
代码如下：（详细看注释）
bool backtracking(vector<vector<char>>& board) {
for (int i = 0; i < board.size(); i++) { // 遍历行
for (int j = 0; j < board[0].size(); j++) { // 遍历列
if (board[i][j] != '.') continue;
for (char k = '1'; k <= '9'; k++) { // (i, j) 这个位置放k是否合适
if (isValid(i, j, k, board)) {
board[i][j] = k; // 放置k
if (backtracking(board)) return true; // 如果找到合适一组立刻返回
board[i][j] = '.'; // 回溯，撤销k
}
}
return false; // 9个数都试完了，都不行，那么就返回false
}
}
return true; // 遍历完没有返回false，说明找到了合适棋盘位置了
}
注意这里return false的地方，这里放return false 是有讲究的。
因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
那么会直接返回，这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！
判断棋盘是否合法
判断棋盘是否合法有如下三个维度：
- 同行是否重复
- 同列是否重复
- 9宫格里是否重复
代码如下：
bool isValid(int row, int col, char val, vector<vector<char>>& board) {
for (int i = 0; i < 9; i++) { // 判断行里是否重复
if (board[row][i] == val) {
return false;
}
}
for (int j = 0; j < 9; j++) { // 判断列里是否重复
if (board[j][col] == val) {
return false;
}
}
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == val ) {
return false;
}
}
}
return true;
}
最后整体C++代码如下：
class Solution {
private:
bool backtracking(vector<vector<char>>& board) {
for (int i = 0; i < board.size(); i++) { // 遍历行
for (int j = 0; j < board[0].size(); j++) { // 遍历列
if (board[i][j] == '.') {
for (char k = '1'; k <= '9'; k++) { // (i, j) 这个位置放k是否合适
if (isValid(i, j, k, board)) {
board[i][j] = k; // 放置k
if (backtracking(board)) return true; // 如果找到合适一组立刻返回
board[i][j] = '.'; // 回溯，撤销k
}
}
return false; // 9个数都试完了，都不行，那么就返回false
}
}
}
return true; // 遍历完没有返回false，说明找到了合适棋盘位置了
}
bool isValid(int row, int col, char val, vector<vector<char>>& board) {
for (int i = 0; i < 9; i++) { // 判断行里是否重复
if (board[row][i] == val) {
return false;
}
}
for (int j = 0; j < 9; j++) { // 判断列里是否重复
if (board[j][col] == val) {
return false;
}
}
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == val ) {
return false;
}
}
}
return true;
}
public:
void solveSudoku(vector<vector<char>>& board) {
backtracking(board);
}
};
总结
解数独可以说是非常难的题目了，如果还一直停留在单层递归的逻辑中，这道题目可以让大家瞬间崩溃。
所以我在开篇就提到了二维递归，这也是我自创词汇，希望可以帮助大家理解解数独的搜索过程。
一波分析之后，再看代码会发现其实也不难，唯一难点就是理解二维递归的思维逻辑。
这样，解数独这么难的问题，也被我们攻克了。
恭喜一路上坚持打卡的录友们，回溯算法已经接近尾声了，接下来就是要一波总结了。
其他语言版本
- Java
- Python
- Go
- JavaScript
- TypeScript
- Rust
- C
- Swift
- Scala
- C#
解法一:
class Solution {
public void solveSudoku(char[][] board) {
solveSudokuHelper(board);
}
private boolean solveSudokuHelper(char[][] board){
//「一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，
// 一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！」
for (int i = 0; i < 9; i++){ // 遍历行
for (int j = 0; j < 9; j++){ // 遍历列
if (board[i][j] != '.'){ // 跳过原始数字
continue;
}
for (char k = '1'; k <= '9'; k++){ // (i, j) 这个位置放k是否合适
if (isValidSudoku(i, j, k, board)){
board[i][j] = k;
if (solveSudokuHelper(board)){ // 如果找到合适一组立刻返回
return true;
}
board[i][j] = '.';
}
}
// 9个数都试完了，都不行，那么就返回false
return false;
// 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
// 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
}
}
// 遍历完没有返回false，说明找到了合适棋盘位置了
return true;
}
/**
* 判断棋盘是否合法有如下三个维度:
* 同行是否重复
* 同列是否重复
* 9宫格里是否重复
*/
private boolean isValidSudoku(int row, int col, char val, char[][] board){
// 同行是否重复
for (int i = 0; i < 9; i++){
if (board[row][i] == val){
return false;
}
}
// 同列是否重复
for (int j = 0; j < 9; j++){
if (board[j][col] == val){
return false;
}
}
// 9宫格里是否重复
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++){
for (int j = startCol; j < startCol + 3; j++){
if (board[i][j] == val){
return false;
}
}
}
return true;
}
}
解法二(bitmap标记)
class Solution{
int[] rowBit = new int[9];
int[] colBit = new int[9];
int[] square9Bit = new int[9];
public void solveSudoku(char[][] board) {
// 1 10 11
for (int y = 0; y < board.length; y++) {
for (int x = 0; x < board[y].length; x++) {
int numBit = 1 << (board[y][x] - '1');
rowBit[y] ^= numBit;
colBit[x] ^= numBit;
square9Bit[(y / 3) * 3 + x / 3] ^= numBit;
}
}
backtrack(board, 0);
}
public boolean backtrack(char[][] board, int n) {
if (n >= 81) {
return true;
}
// 快速算出行列编号 n/9 n%9
int row = n / 9;
int col = n % 9;
if (board[row][col] != '.') {
return backtrack(board, n + 1);
}
for (char c = '1'; c <= '9'; c++) {
int numBit = 1 << (c - '1');
if (!isValid(numBit, row, col)) continue;
{
board[row][col] = c; // 当前的数字放入到数组之中，
rowBit[row] ^= numBit; // 第一行rowBit[0],第一个元素eg: 1 , 0^1=1,第一个元素:4, 100^1=101,...
colBit[col] ^= numBit;
square9Bit[(row / 3) * 3 + col / 3] ^= numBit;
}
if (backtrack(board, n + 1)) return true;
{
board[row][col] = '.'; // 不满足条件，回退成'.'
rowBit[row] &= ~numBit; // 第一行rowBit[0],第一个元素eg: 1 , 101&=~1==>101&111111110==>100
colBit[col] &= ~numBit;
square9Bit[(row / 3) * 3 + col / 3] &= ~numBit;
}
}
return false;
}
boolean isValid(int numBit, int row, int col) {
// 左右
if ((rowBit[row] & numBit) > 0) return false;
// 上下
if ((colBit[col] & numBit) > 0) return false;
// 9宫格: 快速算出第n个九宫格,编号[0,8] , 编号=(row / 3) * 3 + col / 3
if ((square9Bit[(row / 3) * 3 + col / 3] & numBit) > 0) return false;
return true;
}
}
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
row_used = [set() for _ in range(9)]
col_used = [set() for _ in range(9)]
box_used = [set() for _ in range(9)]
for row in range(9):
for col in range(9):
num = board[row][col]
if num == ".":
continue
row_used[row].add(num)
col_used[col].add(num)
box_used[(row // 3) * 3 + col // 3].add(num)
self.backtracking(0, 0, board, row_used, col_used, box_used)
def backtracking(
self,
row: int,
col: int,
board: List[List[str]],
row_used: List[List[int]],
col_used: List[List[int]],
box_used: List[List[int]],
) -> bool:
if row == 9:
return True
next_row, next_col = (row, col + 1) if col < 8 else (row + 1, 0)
if board[row][col] != ".":
return self.backtracking(
next_row, next_col, board, row_used, col_used, box_used
)
for num in map(str, range(1, 10)):
if (
num not in row_used[row]
and num not in col_used[col]
and num not in box_used[(row // 3) * 3 + col // 3]
):
board[row][col] = num
row_used[row].add(num)
col_used[col].add(num)
box_used[(row // 3) * 3 + col // 3].add(num)
if self.backtracking(
next_row, next_col, board, row_used, col_used, box_used
):
return True
board[row][col] = "."
row_used[row].remove(num)
col_used[col].remove(num)
box_used[(row // 3) * 3 + col // 3].remove(num)
return False
func solveSudoku(board [][]byte) {
var backtracking func(board [][]byte) bool
backtracking = func(board [][]byte) bool {
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
//判断此位置是否适合填数字
if board[i][j] != '.' {
continue
}
//尝试填1-9
for k := '1'; k <= '9'; k++ {
if isvalid(i, j, byte(k), board) == true { //如果满足要求就填
board[i][j] = byte(k)
if backtracking(board) == true {
return true
}
board[i][j] = '.'
}
}
return false
}
}
return true
}
backtracking(board)
}
//判断填入数字是否满足要求
func isvalid(row, col int, k byte, board [][]byte) bool {
for i := 0; i < 9; i++ { //行
if board[row][i] == k {
return false
}
}
for i := 0; i < 9; i++ { //列
if board[i][col] == k {
return false
}
}
//方格
startrow := (row / 3) * 3
startcol := (col / 3) * 3
for i := startrow; i < startrow+3; i++ {
for j := startcol; j < startcol+3; j++ {
if board[i][j] == k {
return false
}
}
}
return true
}
var solveSudoku = function(board) {
function isValid(row, col, val, board) {
let len = board.length
// 行不能重复
for(let i = 0; i < len; i++) {
if(board[row][i] === val) {
return false
}
}
// 列不能重复
for(let i = 0; i < len; i++) {
if(board[i][col] === val) {
return false
}
}
let startRow = Math.floor(row / 3) * 3
let startCol = Math.floor(col / 3) * 3
for(let i = startRow; i < startRow + 3; i++) {
for(let j = startCol; j < startCol + 3; j++) {
if(board[i][j] === val) {
return false
}
}
}
return true
}
function backTracking() {
for(let i = 0; i < board.length; i++) {
for(let j = 0; j < board[0].length; j++) {
if(board[i][j] !== '.') continue
for(let val = 1; val <= 9; val++) {
if(isValid(i, j, `${val}`, board)) {
board[i][j] = `${val}`
if (backTracking()) {
return true
}
board[i][j] = `.`
}
}
return false
}
}
return true
}
backTracking(board)
return board
};
/**
Do not return anything, modify board in-place instead.
*/
function isValid(col: number, row: number, val: string, board: string[][]): boolean {
let n: number = board.length;
// 列向检查
for (let rowIndex = 0; rowIndex < n; rowIndex++) {
if (board[rowIndex][col] === val) return false;
}
// 横向检查
for (let colIndex = 0; colIndex < n; colIndex++) {
if (board[row][colIndex] === val) return false;
}
// 九宫格检查
const startX = Math.floor(col / 3) * 3;
const startY = Math.floor(row / 3) * 3;
for (let rowIndex = startY; rowIndex < startY + 3; rowIndex++) {
for (let colIndex = startX; colIndex < startX + 3; colIndex++) {
if (board[rowIndex][colIndex] === val) return false;
}
}
return true;
}
function solveSudoku(board: string[][]): void {
let n: number = 9;
backTracking(n, board);
function backTracking(n: number, board: string[][]): boolean {
for (let row = 0; row < n; row++) {
for (let col = 0; col < n; col++) {
if (board[row][col] === '.') {
for (let i = 1; i <= n; i++) {
if (isValid(col, row, String(i), board)) {
board[row][col] = String(i);
if (backTracking(n, board) === true) return true;
board[row][col] = '.';
}
}
return false;
}
}
}
return true;
}
};
impl Solution {
fn is_valid(row: usize, col: usize, val: char, board: &mut Vec<Vec<char>>) -> bool{
for i in 0..9 {
if board[row][i] == val { return false; }
}
for j in 0..9 {
if board[j][col] == val {
return false;
}
}
let start_row = (row / 3) * 3;
let start_col = (col / 3) * 3;
for i in start_row..(start_row + 3) {
for j in start_col..(start_col + 3) {
if board[i][j] == val { return false; }
}
}
return true;
}
fn backtracking(board: &mut Vec<Vec<char>>) -> bool{
for i in 0..board.len() {
for j in 0..board[0].len() {
if board[i][j] != '.' { continue; }
for k in '1'..='9' {
if Self::is_valid(i, j, k, board) {
board[i][j] = k;
if Self::backtracking(board) { return true; }
board[i][j] = '.';
}
}
return false;
}
}
return true;
}
pub fn solve_sudoku(board: &mut Vec<Vec<char>>) {
Self::backtracking(board);
}
}
bool isValid(char** board, int row, int col, int k) {
/* 判断当前行是否有重复元素 */
for (int i = 0; i < 9; i++) {
if (board[i][col] == k) {
return false;
}
}
/* 判断当前列是否有重复元素 */
for (int j = 0; j < 9; j++) {
if (board[row][j] == k) {
return false;
}
}
/* 计算当前9宫格左上角的位置 */
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
/* 判断当前元素所在九宫格是否有重复元素 */
for (int i = startRow; i < startRow + 3; i++) {
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == k) {
return false;
}
}
}
/* 满足条件，返回true */
return true;
}
bool backtracking(char** board, int boardSize, int* boardColSize) {
/* 从上到下、从左到右依次遍历输入数组 */
for (int i = 0; i < boardSize; i++) {
for (int j = 0; j < *boardColSize; j++) {
/* 遇到数字跳过 */
if (board[i][j] != '.') {
continue;
}
/* 依次将数组1到9填入当前位置 */
for (int k = '1'; k <= '9'; k++) {
/* 判断当前位置是否与满足条件，是则进入下一层 */
if (isValid(board, i, j, k)) {
board[i][j] = k;
/* 判断下一层递归之后是否找到一种解法，是则返回true */
if (backtracking(board, boardSize, boardColSize)) {
return true;
}
/* 回溯，将当前位置清零 */
board[i][j] = '.';
}
}
/* 若填入的9个数均不满足条件，返回false，说明此解法无效 */
return false;
}
}
/* 遍历完所有的棋盘，没有返回false，说明找到了解法，返回true */
return true;
}
void solveSudoku(char** board, int boardSize, int* boardColSize) {
bool res = backtracking(board, boardSize, boardColSize);
}
func solveSudoku(_ board: inout [[Character]]) {
// 判断对应格子的值是否合法
func isValid(row: Int, col: Int, val: Character) -> Bool {
// 行中是否重复
for i in 0 ..< 9 {
if board[row][i] == val { return false }
}
// 列中是否重复
for j in 0 ..< 9 {
if board[j][col] == val { return false }
}
// 9方格内是否重复
let startRow = row / 3 * 3
let startCol = col / 3 * 3
for i in startRow ..< startRow + 3 {
for j in startCol ..< startCol + 3 {
if board[i][j] == val { return false }
}
}
return true
}
@discardableResult
func backtracking() -> Bool {
for i in 0 ..< board.count { // i：行坐标
for j in 0 ..< board[0].count { // j：列坐标
guard board[i][j] == "." else { continue } // 跳过已填写格子
// 填写格子
for val in 1 ... 9 {
let charVal = Character("\(val)")
guard isValid(row: i, col: j, val: charVal) else { continue } // 跳过不合法的
board[i][j] = charVal // 填写
if backtracking() { return true }
board[i][j] = "." // 回溯：擦除
}
return false // 遍历完数字都不行
}
}
return true // 没有不合法的，填写正确
}
backtracking()
}
详细写法：
object Solution {
def solveSudoku(board: Array[Array[Char]]): Unit = {
backtracking(board)
}
def backtracking(board: Array[Array[Char]]): Boolean = {
for (i <- 0 until 9) {
for (j <- 0 until 9) {
if (board(i)(j) == '.') { // 必须是为 . 的数字才放数字
for (k <- '1' to '9') { // 这个位置放k是否合适
if (isVaild(i, j, k, board)) {
board(i)(j) = k
if (backtracking(board)) return true // 找到了立刻返回
board(i)(j) = '.' // 回溯
}
}
return false // 9个数都试完了，都不行就返回false
}
}
}
true // 遍历完所有的都没返回false，说明找到了
}
def isVaild(x: Int, y: Int, value: Char, board: Array[Array[Char]]): Boolean = {
// 行
for (i <- 0 until 9 ) {
if (board(i)(y) == value) {
return false
}
}
// 列
for (j <- 0 until 9) {
if (board(x)(j) == value) {
return false
}
}
// 宫
var row = (x / 3) * 3
var col = (y / 3) * 3
for (i <- row until row + 3) {
for (j <- col until col + 3) {
if (board(i)(j) == value) {
return false
}
}
}
true
}
}
遵循Scala至简原则写法：
object Solution {
def solveSudoku(board: Array[Array[Char]]): Unit = {
backtracking(board)
}
def backtracking(board: Array[Array[Char]]): Boolean = {
// 双重for循环 + 循环守卫
for (i <- 0 until 9; j <- 0 until 9 if board(i)(j) == '.') {
// 必须是为 . 的数字才放数字，使用循环守卫判断该位置是否可以放置当前循环的数字
for (k <- '1' to '9' if isVaild(i, j, k, board)) { // 这个位置放k是否合适
board(i)(j) = k
if (backtracking(board)) return true // 找到了立刻返回
board(i)(j) = '.' // 回溯
}
return false // 9个数都试完了，都不行就返回false
}
true // 遍历完所有的都没返回false，说明找到了
}
def isVaild(x: Int, y: Int, value: Char, board: Array[Array[Char]]): Boolean = {
// 行，循环守卫进行判断
for (i <- 0 until 9 if board(i)(y) == value) return false
// 列，循环守卫进行判断
for (j <- 0 until 9 if board(x)(j) == value) return false
// 宫，循环守卫进行判断
var row = (x / 3) * 3
var col = (y / 3) * 3
for (i <- row until row + 3; j <- col until col + 3 if board(i)(j) == value) return false
true // 最终没有返回false，就说明该位置可以填写true
}
}
public class Solution
{
public void SolveSudoku(char[][] board)
{
BackTracking(board);
}
public bool BackTracking(char[][] board)
{
for (int i = 0; i < board.Length; i++)
{
for (int j = 0; j < board[0].Length; j++)
{
if (board[i][j] != '.') continue;
for (char k = '1'; k <= '9'; k++)
{
if (IsValid(board, i, j, k))
{
board[i][j] = k;
if (BackTracking(board)) return true;
board[i][j] = '.';
}
}
return false;
}
}
return true;
}
public bool IsValid(char[][] board, int row, int col, char val)
{
for (int i = 0; i < 9; i++)
{
if (board[i][col] == val) return false;
}
for (int i = 0; i < 9; i++)
{
if (board[row][i] == val) return false;
}
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++)
{
for (int j = startCol; j < startCol + 3; j++)
{
if (board[i][j] == val) return false;
}
}
return true;
}
}