创作背景

小学的时候玩过数独，在假期里做了好多数独题，初中的时候有一个同学给我发了一个特别难的数独题，是一个数学家出的，还据说有一个农民只花了一天的时间就做出来了。当时那个数独题实在是太难了，做到一定程度就感觉没有线索了。

后来大学之后学了编程，我就在想，可以自己写一个破解数独的程序来，让程序破解数独。于是我就自己想了一种算法，一个一个数字的往下测试，不通过就撤回，不通过就继续测试下一个数，最终破解的方法。

大一结束，疫情时代，暑假在家的时候做的，未参考任何数独破解相关资料就直接埋头做出来的。

效果截图

草稿思路

结果

合影留念

源代码

Java版

 import  Java .util.ArrayList;
import java.util.Scanner;

/**
 * 破解数独的程序，java版
 * 此程序要求使用者自己手动写入一个9*9标准数独，然后程序会对其破解
 * 2020年7月19日
 * @author littlefean
 */public class Sudoku {

    public static void main(String[] args) {
        int[][][] sudokuBox = newTemp();
        printSudoku(sudokuBox);
        startWrite(sudokuBox);
        printSudokuWithBorder(sudokuBox);
        crack(su do kuBox);
        printSudokuWithBorder(sudokuBox);
    }

    /**
     * 新创一个数独三维数组，返回这个三维数组
     * 数独的数据结构是一个三维数组，
     * 其中第一维度是行，
     * 第二维度是列，
     * 第三维度是这个数的信息，含有两个元素，【数字，是否可写（0 1表示）】
     * @return 返回这个三维数组
     */    private static int[][][] newTemp(){
        int[][][] box = new int[9][9][2];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                box[i][j] = new int[]{0, 1};
            }
        }
        //System.out.println(Arrays.deepToString(box));
        return box;
    }

    /**
     * 打印数独三维数组
     */    private static void printSudoku(int[][][] box){
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    for (int m = 0; m < 3; m++) {
                        System.out.print(box[i*3+j][k*3+m][0]+" ");
                    }
                    System.out.print("  ");
                }
                System.out.println();
            }
            System.out.println();
        }
    }

    /**
     * 以含有边框的形式打印数独
     * @param box 数独的三维数组
     */    private static void printSudokuWithBorder(int[][][] box){
        System.out.println("┏━━━━━━━┳━━━━━━━┳━━━━━━━┓");
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                System.out.print("┃ ");
                for (int k = 0; k < 3; k++) {
                    for (int m = 0; m < 3; m++) {
                        System.out.print(box[i*3+j][k*3+m][0] + " ");
                    }
                    System.out.print("┃ ");
                }
                if(j != 3-1){
                    System.out.println();
                }
            }
            if(i != 3-1){
                System.out.println("n┣━━━━━━━╋━━━━━━━╋━━━━━━━┫");
            }
        }
        System.out.println("n┗━━━━━━━┻━━━━━━━┻━━━━━━━┛");
    }

    /**
     * 开始出题
     * 传入数独数组，并要求用户输入数据对其内容进行修改
     * 注意：该函数直接改变了三维数组参数的状态，所以不用返回值
     * 注意：该函数没有处理输入异常，用户需要自觉输入整数
     * @param box 空数独
     *
     */    private static void startWrite(int[][][] box){
        Scanner sc = new Scanner(System.in);
        System.out.println("提示：0表示空白位置，如果想删除某个位置的数，可以在输入数字的时候输入0，并覆盖相应的位置");
        System.out.println("请输入数独中已知数的数量：");
        int num = sc.nextInt();
        for (int i = 0; i < num; i++) {
            System.out.print("请输入第"+i+1+"个数的数字：");
            int number = sc.nextInt();
            System.out.print("数字在第几行？");
            int y = sc.nextInt();
            System.out.println("第几列？");
            int x = sc.nextInt();
            box[y-1][x-1][0] = number;
            box[y-1][x-1][1] = 0;
        }
        sc.close();
    }

    /**
     * 判断整个数独是不是合法的，如果是，返回True，反之 False 。
     * @param box 数独三维数组
     * @return 如果是，返回True，反之False
     */    private static boolean isTrue(int[][][] box){
        //判断所有行
        for (int i = 0; i < 9; i++) {
            //遍历每一行：
            for (int j = 0; j < 9; j++) {
                //遍历1-9数字，看是否重复
                int num = j + 1;
                int numTimes = 0;
                for (int k = 0; k < 9; k++) {
                    //遍历一行里的9个位置：
                    if(box[i][k][0] == num){
                        numTimes++;
                    }
                }
                if(numTimes>1){
                    return false;
                }
            }
        }
        //判断所有列
        for (int i = 0; i < 9; i++) {
            //遍历每一列：
            for (int j = 0; j < 9; j++) {
                //遍历1-9数字，看是否超过1：
                int num = j + 1;
                int numTimes = 0;
                for (int k = 0; k < 9; k++) {
                    //遍历一列里的9个位置：
                    if(box[k][i][0] == num){
                        numTimes++;
                    }
                }
                if(numTimes>1){
                    return false;
                }
            }
        }
        //判断所有宫
        for (int i = 0; i < 3; i++) {
            //遍历每一行宫
            for (int j = 0; j < 3; j++) {
                //在每一行宫里遍历每一个宫
                for (int k = 0; k < 9; k++) {
                    //在每一个宫里遍历每一个数字：
                    int num = k + 1;
                    int numTimes = 0;
                    for (int m = 0; m < 3; m++) {
                        //在每一个宫里遍历3行
                        for (int n = 0; n < 3; n++) {
                            //在每一个宫的每一行里遍历三个位置：
                            if(box[i*3+m][j*3+n][0] == num){
                                numTimes++;
                            }
                        }
                    }
                    if(numTimes>1){
                        return false;
                    }
                }
            }
        }
        return true;
    }

    /**
     * 破解数独
     * 输入一个数独三维数组，修改数独三维数组的内容使其成为一个完整的正确的数独三维数组
     * 若发现无解则直接退出程序。
     * 注意：此函数直接修改了数独的状态
     * @param box 数独三维数组
     */    private static void crack(int[][][] box){

        //int[][] writeArray = new int[81][2];
        //writeArray不知道多长，只能用集合表示
        ArrayList<int[]> writeArray = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if(box[i][j][1] == 1){
                    //在集合中增加box[i][j]这个数
                    writeArray.add(box[i][j]);
                }
            }
        }
        int x = 0;
        int n = 1;
        while(true){
            //writeArray[x][0] = n; 编译器说这样不行
            //Array type expected; found: 'java.util.ArrayList<int[]>'
            writeArray.get(x)[0] = n;
            if(isTrue(box)){
                if(x == writeArray.size()-1){
                    System.out.println("破解成功");
                     break ;
                }else{
                    x++;
                    n=1;
                }
            }else{
                while(true){
                    if(n >= 9){
                        if(x == 0){
                            System.out.println("无解");
                            System.exit(1);
                        }else{
                            writeArray.get(x)[0] = 0;
                            x --;
                            n = writeArray.get(x)[0];
                            n++;
                        }
                    }else{
                        n++;
                        break;
                    }
                }
            }
        }
    }
}  

