1. 首页
  2. Python

python轻松解决数独小游戏,结果通过递归获得最终答案

“u003Cdivu003Eu003Cpu003E对于值域列表缩减函数进行了改造,增加了检测唯一值的方法,但最终我们依然没有得到答案,还有很多单元格的答案没有确定,应该怎么办呢?u003Cu002Fpu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp1.pstatp.comu002Flargeu002Fpgc-imageu002Fffdcea92cf154f828366013be3f4528b” img_width=”360″ img_height=”359″ alt=”python轻松解决数独小游戏,结果通过递归获得最终答案” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cpu003E在当前这种情况下,我们已经无法从数独中直接确定某个单元格的答案了,但是我们可以用测试的办法,去验证某个单元格的答案是哪一个值,我们以第7行第7列单元格为例,我们假设它的值是1,则这个变化会引起一系列的变化,最终我们得到这个:u003Cu002Fpu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp1.pstatp.comu002Flargeu002Fpgc-imageu002Febdb22e5305b487a999d9e695e82fd0b” img_width=”360″ img_height=”358″ alt=”python轻松解决数独小游戏,结果通过递归获得最终答案” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cpu003E在第二个九宫格出现了2个7,因此我们可以判断第7行第7列的值不是1,而应该是6。我们通过这种测试验证的方法获得了某个单元格的答案。我们现在需要用代码来实现:u003Cu002Fpu003Eu003Cpreu003E# 主函数,输入值域列表,如遇到多个取值的单元格,依次尝试值域里的每个值,通过递归的方法检测值是否正确u003Cbru003Edef trial(total_value_range):u003Cbru003E for i in range(9):u003Cbru003E for j in range(9):u003Cbru003E if len(total_value_range[i][j]) > 1:u003Cbru003E for k in total_value_range[i][j]:u003Cbru003E test_value = copy.deepcopy(total_value_range)u003Cbru003E test_value[i][j] = [k]u003Cbru003E test_value = reduce_totalValueRange(generator_soduku(test_value))u003Cbru003E if soduku_checkRepeat(test_value):u003Cbru003E if sodukuRate(s_row_vrange) == 1:u003Cbru003E return s_row_vrangeu003Cbru003E else: u003Cbru003E if trial(test_value):u003Cbru003E return trial(test_value)u003Cbru003E else:u003Cbru003E continueu003Cbru003E else:u003Cbru003E continueu003Cbru003E return Falseu003Cbru003Eu003Cu002Fpreu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp9.pstatp.comu002Flargeu002Fdfic-imagehandleru002F51cd7973-b34a-4cdb-bba6-9b03efa0746e” img_width=”1200″ img_height=”800″ alt=”python轻松解决数独小游戏,结果通过递归获得最终答案” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cpu003E这段代码其实还是挺复杂的,容我细细解读:u003Cu002Fpu003Eu003Cpreu003E# 主函数,输入值域列表,如遇到多个取值的单元格,依次尝试值域里的每个值,通过递归的方法检测值是否正确u003Cbru003Edef trial(total_value_range):u003Cbru003E for i in range(9):u003Cbru003E for j in range(9):u003Cbru003E if len(total_value_range[i][j]) > 1:u003Cbru003E for k in total_value_range[i][j]:u003Cbru003E test_value = copy.deepcopy(total_value_range)u003Cbru003E test_value[i][j] = [k]u003Cbru003Eu003Cu002Fpreu003Eu003Culu003Eu003Cliu003E我们设置i和j两个循环,是为了遍历total_value_range里的每一个元素当total_value_range[i][j] = 1时,也就是说这个单元格是已知单元格,取值已经确定了;如果total_value_range[i][j] > 1,这个单元格是未知单元格,值域列表有多个取值;对于未知单元格,我们遍历它的值域,同时拷贝一份total_value_range,并把值域里的值赋给test_value[i][j],开始进行“试验”,看test_value[i][j]里的哪一个值是正确的;u003Cu002Fliu003Eu003Cu002Fulu003Eu003Cpreu003E# 检查行值域列表是否合法u003Cbru003Edef row_checkRepeat(s_value_range):u003Cbru003E for i in s_value_range:u003Cbru003E temp = []u003Cbru003E for j in i:u003Cbru003E if len(j) == 1:u003Cbru003E temp.append(j[0])u003Cbru003E len_temp = len(temp)u003Cbru003E if len_temp != len(list(set(temp))):u003Cbru003E return Falseu003Cbru003E return Trueu003Cbru003E# 检查值域列表是否合法:行检测,列检测,九宫格检测u003Cbru003Edef soduku_checkRepeat(s_value_range):u003Cbru003E temp_col = list(zip(*s_value_range))u003Cbru003E temp_matrix = matrix_invert(s_value_range)u003Cbru003E return row_checkRepeat(s_value_range) and row_checkRepeat(temp_col) and row_checkRepeat(temp_matrix)u003Cbru003E# 计算值域列表取值总的组合数(各单元格值域长度相乘)u003Cbru003Edef sodukuRate(s_row_vrange):u003Cbru003E rate = 1u003Cbru003E for i in s_row_vrange:u003Cbru003E for j in i:u003Cbru003E rate *= len(j)u003Cbru003E return rateu003Cbru003Edef trial(total_value_range):u003Cbru003E for i in range(9):u003Cbru003E for j in range(9):u003Cbru003E if len(total_value_range[i][j]) > 1:u003Cbru003E for k in total_value_range[i][j]:u003Cbru003E test_value = copy.deepcopy(total_value_range)u003Cbru003E test_value[i][j] = [k]u003Cbru003E test_value = reduce_totalValueRange(generator_soduku(test_value))u003Cbru003E if soduku_checkRepeat(test_value):u003Cbru003E if sodukuRate(test_value) == 1:u003Cbru003E return test_valueu003Cbru003E else: u003Cbru003E return trial(test_value)u003Cbru003E else:u003Cbru003E continueu003Cbru003E return Falseu003Cbru003Eu003Cu002Fpreu003Eu003Culu003Eu003Cliu003E赋值之后,我们立即使用之前的generator_soduku()和reduce_totalValueRange()方法,基于已有条件生成一个最新的值域列表;然后我们需要做的是,用soduku_checkRepeat()方法检验当前的值域列表是否合法,soduku_checkRepeat()方法的原理也很简单:首先我们写出一个检查行值域列表是否合法的函数:将一行已知单元格都选出放到一个列表里,检查列表是否有重复值;有了行值域检查函数,只需将数独进行行列转换和九宫格转换然后分别进行检测,如果三项检测均为True,则最后返回True,有一项False,最后返回False如果soduku_checkRepeat()显示当前值域列表合法,则使用sodukuRate()方法检测当前值域列表每个单元格是否都是已知单元格(各单元格值域长度均为1)若每个单元格值域长度均为1,则说明已经得到最终正确答案,则返回test_value,即最终正确答案;若sodukuRate(test_value)不为1,则说明经过一番操作后还未得到正确答案,或者得到错误答案,因此我们将当前的值域列表test_value作为参数,返回trial(test_value),这个就用上了递归的概念,我们稍后详细解释;如果soduku_checkRepeat()显示当前值域列表不合法,则说明total_value_range[i][j]当前的取值k不正确,我们continue,继续循环;如果for k in total_value_range[i][j],这个循环结束了,说明所有的取值k都是导向错误的结果(在第一层循环是不会出现的,会出现在第二层循环时),则返回False;u003Cu002Fliu003Eu003Cu002Fulu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp1.pstatp.comu002Flargeu002Fdfic-imagehandleru002F7344ec86-9337-4094-924c-6a48c962c328″ img_width=”1024″ img_height=”683″ alt=”python轻松解决数独小游戏,结果通过递归获得最终答案” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cpu003E最终运行代码,得到了结果u003Cu002Fpu003Eu003Cpreu003EPS D:\python\0624-soduku> python zhihutest2.pyu003Cbru003E[[5], [1], [4], [8], [9], [6], [3], [2], [7]]u003Cbru003E[[7], [2], [6], [1], [3], [4], [9], [8], [5]]u003Cbru003E[[3], [8], [9], [5], [7], [2], [4], [6], [1]]u003Cbru003E[[8], [4], [7], [6], [1], [3], [5], [9], [2]]u003Cbru003E[[1], [9], [5], [2], [4], [8], [7], [3], [6]]u003Cbru003E[[6], [3], [2], [9], [5], [7], [8], [1], [4]]u003Cbru003E[[2], [5], [3], [4], [8], [1], [6], [7], [9]]u003Cbru003E[[4], [6], [8], [7], [2], [9], [1], [5], [3]]u003Cbru003E[[9], [7], [1], [3], [6], [5], [2], [4], [8]]u003Cbru003E代码执行完毕,用时0.04秒u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003E把全部源码展示出来:u003Cu002Fpu003Eu003Cpreu003Eimport copyu003Cbru003Eimport timeu003Cbru003E# 求每一行单元格行值域u003Cbru003Edef valueRange(row):u003Cbru003E temp = copy.deepcopy(row)u003Cbru003E row_value_range = list(range(1,10))u003Cbru003E for i in row:u003Cbru003E if i == ”:u003Cbru003E continueu003Cbru003E else:u003Cbru003E if row_value_range.count(i) > 0:u003Cbru003E row_value_range.remove(i)u003Cbru003E else:u003Cbru003E continueu003Cbru003E for j in range(9):u003Cbru003E if temp[j] == ”:u003Cbru003E temp[j] = row_value_rangeu003Cbru003E else:u003Cbru003E temp[j] = [temp[j]]u003Cbru003E return tempu003Cbru003E# 求数独每个单元格行值域u003Cbru003Edef rowValueRange(soduku):u003Cbru003E row_value_range = []u003Cbru003E for row in soduku:u003Cbru003E row_value_range.append(valueRange(row))u003Cbru003E return row_value_rangeu003Cbru003E# 求数独每个单元格列值域u003Cbru003Edef colValueRange(soduku):u003Cbru003E soduku_invert = [list(i) for i in list(zip(*soduku))]u003Cbru003E temp = rowValueRange(soduku_invert)u003Cbru003E s_column_vrange = [list(i) for i in list(zip(*temp))]u003Cbru003E return s_column_vrangeu003Cbru003E# 将一个数独数组转化为数独九宫格数组u003Cbru003Edef matrix_invert(lista):u003Cbru003E listb = [[] for i in range(9)]u003Cbru003E for i in range(9):u003Cbru003E for j in range(9):u003Cbru003E k = iu002Fu002F3u003Cbru003E l = ju002Fu002F3u003Cbru003E m = k*3 + lu003Cbru003E listb[m].append(lista[i][j])u003Cbru003E return listbu003Cbru003E# 求数独每个单元格九宫格值域u003Cbru003Edef matrixValueRange(soduku):u003Cbru003E matrix = matrix_invert(soduku)u003Cbru003E temp = rowValueRange(matrix)u003Cbru003E matrix_vrange = matrix_invert(temp)u003Cbru003E return matrix_vrangeu003Cbru003E# 三个列表求交集函数u003Cbru003Edef inersection(lista,listb,listc):u003Cbru003E tempa = []u003Cbru003E tempb = []u003Cbru003E for i in lista:u003Cbru003E for j in listb:u003Cbru003E if i == j:u003Cbru003E tempa.append(i)u003Cbru003E for k in listc:u003Cbru003E for l in tempa:u003Cbru003E if k == l:u003Cbru003E tempb.append(k)u003Cbru003E return tempbu003Cbru003E# 求数独每个单元格总值域u003Cbru003Edef totalValueRange(soduku):u003Cbru003E row_value_range = rowValueRange(soduku)u003Cbru003E col_value_range = colValueRange(soduku)u003Cbru003E matrix_value_range = matrixValueRange(soduku)u003Cbru003E total_value_range = [[] for i in range(9)]u003Cbru003E for i in range(9):u003Cbru003E for j in range(9):u003Cbru003E total_value_range[i].append(inersection(row_value_range[i][j],col_value_range[i][j],matrix_value_range[i][j]))u003Cbru003E return total_value_rangeu003Cbru003E# 寻找一行中唯一的值,若该值仅在行值域列表中出现了一次,则其所在单元格取值为该值u003Cbru003Edef checkUnique(list):u003Cbru003E listb = copy.deepcopy(list)u003Cbru003E templist = []u003Cbru003E for i in listb:u003Cbru003E templist.extend(i)u003Cbru003E for i in range(len(list)):u003Cbru003E for j in list[i]:u003Cbru003E if templist.count(j) == 1:u003Cbru003E listb[i] = [j]u003Cbru003E list = listbu003Cbru003E return listu003Cbru003E# 寻找每一行的唯一值,更新值域列表u003Cbru003Edef row_checkUnique(s_row_vrange):u003Cbru003E temp = []u003Cbru003E for list in s_row_vrange:u003Cbru003E temp.append(checkUnique(list))u003Cbru003E s_row_vrange = tempu003Cbru003E return s_row_vrangeu003Cbru003E# 检查值域列表每一行、每一列、每一个九宫格的值域,并寻找唯一值,更新值域列表u003Cbru003Edef soduku_checkUnique(s_row_vrange):u003Cbru003E temp = []u003Cbru003E temp_b = []u003Cbru003E s_row_vrange = row_checkUnique(s_row_vrange)u003Cbru003E for i in list(zip(*s_row_vrange)):# 将数独进行行列转换,然后对每一列进行唯一值检测u003Cbru003E temp.append(list(i))u003Cbru003E temp = row_checkUnique(temp)u003Cbru003E for i in list(zip(*temp)):u003Cbru003E temp_b.append(list(i))u003Cbru003E temp_c = matrix_invert(temp_b)# 将数独进行九宫格转换,然后对每一九宫格进行唯一值检测u003Cbru003E temp_c = row_checkUnique(temp_c)u003Cbru003E temp_d = matrix_invert(temp_c)u003Cbru003E return temp_du003Cbru003E# 将获得的值域列表转化为一个新的数独题目u003Cbru003Edef generator_soduku(total_value_range):u003Cbru003E soduku = [[] for i in range(9)]u003Cbru003E for i in range(9):u003Cbru003E for j in range(9):u003Cbru003E if len(total_value_range[i][j]) == 1:u003Cbru003E soduku[i].append(total_value_range[i][j][0])u003Cbru003E else:u003Cbru003E soduku[i].append(”)u003Cbru003E return sodukuu003Cbru003E# 值域列表缩减函数:将值域列表转化为数独题目,求新的数独题目的值域列表,如此反复u003Cbru003Edef reduce_totalValueRange(soduku):u003Cbru003E for n in range(100):u003Cbru003E total_value_range = totalValueRange(soduku)u003Cbru003E total_value_range = soduku_checkUnique(total_value_range)u003Cbru003E soduku = generator_soduku(total_value_range)u003Cbru003E if total_value_range == totalValueRange(generator_soduku(total_value_range)):u003Cbru003E breaku003Cbru003E return total_value_rangeu003Cbru003E# 检查行值域列表是否合法u003Cbru003Edef row_checkRepeat(s_value_range):u003Cbru003E for i in s_value_range:u003Cbru003E temp = []u003Cbru003E for j in i:u003Cbru003E if len(j) == 1:u003Cbru003E temp.append(j[0])u003Cbru003E len_temp = len(temp)u003Cbru003E if len_temp != len(list(set(temp))):u003Cbru003E return Falseu003Cbru003E return Trueu003Cbru003E# 检查值域列表是否合法:行检测,列检测,九宫格检测u003Cbru003Edef soduku_checkRepeat(s_value_range):u003Cbru003E temp_col = list(zip(*s_value_range))u003Cbru003E temp_matrix = matrix_invert(s_value_range)u003Cbru003E return row_checkRepeat(s_value_range) and row_checkRepeat(temp_col) and row_checkRepeat(temp_matrix)u003Cbru003E# 计算值域列表取值总的组合数(各单元格值域长度相乘)u003Cbru003Edef sodukuRate(s_row_vrange):u003Cbru003E rate = 1u003Cbru003E for i in s_row_vrange:u003Cbru003E for j in i:u003Cbru003E rate *= len(j)u003Cbru003E return rateu003Cbru003E# 主函数,输入值域列表,如遇到多个取值的单元格,依次尝试值域里的每个值,通过递归的方法检测值是否正确u003Cbru003Edef trial(total_value_range):u003Cbru003E for i in range(9):u003Cbru003E for j in range(9):u003Cbru003E if len(total_value_range[i][j]) > 1:u003Cbru003E for k in total_value_range[i][j]:u003Cbru003E test_value = copy.deepcopy(total_value_range)u003Cbru003E test_value[i][j] = [k]u003Cbru003E test_value = reduce_totalValueRange(generator_soduku(test_value))u003Cbru003E if soduku_checkRepeat(test_value):u003Cbru003E if sodukuRate(test_value) == 1:u003Cbru003E return test_valueu003Cbru003E else: u003Cbru003E return trial(test_value)u003Cbru003E else:u003Cbru003E continueu003Cbru003E return Falseu003Cbru003Eif __name__ == ‘__main__’:u003Cbru003E t1 = time.time()u003Cbru003E soduku = [[] for i in range(9)]u003Cbru003E soduku[0] = [”,1,4,”,9,”,”,2,”]u003Cbru003E soduku[1] = [”,”,”,”,3,”,”,”,5]u003Cbru003E soduku[2] = [3,8,”,”,”,2,”,6,”]u003Cbru003E soduku[3] = [8,4,”,6,”,”,”,”,2]u003Cbru003E soduku[4] = [1,”,5,2,”,”,7,”,”]u003Cbru003E soduku[5] = [”,”,”,”,”,7,8,”,”]u003Cbru003E soduku[6] = [2,”,”,4,”,”,”,”,9]u003Cbru003E soduku[7] = [”,6,”,”,”,9,”,5,”]u003Cbru003E soduku[8] = [”,”,”,”,”,”,”,”,”]u003Cbru003E a = reduce_totalValueRange(soduku)u003Cbru003E for i in trial(a):u003Cbru003E print(i)u003Cbru003E print(“代码执行完毕,用时{}秒”.format(round(time.time() – t1,2)))u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003E最后多说一句,小编是一名python开发工程师,这里有我自己整理了一套最新的python系统学习教程,包括从基础的python脚本到web开发、爬虫、数据分析、数据可视化、机器学习等。想要这些资料的可以关注小编,并在后台私信小编:“01”即可领取。u003Cu002Fpu003Eu003Cu002Fdivu003E”

原文始发于:python轻松解决数独小游戏,结果通过递归获得最终答案

主题测试文章,只做测试使用。发布者:逗乐男神i,转转请注明出处:http://www.cxybcw.com/12888.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code