代码实践：如何用 C、Java 和 Python 中的回溯求解数独问题？

#include <stdio.h>
#define SIZE 9
//数独问题int matrix[9][9] = {    {6,5,0,8,7,3,0,9,0},    {0,0,3,2,5,0,0,0,8},    {9,8,0,1,0,4,3,5,7},    {1,0,5,0,0,0,0,0,0},    {4,0,0,0,0,0,0,0,2},    {0,0,0,0,0,0,5,0,3},    {5,7,8,3,0,1,0,2,6},    {2,0,0,0,4,8,9,0,0},    {0,9,0,6,2,5,0,8,1}};
//该方法用于打印数独void print_sudoku(){    int i,j;    for(i=0;i<SIZE;i++)    {        for(j=0;j<SIZE;j++)        {            printf("%d\t",matrix[i][j]);        }        printf("\n\n");    }}
//该方法用于检查是否还有未赋值的单元格//如果有未赋值的单元格//那么这个方法将相应地修改行和列的值int number_unassigned(int *row, int *col){    int num_unassign = 0;    int i,j;    for(i=0;i<SIZE;i++)    {        for(j=0;j<SIZE;j++)        {            //单元格未被赋值            if(matrix[i][j] == 0)            {                //修改行和列的值                *row = i;                *col = j;                //有一个或多个未赋值的单元格                num_unassign = 1;                return num_unassign;            }        }    }    return num_unassign;}
// 该方法用于检查是否可以填写一个// 值到对应的单元格中int is_safe(int n, int r, int c){    int i,j;    //检查行    for(i=0;i<SIZE;i++)    {        //某个单元格具有相同值        if(matrix[r][i] == n)            return 0;    }    //检查列    for(i=0;i<SIZE;i++)    {        //某个单元格的值等于i        if(matrix[i][c] == n)            return 0;    }    //检查子矩阵    int row_start = (r/3)*3;    int col_start = (c/3)*3;    for(i=row_start;i<row_start+3;i++)    {        for(j=col_start;j<col_start+3;j++)        {            if(matrix[i][j]==n)                return 0;        }    }    return 1;}
//该方法用回溯来求解数独问题int solve_sudoku(){    int row;    int col;    //如果所有单元格都被赋值了的，那么数独问题已经通过引用被求解了；    //因为number_unassigned将修改    if(number_unassigned(&row, &col) == 0)        return 1;    int n,i;    //1到9之间的数字    for(i=1;i<=SIZE;i++)    {        //是否可以将i赋值给单元格        //单元格是matrix[row][col]        if(is_safe(i, row, col))        {            matrix[row][col] = i;            //回溯            if(solve_sudoku())                return 1;            //如果我们不能继续求解这个问题            //重新赋值单元            matrix[row][col]=0;        }    }    return 0;}
int main(){    if (solve_sudoku())        print_sudoku();    else        printf("No solution\n");    return 0;}

