Python生成数独题目

  • 发布时间:2020年3月12日 00:52
  • 作者:杨仕航
  • 分类标签: Python
  • 阅读(3255)
  • 评论(0)

之前简单用Numpy的二维矩阵结构解过数独:Python秒解最难数独

闲暇之余,产生另外一个想法:用Python生成数独题目。


1、初次尝试

经典数独是9*9的方阵。最简单的生成题目思路是按照从左至右,从上至下的顺序逐个把1~9的数字随机填入到数独的格子中。然后再随机抹去一定数量的格子即可。

20200219/20200219182721331.png

当然,这里随机填入的时候,还要考虑到数独的规则:

1)同一行的数字不能重复

2)同一列的数字不能重复

3)同一个九宫格的数字不能重复


所以,在随机填入的时候,每次填入之前都要检查是否符合上面的条件。或者在随机生成数字的时候,就把所在格子的行、列、九宫格已经存在的数字排除在外,然后再生成随机数字。


我采取排除的方法生成随机数字,简单代码如下:

1)先定义获取一个二维矩阵行、列、九宫格的方法

import random
import numpy as np


# 其中sudo参数是numpy的二维矩阵
# 获取格子所在的行的全部格子
def get_row(sudo, row):
    return sudo[row, :]

# 获取格子所在的列的全部格子
def get_col(sudo, col):
    return sudo[:, col]

# 获取格子所在的九宫格的全部格子
def get_block(sudo, row, col):
    row_start = row // 3 * 3
    col_start = col // 3 * 3
    return sudo[row_start: row_start + 3, col_start: col_start + 3]


2)书写生成逻辑:遍历,排除已被使用的数字,随机填入

def create():
    # 1~9,参考一维数组
    sample = np.array(range(1, 10))
    # 9*9的二维矩阵,每个格子默认值为0
    sudo = np.zeros((9, 9), dtype=int)

    # 遍历从左到右,从上到下逐个遍历
    for row in range(9):
        for col in range(9):
            # 获取该格子对应的行、列、九宫格
            sudo_row = get_row(sudo, row)
            sudo_col = get_col(sudo, col)
            sudo_block = get_block(sudo, row, col)

            # 该格子已被使用的数字,并集运算
            used_nums = np.union1d(np.union1d(sudo_row, sudo_col), sudo_block)
            # 剩下可用的数字,差集运算
            rest_nums = np.setdiff1d(sample, used_nums)

            # 判断是否有数字可用
            if len(rest_nums) == 0:
                raise Exception('发生错误,没有数字可用')
            
            # 随机取出一个
            rand_num = random.sample(rest_nums.tolist(),1)[0]
            sudo[row, col] = rand_num
    return sudo


3)执行

我尝试执行,都遇到没有数字可用的错误

20200219/20200219190749341.png


调整代码,打印发生错误时的数独

# 打印数独
def print_sudo(sudo):
    for row_index, row in enumerate(sudo):
        if row_index % 3 == 0 and row_index != 0:
            print('-' * (9 + 8 + 4))
        row = list(map(str, row.tolist()))
        row.insert(6, '|')
        row.insert(3, '|')
        print(' '.join(row))

def create():
    # 1~9,参考一维数组
    sample = np.array(range(1, 10))
    # 9*9的二维矩阵,每个格子默认值为0
    sudo = np.zeros((9, 9), dtype=int)

    # 遍历从左到右,从上到下逐个遍历
    for row in range(9):
        for col in range(9):
            # 获取该格子对应的行、列、九宫格
            sudo_row = get_row(sudo, row)
            sudo_col = get_col(sudo, col)
            sudo_block = get_block(sudo, row, col)

            # 该格子已被使用的数字,并集运算
            used_nums = np.union1d(np.union1d(sudo_row, sudo_col), sudo_block)
            # 剩下可用的数字,差集运算
            rest_nums = np.setdiff1d(sample, used_nums)

            # 判断是否有数字可用
            if len(rest_nums) == 0:
                print_sudo(sudo)
                raise Exception('发生错误,[{0}, {1}]没有数字可用'.format(row + 1, col + 1))
            
            # 随机取出一个
            rand_num = random.sample(rest_nums.tolist(),1)[0]
            sudo[row, col] = rand_num
    return sudo


再次执行:

20200219/20200219191353073.png


执行结果,第2行第9列没有数字可用。

我们看第2行已经几乎填满了数字,剩下4可填。而在这个九宫格,数字4已经被使用(第1行第8列)。所以无数字可用。


4)初步结论

后来,我又尝试了好几次,都是出现这种结果。仔细思考,得出以下结论:

