当前位置: > 投稿>正文

最难数独解答思路,而且它只有一个答案

11-24 互联网 未知 投稿

关于【最难数独解答思路】,而且它只有一个答案,今天犇涌小编给您分享一下,如果对您有所帮助别忘了关注本站哦。

1、迄今难度最大的数独游戏,而且它只有一个答案(附解法代码)

芬兰数学家因卡拉,花费3个月时间设计出了世界上迄今难度最大的数独游戏,而且它只有一个答案。因卡拉说只有思考能力最快、头脑最聪明的人才能破解这个游戏

最难数独解答思路,而且它只有一个答案

写在前面

今天来点干货,结合深度优先搜索算法,对数独进行求解。以下代码纯属手工编写,每个步骤都附加详细说明。

最难数独解答思路,而且它只有一个答案

  • 环境配置
  • python版本: 3.6.0

    编辑器: pycharm

    第一步:导入相关的python包

    # encoding:utf-8import copy

    copy: 主要用于数组(矩阵)的深拷贝,有深拷贝就有浅拷贝。可以这么理解,深拷贝就是新开辟一个内存,修改原数据,拷贝后的数据不会被影响。而浅拷贝只是给数组取了个别名,实际上是同一个内容的数据,修改原数据,拷贝后的数据会跟着修改

    如果不特别声明,数组的拷贝一般是浅拷贝,例如函数传参。后面递归的参数数组,用的是浅拷贝,所以同一个数组共用一块内存。

    最难数独解答思路,而且它只有一个答案

    第二步:判断矩阵是否填满

    """判断矩阵是否填满了"""def is_full(in_sd_matrix): for i in range(len(in_sd_matrix)): for j in range(len(in_sd_matrix[i])): if in_sd_matrix[i][j] == 0: return False return True

    这里作了个前提,如果矩阵中数值为0,说明该位置还未填入数字。

    最难数独解答思路,而且它只有一个答案

    第三步:数独的规则

    """判断当前位置能否填指定数字"""def can_fit(in_sd_matrix, row_index:int, col_index:int, num): # 判断当前行是否出现重复的非零数字 for k in range(len(in_sd_matrix[row_index])): if k != col_index and in_sd_matrix[row_index][k] == num: return False # 判断当前列是否出现重复的非零数字 for k in range(len(in_sd_matrix)): if k != row_index and in_sd_matrix[k][col_index] == num: return False # 判断当前矩阵是否出现重复的非零数字 cube_i, cube_j = int(row_index / 3), int(col_index / 3) for k in range(cube_i * 3, (cube_i + 1) * 3): for p in range(cube_j * 3, (cube_j + 1) * 3): if k != row_index and p != col_index and in_sd_matrix[k][p] == num: return False return Tru

    利用了数独的规则,每个数字满足三个条件:

    1. 该数字所在的当前行不会重复,

    2. 该数字所在的当前列不会重复,

    3. 该数字所在的小九宫格数字不会重复。

    最难数独解答思路,而且它只有一个答案

    第四步:递归-深度优先搜索

    """递归填数字"""def depth_fit_num(in_sd_matrix): # 递归结束条件, 已经填满了 if is_full(in_sd_matrix): return True for i in range(0, 9): for j in range(0, 9): if in_sd_matrix[i][j] != 0: continue # 尝试填 1 ~ 9 数字 fail_cnt = 0 for t_num in range(1, 10): # 判断当前位置是否可以填数字num if can_fit(in_sd_matrix, i, j, t_num): in_sd_matrix[i][j] = t_num # 尝试填数字 flag = depth_fit_num(in_sd_matrix) # 递归 if flag is False: fail_cnt += 1 # 这里也代表不能填数字 else: fail_cnt += 1 # 不能填的数字个数 # 如果该空格 1~ 9都不能填,说明该路径行不通 if 9 == fail_cnt: in_sd_matrix[i][j] = 0 # 回溯 return False return True

    depth_fit_num()递归填数字,参数in_sd_matrix是一个数组(浅拷贝),也就是说,每一次递归,都是在原数组上进行操作。这是一个非常典型的递归的函数。我们假设输入的数独一定存在一个或多个解。该递归满足五个步骤:

    1. 递归结束条件。在开头is_full()函数,一旦数组填满,就结束递归;

    2. 递归主体1,双重for循环对9X9宫格进行遍历,对每个空格进行1~9的数字填入

    3. 递归主体2,depth_fit_num(),对矩阵进行深度优先搜索

    4. 递归主体3,回溯,如果发现当层递归中,该空格1~9都不能填入,说明上层递归尝试的的数字不对,则当前位置数字回溯重置为0,并 return False 结束当层递归;

    5. 递归结束条件,当前层递归循环体全部完成,return True, 结束当层递归。

    (ps: 可以使用单步调试,查看每次递归,in_sd_matrix 矩阵的数值变化)

    换一种方式说,就是该递归函数,在这个9X9的宫格中,不断去尝试每个位置1~9数字的逐个逐个填入,并判断是否满足数独要求。一旦发现某个位置不满足,就不会继续尝试下去,而是倒回前一个位置尝试其他数字。如此反复。

    最难数独解答思路,而且它只有一个答案

    第五步:规则打印

    """打印矩阵"""def print_sd(in_sd_matrix, out_sd_matrix, question_type, answer_type): """ 打印矩阵 :param in_sd_matrix: 输入矩阵 :param out_sd_matrix: 输出矩阵 :param question_type: 问题颜色 :param answer_type: 答案颜色 :return: """ head_line = ("+" + "+=====" * 3) * 3 + "++" mid_line = ("+" + "+-----" * 3) * 3 + "++" for i in range(len(in_sd_matrix)): new_line = '' for j in range(len(in_sd_matrix[i])): if j == 0: new_line += "||" if in_sd_matrix[i][j] != 0: new_line += " %s " % (question_type % str(in_sd_matrix[i][j])) else: new_line += " %s " % (answer_type % (str(out_sd_matrix[i][j]) if out_sd_matrix[i][j] != 0 else ' ')) if (j + 1) % 3 != 0: new_line += "|" elif (j + 1) % 3 == 0: new_line += "||" if i == 0: print(head_line) print(new_line) if (i + 1) % 3 != 0: print(mid_line) elif (i + 1) % 3 == 0: print(head_line)

    设计好了基础算法,还需要设计输出展示“UI”。这里只是对输出的矩阵进行美化,使得更加可观。同时区分数独题目,和数独求解后的答案。题目是红色标注,填的答案用绿色标注。

    最难数独解答思路,而且它只有一个答案

    第六步:主函数

    if __name__ == '__main__': sd_matrix = [[8, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 3, 6, 0, 0, 0, 0, 0], [0, 7, 0, 0, 9, 0, 2, 0, 0], [0, 5, 0, 0, 0, 7, 0, 0, 0], [0, 0, 0, 8, 4, 5, 7, 0, 0], [0, 0, 0, 1, 0, 0, 0, 3, 0], [0, 0, 1, 0, 0, 0, 0, 6, 8], [0, 0, 8, 5, 0, 0, 0, 1, 0], [0, 9, 0, 0, 0, 0, 4, 0, 0]] red_type = "\033[031m%s\033[0m" green_type = "\033[036m%s\033[0m" out_sd_matrix = copy.deepcopy(sd_matrix) # 深复制 print_sd(sd_matrix, out_sd_matrix, red_type, green_type) depth_fit_num(out_sd_matrix) print_sd(sd_matrix, out_sd_matrix, red_type, green_type) print(

    主函数,对输入的矩阵进行深拷贝(主要用于对比题目和答案)。调用之前写好的数独求解的算法。

    最难数独解答思路,而且它只有一个答案

    输入输出:

    最难数独解答思路,而且它只有一个答案

    最后,给一点点学习建议,不懂的时候,先弄明白它的功能以及会使用它,让代码先运行起来。等有时间就一个一个细节去攻破它,编程和写文章一样,需要慢慢积累,加油。

    2、最难数独解答思路,而且它只有一个答案

    【什么是数独】

    数独是一种运用纸、笔进行演算的逻辑游戏。数独盘面是个九宫,每一宫又分为九个小格。在这81格中给出一定的已知数字,利用逻辑推理,在其他的空格上填入1--9的数字。使1---9每个数字在每一行、每一列和每一宫格都只出现一次,所以又称为“九宫格”。


    【学习数独的好处】

    培养数感---锻炼逻辑思维能力---培养专注力---培养主动注意能力---培养耐心---激发学生潜能---增强孩子的自信心


    而下面的三组数独题,据说只有2%的人能全部做对,能做出来一组就很厉害了,你来试试看?

    第一组:难度系数:2颗星

    最难数独解答思路,而且它只有一个答案


    第二组:难度系数:3颗星

    最难数独解答思路,而且它只有一个答案


    第三组:难度系数:4颗星

    本文关键词:最难解的数独40题,最难的数独题怎么解,最难数独和答案,最难数独解题过程,最难的数独题答案。这就是关于《最难数独解答思路,而且它只有一个答案》的所有内容,希望对您能有所帮助!更多的知识请继续关注《犇涌向乾》百科知识网站:http://www.029ztxx.com!

    版权声明: 本站仅提供信息存储空间服务,旨在传递更多信息,不拥有所有权,不承担相关法律责任,不代表本网赞同其观点和对其真实性负责。如因作品内容、版权和其它问题需要同本网联系的,请发送邮件至 举报,一经查实,本站将立刻删除。

    猜你喜欢