22-数独生成

  • 阅读: 253
  • 更新: 2022-06-11

难度:

1. 题目描述

2. 关键点

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

3. 代码实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
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. 运行示例

1
2
3
4
5
6
7
8
9
[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. 随机挖洞无法有效产生较高难度的数独;改成间隔挖洞,可有效提高难度

=== 全文完 ===


欢迎加入QQ群:778391413

京公网安备 11011302003970号 京ICP备2022012301号-1