穷举法介绍

穷举法的基本思想是从所有可能的情况中搜索出正确答案。

穷举法效率并不高，适合于一些没有明显规律可循的场合，在使用穷举法时，需要明确问题的答案的范围，这样才可以在指定范围内搜索答案，指定范围之后就可以使用循环语句和条件判断语句逐步验证候选答案的正确性，从而得到需要的正确的答案。

穷举法的执行步骤

• 对于一种可能的情况，计算其结果；

• 判断结果是否满足要求，如果不满足，继续执行第一步来搜索正确答案；如果满足，则找到了一个正确答案；

代码示例

• 百钱百鸡

中国古代数学家张丘建在他的《算经》中提出了著名的“百钱买百鸡问题”：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？

def get_chicken_money():
    cock = 0  # 公鸡
    while (cock <=  // 5):
        cock += 1
        hen = 0
        while (hen <=  // 3):  # 母鸡
            hen += 1
            chicken = 0
            while (chicken <= ):
                if (5 * cock + 3 * hen + chicken / 3 == ) and (cock + hen + chicken == ):
                    print("公鸡=%d,母鸡=%d,小鸡=%d" % (cock, hen, chicken))
                chicken += 1

• 数独

import random
import numpy as np
# 代码参考https://yshblog.com/blog/
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)  # 获取三行三列数据
            # print(f"sudo_block:\n {sudo_row}, \n {sudo_col},\n {sudo_block}")
            # 如果该数字已经存在于对应的行、列、九宫格
            # 则继续判断下一个候选数字，直到没有重复
            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到，随机取要删除的个数）
    clears = random.sample(range(), del_nums)
    for clear_index in clears:
        # 把0到的坐标转化成行和列索引
        # 这样就不会重复删除同一个格子的数字
        row_index = clear_index // 9
        col_index = clear_index % 9
        subject[row_index, col_index] = 0
    return subject

if __name__ == '__main__':
    max_clear_count =   # 最多清除个数
    min_clear_count =   # 最少清除个数
    level = 3  # 设置难度等级，1~5，5个等级：入门、初级、熟练、精通、大神
    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, )  # 生成终盘
    subject = get_sudo_subject(sudo, del_nums)  # 获取数独题目
    print(f'题目：\n{"=" * }')
    print_sudo(subject)
    print(f'\n答案：\n{"=" * }')
    print_sudo(sudo)

总结

数独生成基本盘的时候，数字填充9宫格，随机生成数字后，通过while循环判断该数字不在行、列和3*3格子里，然后进行赋值，从而保证了数字的独立性！

while num in sudo_row or num in sudo_col or num in sudo_block:

num = num % 9 + 1