龙空技术网

Python学习笔记 动手实践之数独求所有解

爱思考的ERIC艾瑞克 135

前言:

目前朋友们对“数独题目生成算法及答案”可能比较关怀,兄弟们都想要剖析一些“数独题目生成算法及答案”的相关文章。那么小编也在网摘上汇集了一些对于“数独题目生成算法及答案””的相关内容,希望朋友们能喜欢,咱们快快来学习一下吧!

网上也看了python怎么解数独,都谈到回溯算法。看半天也没看明白,直接暴力求解数独的全部解。

遇到最头大的问题:求大佬指教!!!!

def can_choose_keys(row, col, MATRIX):	allkeys = keys_of_row(row, col, MATRIX) + keys_of_col(row,col, MATRIX) + keys_of_block(row, col, MATRIX)    keys = set(ANSWER_KEYS) - set(allkeys)    return keys返回的是正常的 {2, 4, 5, 6, 8}def can_choose_keys(row, col, MATRIX):    keys = set(ANSWER_KEYS) -set(keys_of_row(row, col, MATRIX)+keys_of_row(row,col, MATRIX) + keys_of_block(row, col, MATRIX))    return keys返回的确实是 {1, 2, 4, 5, 6, 8}

遇到的其他问题:

1.def get_result(MATRIX) 中选中的 MATRIX[row][col] = 0 这句一定要加上,否则会导致后面无法继续。例如当前坐标可以选择 2 和 3 两个数字,先选了 2 之后发现 2 是错误的,就会继续回来用 3 往下面继续暴力求解。没有这句MATRIX[row][col] = 0 的话,用 2 暴力求解的坐标会保留下原来错误的值。

def get_result(MATRIX)

2.def get_all_results(MATRIX, RESULTS_LIST) 中 要把所有的可能全部跑一遍,最后一个坐标,又是keys中最后一个值正确的概率几乎没有,所有永远是return False。没有办法return回解的列表。不知道有没有大佬能给个办法。现在只能print出来。

def get_all_results(MATRIX, RESULTS_LIST)

# 数独求解# 获取当前坐标对应所有 行 的值def keys_of_row(row, col, MATRIX):    keys_row = []    for cols in range(9):        keys_row.append(MATRIX[row][cols])    return keys_row# 获取当前坐标对应所有 列 的值def keys_of_col(row, col, MATRIX):    keys_col = []    for rows in range(9):        keys_col.append(MATRIX[rows][col])    return keys_col# 获取当前坐标对应所有 块 的值def keys_of_block(row, col, MATRIX):    keys_block = []    for row_fix in range(3):        for col_fix in range(3):            keys_block.append(MATRIX[row//3*3+row_fix][col//3*3+col_fix])    return keys_block# 删除当前坐标对应所有 行 块 列 的值后,取得可用的值def can_choose_keys(row, col, MATRIX):    # 不知道为什么下面这条会在  can_choose_keys(0, 0, M)  是个 1    # keys = set(ANSWER_KEYS) -set(keys_of_row(row, col, MATRIX)+keys_of_row(row,col, MATRIX) + keys_of_block(row, col, MATRIX))    allkeys = keys_of_row(row, col, MATRIX) + keys_of_col(row,                                                          col, MATRIX) + keys_of_block(row, col, MATRIX)    keys = set(ANSWER_KEYS) - set(allkeys)    return keys# 数独求单一解def get_result(MATRIX):    for row in range(9):        for col in range(9):            if MATRIX[row][col] == 0:                keys = can_choose_keys(row, col, MATRIX)                for key in keys:                    MATRIX[row][col] = key                    if get_result(MATRIX):                        return MATRIX                    else:                        MATRIX[row][col] = 0                return False    return MATRIX# 数独求全部解def get_all_results(MATRIX, RESULTS_LIST):    for row in range(9):        for col in range(9):            if row == 8 and col == 8 and MATRIX[row][col] > 0:                RESULTS_LIST.append(MATRIX)                print("数独的第", len(RESULTS_LIST), "个解")                for j in RESULTS_LIST[len(RESULTS_LIST)-1]:                    print(j)            if MATRIX[row][col] == 0:                keys = can_choose_keys(row, col, MATRIX)                for key in keys:                    MATRIX[row][col] = key                    if not get_all_results(MATRIX, RESULTS_LIST):                        MATRIX[row][col] = 0                return Falsedef check_result(MATRIX):    msg = "好像没有错"    for i in get_result(MATRIX):        if sum(i) != 45:            msg = "ERROR"    a = list(zip(*get_result(MATRIX)))    for j in a:        if sum(i) != 45:            msg = "ERROR"    print(msg)    if msg == "好像没有错":        return Truedef check_all_result(MATRIX):    msg = "好像没有错"    for i in MATRIX:        if sum(i) != 45:            msg = "ERROR"    a = list(zip(*MATRIX))    for j in a:        if sum(i) != 45:            msg = "ERROR"    print(msg)    if msg == "好像没有错":        return TrueRESULTS_LIST = []ANSWER_KEYS = {1, 2, 3, 4, 5, 6, 7, 8, 9}# ;puzzle_num=24245&play=1&difficult=4&timer=1&time_limit=0M = [    [0, 0, 3, 0, 9, 0, 0, 0, 0],    [0, 0, 0, 3, 0, 0, 5, 8, 0],    [7, 0, 0, 0, 0, 8, 2, 0, 0],    [0, 8, 0, 0, 5, 0, 1, 0, 0],    [1, 0, 0, 9, 7, 4, 0, 0, 2],    [0, 0, 6, 0, 8, 0, 0, 4, 0],    [0, 2, 0, 4, 0, 0, 0, 0, 6],    [0, 6, 1, 0, 0, 5, 0, 0, 0],    [0, 0, 0, 0, 2, 0, 3, 0, 0],]M_KEY = [    [8, 5, 3, 2, 9, 1, 6, 7, 4],    [6, 1, 2, 3, 4, 7, 5, 8, 9],    [7, 9, 4, 5, 6, 8, 2, 1, 3],    [4, 8, 9, 6, 5, 2, 1, 3, 7],    [1, 3, 5, 9, 7, 4, 8, 6, 2],    [2, 7, 6, 1, 8, 3, 9, 4, 5],    [3, 2, 8, 4, 1, 9, 7, 5, 6],    [9, 6, 1, 7, 3, 5, 4, 2, 8],    [5, 4, 7, 8, 2, 6, 3, 9, 1]]##############################################################################################                                    PRINT TEST  ZONE                                       #get_all_results(M4, RESULTS_LIST)

标签: #数独题目生成算法及答案