数独生成

难度：⭐⭐⭐⭐⭐

1. 题目描述

题目描述

随机生成一个数独题目

2. 关键点

• 先构建数独终盘（类似数独求解之后）
• 再依次在数独终盘中进行挖洞，并每挖一次均保证数独唯一解，直至无法再挖

3. 代码实现

点击显示代码

import random


class Sudoku():
    """数独求解与生成"""
    def __init__(self, sudoku=None):
        if sudoku is None:
            self.init_sudoku()
        else:
            self.sudoku = sudoku
        self.solve_cnt = 0      # 数独求解时解的数量
        self.solve_sudoku = []  # 数独解

    def init_sudoku(self):
        self.sudoku = [[0] * 9 for i in range(9)]

    def random_num(self, x, y):
        """随机值"""
        candidate = [n for n in range(1, 10) if self.possible(x, y, n)]
        if candidate:
            return random.choice(candidate)
        else:
            return -1

    def generate(self):
        """生成数独"""
        self._generate()
        self.puzzle_dibble()

    def _generate(self):
        """生成数独终盘"""
        def random_one():
            for x in range(9):
                for y in range(9):
                    random_num = self.random_num(x, y)
                    if random_num == -1:
                        self.init_sudoku()
                        return False
                    self.sudoku[x][y] = random_num
            return True

        while random_one() is False:
            pass

    def puzzle_dibble(self):
        """挖洞生成"""
        while True:
            x = random.randint(0, 8)
            y = random.randint(0, 8)
            if self.sudoku[x][y] != 0:
                n = self.sudoku[x][y]
                self.sudoku[x][y] = 0
                self.solve_cnt = 0
                self.solve()
                if self.solve_cnt > 1:
                    self.sudoku[x][y] = n
                    break

    def possible(self, x, y, n):
        """验证值的可能性"""
        for i in range(9):
            if self.sudoku[i][y] == n:
                return False

        for j in range(9):
            if self.sudoku[x][j] == n:
                return False

        # 所在小矩阵第一个元素的坐标
        grid_x = x // 3 * 3
        grid_y = y // 3 * 3
        for i in range(3):
            for j in range(3):
                xx = grid_x + j
                yy = grid_y + i
                if self.sudoku[xx][yy] == n:
                    return False
        return True

    def solve(self):
        """数独求解"""
        for x in range(9):
            for y in range(9):
                if self.sudoku[x][y] == 0:
                    for n in range(1, 10):
                        if self.possible(x, y, n):
                            self.sudoku[x][y] = n
                            self.solve()
                            self.sudoku[x][y] = 0
                    return
        self.solve_cnt += 1
        self.solve_sudoku = self.copy()

    def copy(self, sudoku=None):
        if sudoku is None:
            sudoku = self.sudoku
        return [[c for c in row] for row in sudoku]

    def out(self, sudoku=None):
        if sudoku is None:
            sudoku = self.sudoku
        num_cnt = 0
        for row in sudoku:
            print(row)
            num_cnt += len([num for num in row if num != 0])
        print(num_cnt, sudoku)


if __name__ == '__main__':
    sdk = Sudoku()
    sdk.generate()
    sdk.out()

4. 运行示例

[7, 0, 8, 1, 0, 0, 5, 0, 0]
[0, 0, 0, 6, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 6]
[0, 9, 7, 0, 0, 2, 6, 0, 0]
[6, 3, 0, 9, 8, 0, 0, 1, 7]
[8, 0, 1, 5, 6, 0, 0, 4, 0]
[2, 8, 4, 0, 3, 0, 0, 6, 0]
[0, 0, 0, 0, 2, 0, 0, 8, 0]
[1, 0, 9, 8, 5, 0, 0, 3, 0]

5. 进阶思考

1. 随机挖洞无法有效产生较高难度的数独；改成间隔挖洞，可有效提高难度