以上面的例子为例,第二行在随机填写数字的时候,没有考虑到数字4在后面3列无法使用。除了数独基本3个限制条件外,其实这3个限制条件会导致数字之间产生一种纠缠关系。而前面简单的做法没有考虑到这种潜在的影响,所以无法生成一个完整的数独。

从数独的3个限制条件出发,3个限制条件都是不同的维度。而这些维度都有交叉关系,例如一个格子同时存在于某一行和某一列、某一九宫格。就像空间坐标轴,空间上的任意一点都有x、y、z等3个坐标轴。

感觉数独是一种高纬度的矩阵,我们看到的二维矩阵只是高纬度矩阵在二维上的投影。如果用这种简单随机方法生成数独的话,很难涉及到每个数字之间的纠缠关系,可能需要用更高维度的方式去处理,例如3维矩阵、4维矩阵。


后来,我尝试提高维度去解决问题,也遇到同样无法直接生成数独。可能我的数学知识还不够,不能用数学的方式表达数独。

其实用我之前解数独的方法也可以生成数独。在生成的过程发现有问题就回退上一步,重新选择其他随机数。相当于解一个81个格子都为空的数独。用这个方法没多大意思,一来是我已经做过的了,二来效率其实不太高。


2、柳暗花明又一村

在不断翻阅资料时,偶然发现一个规律:在已有的数独结果上,同一个九宫格内任意两个格子,调换其所在的行或者所在的列后的结果,还是一个有效的数独。

例如交换D1和E3两个格子所在的行:

20200220/20200220120111896.png


数独3个限制条件都没有被破坏。进一步发现,其实只要在九宫格范围里面的任意两行或两列交换都可以。

例如交换D行和E行,D行和E行都在九宫格的范围内。而A行和D行就不能交换。

20200220/20200220114449299.png


如此一来,我们只要用一个简单的数独(这个术语叫基本盘),随机多次交换不会破坏数独完整性的行或列,形成最终结果(术语叫终盘);最后再随机抹去一些数据即可变成数独题目。


1)生成基本盘

生成基本盘的代码如下(延用上面的get_row、get_col、get_block方法):

def create_base_sudo():
    # 9*9的二维矩阵,每个格子默认值为0
    sudo = np.zeros((9, 9), dtype=int)
    # 随机生成起始的基数(1 ~ 9)
    num = random.randrange(9) + 1

    # 遍历从左到右,从上到下逐个遍历
    for row_index in range(9):
        for col_index in range(9):
            # 获取该格子对应的行、列、九宫格
            sudo_row = get_row(sudo, row_index)
            sudo_col = get_col(sudo, col_index)
            sudo_block = get_block(sudo, row_index, col_index)

            # 如果该数字已经存在于对应的行、列、九宫格
            # 则继续判断下一个候选数字,直到没有重复
            while num in sudo_row or num in sudo_col or num in sudo_block:
                num = num % 9 + 1

            # 赋值
            sudo[row_index, col_index] = num
            num = num % 9 + 1
    return sudo


这里用了求余的方法,把num限制在1到9之间。执行该方法,可以得到如下类似的基本盘:

20200311/20200311223918718.png


2)随机交换,得到终盘

然后我们再多次随机交换行列,得到终盘:

# 随机交换n次
def random_sudo(sudo, times):
    for _ in range(times):
        # 随机交换两行
        rand_row_base = random.randrange(3) * 3  # 从0,3,6 随机取一个
        rand_rows = random.sample(range(3), 2)   # 从 0,1,2中随机取两个数
        row_1 = rand_row_base + rand_rows[0]
        row_2 = rand_row_base + rand_rows[1]
        sudo[[row_1, row_2], :] = sudo[[row_2, row_1], :]

        # 随机交换两列
        rand_col_base = random.randrange(3) * 3
        rand_cols = random.sample(range(3), 2)
        col_1 = rand_col_base + rand_cols[0]
        col_2 = rand_col_base + rand_cols[1]
        sudo[:, [col_1, col_2]] = sudo[:, [col_2, col_1]]


我随机交换50次,最终得到一个和基本盘差别很大的终盘:

20200311/20200311224526936.png


3)随机抹去数字,得到数独题目

这里如果抹去数字太多,会导致题目很难解,或者容易有多个解;如果抹去数字太少,数独题目就会变得很简单。

经过一番测试,大概最多清除64个数字,最少清除14个数字,得到的题目可解。代码如下:

def get_sudo_subject(sudo, del_nums):
    # 最少要保留17个数字,题目才可解。一共81个数字,则最多可以擦除81-17 = 64。
    max_clear_count = 64
    # 最少也要擦除14个
    min_clear_count = 14

    if del_nums < min_clear_count:
        del_nums = min_clear_count
    if del_nums > max_clear_count:
        del_nums = max_clear_count

    # 随机擦除(从0到80,随机取要删除的个数)
    clears = random.sample(range(81), del_nums)
    for clear_index in clears:
        # 把0到80的坐标转化成行和列索引
        # 这样就不会重复删除同一个格子的数字
        row_index = clear_index // 9
        col_index = clear_index % 9
        sudo[row_index, col_index] = 0


