简介

给定一个部分填充的9×9二维数组，目标是将数字（从1到9）分配给空单元格，
以便每个行、列包含恰好是从1到9的数字。如下图：

独数

回溯算法

像所有其他回溯问题一样（N皇后问题），数独可以通过为空单元格一一分配数字来解决。在分配号码之前，检查当前行、当前列是否不存在相同的数字。并递归检查此分配是否可行。如果分配有冲突，尝试当前空单元格的下一个数字。如果当前单元格没有一个数字（1 到 9）可安置，则返回false，回溯重试上一个单元个下一个数字。

代码实现（python）

# python

def show(grid):
    for i in range(9):
        for j in range(9):
            print(f'{grid[i][j]} ', end='')
        print()

def get_empty_location(grid):
    for row in range(9):
        for col in range(9):
            if(grid[row][col] == 0):
                return True, row, col
    return False, None, None

def num_in_row(grid, row, num):
    for i in range(9):
        if(grid[row][i] == num):
            return True
    return False

def num_in_col(grid, col, num):
    for i in range(9):
        if(grid[i][col] == num):
            return True
    return False

def is_safe(grid, row, col, num):
    return not num_in_row(grid, row, num) and \
        not num_in_col(grid, col, num)

def solve_sudoku(grid):
    ret, row, col = get_empty_location(grid)
    if not ret:
        return True

    for num in range(1, 10):
        if(is_safe(grid, row, col, num)):
            grid[row][col]= num

            if(solve_sudoku(grid)):
                return True

            grid[row][col] = 0
    # 回溯上个空格的下一个数字
    return False

if __name__=="__main__":
    grid =[[0 for x in range(9)]for y in range(9)]

    grid = [[2, 0, 6, 5, 0, 0, 4, 0, 0],
            [0, 4, 0, 0, 0, 6, 0, 0, 0],
            [0, 8, 7, 0, 0, 0, 0, 3, 1],
            [0, 0, 3, 0, 2, 0, 0, 9, 0],
            [0, 0, 0, 8, 0, 3, 0, 0, 6],
            [0, 5, 0, 0, 9, 0, 6, 0, 0],
            [1, 0, 0, 3, 0, 0, 2, 5, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 4],
            [0, 0, 0, 2, 0, 5, 3, 0, 0]]
    if(solve_sudoku(grid)):
        show(grid)
    else:
        print("solution not exists")

// C

#include <stdio.h>

#define true 1
#define false 0

void show(char grid[][9])
{
    int row, col;

    for (row = 0; row < 9; row++) {
        for (col = 0; col < 9; col++)
            printf("%d  ", grid[row][col]);
        printf("\n");
    }
}

struct point
{
    int row;
    int col;
};

int get_empty_location(char grid[][9], struct point *p)
{
    int row, col;

    p->row = p->col = -1;

    for (row = 0; row < 9; row++)
        for (col = 0; col < 9; col++)
            if(grid[row][col] == 0) {
                p->row = row;
                p->col = col;
                return true;
            }
    return false;
}

int num_in_row(char grid[][9], int row, int num)
{
    int col;

    for (col = 0; col < 9; col++)
        if(grid[row][col] == num)
            return true;
    return false;
}

int num_in_col(char grid[][9], int col, int num)
{
    int row;

    for (row = 0; row < 9; row++)
        if(grid[row][col] == num)
            return true;
    return false;
}

int is_safe(char grid[][9], int row, int col, int num)
{
    return !num_in_row(grid, row, num) &&
           !num_in_col(grid, col, num);
}

int solve_sudoku(char grid[][9])
{
    int num;
    struct point p;

    int ret = get_empty_location(grid, &p);
    if (!ret)
        return true;

    for (num = 1; num <= 9; num++)
        if (is_safe(grid, p.row, p.col, num)) {
            grid[p.row][p.col]= num;

            if(solve_sudoku(grid))
                return true;

            grid[p.row][p.col] = 0;
        }
    // 回溯上个空格的下一个数字
    return false;
}

void main(void)
{
    char grid[][9] =
           {{2, 0, 6, 5, 0, 0, 4, 0, 0},
            {0, 4, 0, 0, 0, 6, 0, 0, 0},
            {0, 8, 7, 0, 0, 0, 0, 3, 1},
            {0, 0, 3, 0, 2, 0, 0, 9, 0},
            {0, 0, 0, 8, 0, 3, 0, 0, 6},
            {0, 5, 0, 0, 9, 0, 6, 0, 0},
            {1, 0, 0, 3, 0, 0, 2, 5, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 4},
            {0, 0, 0, 2, 0, 5, 3, 0, 0}};
    if(solve_sudoku(grid))
        show(grid);
    else
        printf("solution not exists");
}