Python生成数独矩阵

数独(sudoku)盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次,所以又称“九宫格”。

明白了原理之后就很简单了,首先我们在代码里生成一个9x9的二维数组。如下图所示,因为第1、第5、第9宫格之间是没有关联的,只需要保证这三个宫格之中都包含1到9的数字就只可以了,所以我们可以生成3组1-9的数字,分别将3组数字打乱顺序后填入蓝色格式,如下图所示。

9x9二维数组

接着我们只需要遍历每个个格子,排除不可填的数字之后,随机给它填入一个数字,如果发现当前格子没有可填的值,则退回去上一个格子,将此格子原有的值排除后再重新选一个新的值填入,如果发现也没有合适的值,再退一个格子....在不停的重复这个过程之后,就可以得到一个正确的数独矩阵,这里用到了深度优先算法和回溯算法。

以下为示例代码:

import random
import math

matrix = []


# 生成一个随机的数组
def get_random_unit():
    _num_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    random.shuffle(_num_list)
    return _num_list


def print_grid(arr):
    for i in range(9):
        print(arr[i])


def get_row(row):
    row_arr = []
    for v in matrix[row]:
        if v == 0:
            continue
        row_arr.append(v)
    return row_arr


def get_col(col):
    col_arr = []
    for i in range(9):
        val = matrix[i][col]
        if val == 0:
            continue
        col_arr.append(matrix[i][col])
    return col_arr


def get_block(num):
    col_arr = []
    seq = num % 3
    col_end = 9 if seq == 0 else seq * 3
    row_end = int(math.ceil(num / 3) * 3)
    for i in range(row_end - 3, row_end):
        for j in range(col_end - 3, col_end):
            val = matrix[i][j]
            if val != 0:
                col_arr.append(matrix[i][j])
    return col_arr


def get_block_seq(row, col):
    col_seq = int(math.ceil((col + 0.1) / 3))
    row_seq = int(math.ceil((row + 0.1) / 3))
    return 3 * (row_seq - 1) + col_seq


def get_enable_arr(row, col):
    avail_arr = get_random_unit()
    seq = get_block_seq(row, col)
    block = get_block(seq)
    row = get_row(row)
    col = get_col(col)
    unable_arr = list(set(block + row + col))
    for v in unable_arr:
        if v in avail_arr:
            avail_arr.remove(v)
    return avail_arr


def main():
    can_num = {}
    count = 0
    # 初始化一个9行9列的数组
    for i in range(9):
        matrix.append([0] * 9)

    num_list = get_random_unit()
    for row in range(3):
        for col in range(3):
            matrix[row][col] = num_list.pop(0)

    num_list = get_random_unit()
    for row in range(3, 6):
        for col in range(3, 6):
            matrix[row][col] = num_list.pop(0)

    num_list = get_random_unit()
    for row in range(6, 9):
        for col in range(6, 9):
            matrix[row][col] = num_list.pop(0)

    box_list = []
    for row in range(9):
        for col in range(9):
            if matrix[row][col] == 0:
                box_list.append({'row': row, 'col': col})

    i = 0
    while i < len(box_list):
        count += 1
        position = box_list[i]
        row = position['row']
        col = position['col']
        key = '%dx%d' % (row, col)
        if key in can_num:
            enable_arr = can_num[key]
        else:
            enable_arr = get_enable_arr(row, col)
            can_num[key] = enable_arr

        if len(enable_arr) <= 0:
            i -= 1
            if key in can_num:
                del (can_num[key])
            matrix[row][col] = 0
            continue
        else:
            matrix[row][col] = enable_arr.pop()
            i += 1

    print_grid(matrix)
    print(count)


if __name__ == "__main__":
    main()

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 一不小心就沉迷数独无法自拔,起初只是当做锻炼脑子的益智小游戏,后来看到了相关的数独解题技巧,才知道原来方格间还蕴藏...
    Icebay阅读 7,672评论 0 9
  • 由于上篇的算法存在一些不足,我们不免要继续研究数独游戏的完全解,以获得更高效高质量的生成算法,对于完全解的生成过程...
    Chris啊飞飞阅读 8,067评论 0 1
  • 喜欢看《最好的我们》的人不难发现,学霸余淮特别喜欢做数独,在上课的时候也会做数独题。最近重看电视剧,想起官网上的那...
    晨曦爱读书阅读 13,449评论 5 40
  • 难度划分 影响数独难度的因素很多,就题目本身而言,包括最高难度的技巧、各种技巧所用次数、是否有隐藏及隐藏的深度及广...
    杨过的大雕阅读 3,632评论 0 3
  • 读好文,听好的故事可以有醍醐灌顶的好处。好的创意,好的故事,好的新闻,好的想法,好的作品往往是产品+加工的...
    星痕simida阅读 355评论 0 0