下面是我随机抹去30个数字的效果:

20200312/20200312002952960.png


4)整合代码

这里除了整合全部代码之外,我还划分了难度等级,抹去数字越多则越难。我将其划分为5个级别:入门、初级、熟练、精通、大神。

具体代码如下:

import random
import numpy as np


# 获取格子所在的行的全部格子
def get_row(sudo, row):
    return sudo[row, :]

# 获取格子所在的列的全部格子
def get_col(sudo, col):
    return sudo[:, col]

# 获取格子所在的九宫格的全部格子
def get_block(sudo, row, col):
    row_start = row // 3 * 3
    col_start = col // 3 * 3
    return sudo[row_start: row_start + 3, col_start: col_start + 3]

# 打印数独
def print_sudo(sudo):
    for row_index, row in enumerate(sudo):
        if row_index % 3 == 0 and row_index != 0:
            print('-' * (9 + 8 + 4))
        row = list(map(str, row.tolist()))
        row.insert(6, '|')
        row.insert(3, '|')
        row_str = ' '.join(row)
        print(row_str.replace('0', ' '))

def create_base_sudo():
    # 9*9的二维矩阵,每个格子默认值为0
    sudo = np.zeros((9, 9), dtype=int)
    # 随机生成起始的基数(1 ~ 9)
    num = random.randrange(9) + 1

    # 遍历从左到右,从上到下逐个遍历
    for row_index in range(9):
        for col_index in range(9):
            # 获取该格子对应的行、列、九宫格
            sudo_row = get_row(sudo, row_index)
            sudo_col = get_col(sudo, col_index)
            sudo_block = get_block(sudo, row_index, col_index)

            # 如果该数字已经存在于对应的行、列、九宫格
            # 则继续判断下一个候选数字,直到没有重复
            while num in sudo_row or num in sudo_col or num in sudo_block:
                num = num % 9 + 1

            # 赋值
            sudo[row_index, col_index] = num
            num = num % 9 + 1
    return sudo

def random_sudo(sudo, times):
    for _ in range(times):
        # 随机交换两行
        rand_row_base = random.randrange(3) * 3  # 从0,3,6 随机取一个
        rand_rows = random.sample(range(3), 2)   # 从 0,1,2中随机取两个数
        row_1 = rand_row_base + rand_rows[0]
        row_2 = rand_row_base + rand_rows[1]
        sudo[[row_1, row_2], :] = sudo[[row_2, row_1], :]

        # 随机交换两列
        rand_col_base = random.randrange(3) * 3
        rand_cols = random.sample(range(3), 2)
        col_1 = rand_col_base + rand_cols[0]
        col_2 = rand_col_base + rand_cols[1]
        sudo[:, [col_1, col_2]] = sudo[:, [col_2, col_1]]

def get_sudo_subject(sudo, del_nums):
    subject = sudo.copy()

    # 随机擦除(从0到80,随机取要删除的个数)
    clears = random.sample(range(81), del_nums)
    for clear_index in clears:
        # 把0到80的坐标转化成行和列索引
        # 这样就不会重复删除同一个格子的数字
        row_index = clear_index // 9
        col_index = clear_index % 9
        subject[row_index, col_index] = 0
    return subject

if __name__ == '__main__':
    max_clear_count = 64  # 最多清除个数
    min_clear_count = 14  # 最少清除个数

    # 设置难度等级,1~5,5个等级:入门、初级、熟练、精通、大神
    level = 3
    
    # 每个等级的个数
    each_level_count = (max_clear_count - min_clear_count) / 5

    # 该等级最小数
    level_start = min_clear_count + (level - 1) * each_level_count
    # 该等级范围内的随机数
    del_nums = random.randrange(level_start, level_start + each_level_count)

    # 生成基本盘
    sudo = create_base_sudo()
    # 生成终盘
    random_sudo(sudo, 50)
    # 获取数独题目
    subject = get_sudo_subject(sudo, del_nums)

    print('题目:')
    print('=' * 26)
    print_sudo(subject)
    print('\n答案:')
    print('=' * 26)
    print_sudo(sudo)


生成熟练等级的数独题目,执行结果如下:

20200312/20200312005059060.png


上一篇:没有了

下一篇:MySQL忘记root密码【来自官方文档的方法,亲测有用】

相关专题: 我为数独迷   

评论列表

智慧如你,不想发表一下意见吗?

新的评论

清空