class Sudoku{
    private static final int SIZE = 9;    private static int[][] matrix = {        {6,5,0,8,7,3,0,9,0},        {0,0,3,2,5,0,0,0,8},        {9,8,0,1,0,4,3,5,7},        {1,0,5,0,0,0,0,0,0},        {4,0,0,0,0,0,0,0,2},        {0,0,0,0,0,0,5,0,3},        {5,7,8,3,0,1,0,2,6},        {2,0,0,0,4,8,9,0,0},        {0,9,0,6,2,5,0,8,1}    };
    private static void printSudoku()    {        for(int i=0;i<SIZE;i++)        {            for(int j=0;j<SIZE;j++)            {                System.out.print(matrix[i][j]+"\t");            }            System.out.println("");        }    }
    //该方法用于检查是否还有未赋值的单元格    //如果有未赋值的单元格    //那么这个方法将相应地修改行和列的值    private static int[] numberUnassigned(int row, int col)    {        int numunassign = 0;        for(int i=0;i<SIZE;i++)        {            for(int j=0;j<SIZE;j++)            {                //单元格未被赋值                if(matrix[i][j] == 0)                {                    //修改行和列的值                    row = i;                    col = j;                    //有一个或多个未赋值的单元格                    numunassign = 1;                    int[] a = {numunassign, row, col};                    return a;                }            }        }        int[] a = {numunassign, -1, -1};        return a;    }
    //该方法用于检查是否可以填写一个    //值到对应的单元格中    private static boolean isSafe(int n, int r, int c)    {        //检查行        for(int i=0;i<SIZE;i++)        {            //某个单元格具有相同值            if(matrix[r][i] == n)                return false;        }        //检查列        for(int i=0;i<SIZE;i++)        {            //某个单元格的值等于i            if(matrix[i][c] == n)                return false;        }        //检查子矩阵        int row_start = (r/3)*3;        int col_start = (c/3)*3;        for(int i=row_start;i<row_start+3;i++)        {            for(int j=col_start;j<col_start+3;j++)            {                if(matrix[i][j]==n)                    return false;            }        }        return true;    }
    //该方法用回溯来求解数独问题    private static boolean solveSudoku()    {        int row=0;        int col=0;        int[] a = numberUnassigned(row, col);        //如果所有单元格都被赋值了的，那么数独问题已经通过引用被求解了；        //因为number_unassigned将修改行和列的值        if(a[0] == 0)            return true;        //用1到9之间的数字        row = a[1];        col = a[2];        for(int i=1;i<=SIZE;i++)        {            //是否可以将i赋值给单元格            //单元格是matrix[row][col]            if(isSafe(i, row, col))            {                matrix[row][col] = i;                //回溯                if(solveSudoku())                    return true;                //如果我们不能继续求解这个问题                //重新赋值单元                matrix[row][col]=0;            }        }        return false;    }
    public static void main(String[] args)    {        if (solveSudoku())            printSudoku();        else            System.out.println("No solution");    }}

SIZE = 9#数独问题#值为0的单元格为空单元格matrix = [    [6,5,0,8,7,3,0,9,0],    [0,0,3,2,5,0,0,0,8],    [9,8,0,1,0,4,3,5,7],    [1,0,5,0,0,0,0,0,0],    [4,0,0,0,0,0,0,0,2],    [0,0,0,0,0,0,5,0,3],    [5,7,8,3,0,1,0,2,6],    [2,0,0,0,4,8,9,0,0],    [0,9,0,6,2,5,0,8,1]]#该方法用于打印数独def print_sudoku():    for i in matrix:        print (i)
#该方法用于检查是否还有未赋值的单元格#如果有未赋值的单元格#那么这个方法将相应地修改行和列的值def number_unassigned(row, col):    num_unassign = 0    for i in range(0,SIZE):        for j in range (0,SIZE):            #单元格未被赋值            if matrix[i][j] == 0:                row = i                col = j                num_unassign = 1                a = [row, col, num_unassign]                return a    a = [-1, -1, num_unassign]    return a#该方法用于检查是否可以填写一个#值到对应的单元格中def is_safe(n, r, c):    #检查行    for i in range(0,SIZE):        #某个单元格具有相同值        if matrix[r][i] == n:            return False    #检查列    for i in range(0,SIZE):        #某个单元格有相同的值        if matrix[i][c] == n:            return False    row_start = (r//3)*3    col_start = (c//3)*3;    #检查子矩阵    for i in range(row_start,row_start+3):        for j in range(col_start,col_start+3):            if matrix[i][j]==n:                return False    return True
#该方法用回溯来求解数独问题def solve_sudoku():    row = 0    col = 0    #如果所有单元格都被赋值了的，那么数独问题已经通过引用被求解了；    #因为number_unassigned将修改行和列的值    a = number_unassigned(row, col)    if a[2] == 0:        return True    row = a[0]    col = a[1]    #1到9之间的数字    for i in range(1,10):        #是否可以将i赋值给单元格        #单元格是matrix[row][col]        if is_safe(i, row, col):            matrix[row][col] = i            #回溯            if solve_sudoku():                return True            #如果我们不能继续求解这个问题            #重新赋值单元            matrix[row][col]=0    return False
if solve_sudoku():    print_sudoku()else:    print("No solution")