python版

 """
破解数独-成功版
尝试破解标准数独，重新开始写代码
数独结构：
    [ [], [], [], [], [], [], [], [], [] ]
        [][][][][][][][][]
            [num, False]    num表示此位置的数字，后面表示是是否可被更改
2020年7月8日 写好了全局判断函数
2020年7月18日 写好了破解函数，可以开始破解了
by littlefean
"""


def newTemp():
    """
    创建一个空数独
    调用该函数会返回一个9*9的二维列表，每个元素都是一个数字元素
    :return:
    """
    array = []
    for i in range(9):
        array.append([])
        for j in range(9):
            array[i].append([0, True])
    return array


# 这个函数在逻辑上是调用api的人写的，个人建议放在下面，即api函数应放一起，这个函数要单独放
def startWrite(array):
    """开始出题"""
    num = int(input("请输入初始数的数量："))
    for i in range(num):
        print(f"请输入第{i+1}个数")

        num = int(input("您要输入的数字是多少？"))
        y = int(input("输入的数字在第几行？"))
        x = int(input("第几列？"))
        array[y - 1][x - 1][0] = num
        array[y - 1][x - 1][1] = False
        printSudokuTable(array)
    choice = input("数据输入完毕，开始破解输入1，修改输入数据请输入任意……")
    if choice != '1':
        while True:
            num = int(input("您要修改的数字是多少？"))
            y = int(input("输入的数字在第几行？"))
            x = int(input("第几列？"))
            array[y - 1][x - 1][0] = num
            array[y - 1][x - 1][1] = False
            printSudokuTable(array)
            do = input("是否开始破解？是请输入1，否则输入任意：")
            if do == '1':
                break
    return array


def isTrue(array):
    """
    传入一个数独二维列表，判断其是否合法，若合法则返回真，否则返回假
    :param array: 表示数独的二维列表
    :return:
    """
    # 判断所有行
    for i in range(9):
        # 遍历每一行：
        for j in range(9):
            # 遍历1-9数字，看是否超过1：
            num = j + 1
            numTimes = 0
            for k in range(9):
                # 遍历一行里的9个位置：
                if array[i][k][0] == num:
                    numTimes += 1
            if numTimes > 1:
                return False

    # 判断所有列
    for i in range(9):
        # 遍历每一列：
        for j in range(9):
            # 遍历1-9数字，看是否超过1：
            num = j + 1
            numTimes = 0
            for k in range(9):
                # 遍历一列里的9个位置：
                if array[k][i][0] == num:
                    numTimes += 1
            if numTimes > 1:
                return False

    # 判断所有宫
    for i in range(3):
        # 遍历每一行宫
        # y = i * 3
        for j in range(3):
            # 在每一行宫里遍历每一个宫
            # x = i * 3
            for k in range(9):
                # 在每一个宫里遍历每一个数字：
                num = k + 1
                numTimes = 0
                for m in range(3):
                    # 在每一个宫里遍历3行
                    # y += m
                    for n in range(3):
                        # 在每一个宫的每一行里遍历三个位置：
                        # x += n
                        # if array[y][x][0] == num:
                        if array[i * 3 + m][j * 3 + n][0] == num:
                            numTimes += 1
                if numTimes > 1:
                    return False
    return True


def printSudoku(array):
    """打印数独"""
    for i in range(3):
        # 三个大横段
        for j in range(3):
            # 三横行紧凑
            for k in range(3):
                # 横行里每三个数
                for m in range(3):
                    # 每一个数
                    print(array[i*3+j][k*3+m][0], end=" ")
                print('  ', end="")
            print()
        print()


def printSudokuTable(array):
    """打印当前整个数独--有边框的方式"""
    print("┏━━━━━━━┳━━━━━━━┳━━━━━━━┓")
    for i in range(3):
        # 三个大横段
        for j in range(3):
            # 每一行
            print('┃ ', end="")
            for k in range(3):
                # 横行里每个组
                for m in range(3):
                    # 每一个数
                    print(array[i*3+j][k*3+m][0], end=" ")
                print('┃ ', end="")
            if j != 3-1:
                print('')
        if i != 3-1:
            print()
            print("┣━━━━━━━╋━━━━━━━╋━━━━━━━┫")
    print()
    print("┗━━━━━━━┻━━━━━━━┻━━━━━━━┛")


def crack(soduArray):
    """破解数独"""
    # 先建立一个一维数组，存放数独可写位置
    # 此数组里的对象是数独列表里的对象，所以可以直接引用，同步更改
    writeArray = []
    for i in range(len(soduArray)):
        for j in range(len(soduArray[i])):
            if soduArray[i][j][1]:
                writeArray.append(soduArray[i][j])
    x = 0
    n = 1
     step  = 0
    while True:
        print(step)
        printSudokuTable(soduArray)

        writeArray[x][0] = n
        if isTrue(soduArray):
            step += 1
            if x == len(writeArray)-1:
                print("破解成功")
                printSudokuTable(soduArray)
                break
            else:
                x += 1
                n = 1
                continue
        else:
            while True:
                step += 1
                if n >= 9:
                    if x == 0:
                        exit("无解")
                    else:
                        writeArray[x][0] = 0
                        x -= 1
                        n = writeArray[x][0]
                        n += 1
                        continue
                else:
                    n += 1
                    break
    print(f"总共试了{step}个数")


if __name__ == '__main__':
    # 初始化数独
    sudoku = newTemp()
    print("欢迎使用破解程序，本程序由littlefean于2020年7月18日完成")
    print("下面进入数独初始状态输入阶段")
    print("提示：0表示空白位置，如果想删除某个位置的数，可以在输入数字的时候输入0，并覆盖相应的位置")
    # 开始出题
    sudoku = startWrite(sudoku)
    print(isTrue(sudoku))

    # 开始破解
    crack(sudoku)
    input("end")
  

发现

Python破解我那个初中同学发的很难的数独，花了30秒。而java几乎只花了3秒。Java的程序效率比Python的效率高出了很多。

反思与总结

下次我再改进程序的时候，我应该使用面向对象的方法把数独的元素封装起来，把数独写成一个类，方便使用。

肯定有比我的程序更好的算法。我的程序不一定很好。