python - 数独问题 - 固定范围实现 - 动态调整格子的可选范围没有实现

2017-09-13 12:26:14来源:CSDN作者:BigDeng_2014人点击

分享

数独问题

给定9*9的格子,要求每个3*3的小格子填的数字1-9,横线、竖线、斜线填1-9

初始条件是给出随机18个数字。(最少17个数字才能得出解)

解可能不唯一

类似穷举,

1-结合初始条件,遍历每个格子,找到剩余格子可能的取值范围。

2-从最开始的格子中挑选一个数,然后重新计算剩余格子的可能取值范围。

格子的影响范围为横线、竖线,以及3*3小格子,因此,只需要重新计算这块区域内的格子即可。

3-如果当前格子的取值范围没有1-9,说明需要调整搜索参数。

4-Python有递归深度996次的限制,区别于递归次数,递归可以无限次,但深度有限。

算法:

找到下一个空格子(x, y)

19填这个空格子:

若某个数合理:

找下一个空格子(x+1, y+1)

(x+1, y+1)是到末尾:

退出递归

否则

递归找(x+1, y+1)的填数

(x+1, y+1)没有找到填数1-9

回溯,将(x, y)置为空格子

否则

(x+1, y+1)已经填好数,继续往下填空格子

 

注:动态调整空格子取值范围的算法还没有实现。

 

源代码:

# coding=utf-8import osimport numpy as npclass sudoku_cell():    def __init__(self,x,y):        self.x = 0        self.y = 0        self.num = 0        self.choose = []def show_res(res):    for i in range(0,9,1):        print        for j in range(0,9,1):            print res[i*9 + j].num,    printdef update_choose(res, x, y, value):    # 基于位置x,y更新相关位置的choose    res_num = int(res[x*9 + y].num)    norepeat_num = value    flag = 0    if 0 == norepeat_num and 0 != res_num: # value为零则添加res_num,针对回溯        flag = 1    if 0 != norepeat_num: # value不为零则删除,针对递归前进        flag = 2    #     for i in range(0, 9, 1):        if x != i:            if 2 == flag:                for data in range(0, len(res[i*9 + y].choose), 1):                    if norepeat_num == int(res[i*9 + y].choose[data]):                        del res[i*9 + y].choose[data]                        break            if 1 == flag and not res_num in res[i * 9 + y].choose:                res[i * 9 + y].choose.append(res_num)    #     for j in range(0, 9, 1):        if y != j:            if 2 == flag:                for data in range(0, len(res[x*9 + j].choose), 1):                    if norepeat_num == int(res[x*9 + j].choose[data]):                        del res[x*9 + j].choose[data]                        break            if 1 == flag and not res_num in res[x * 9 + j].choose:                res[x*9 + j].choose.append(res_num)    # 小方格    # x0, y0 = find_small_grid(x, y)    x0, y0 = x/3*3, y/3*3  # 分界点 0 3 6    for i in range(x0, x0+3, 1):        for j in range(y0, y0+3, 1):            if x != i and y != j:                if 2 == flag:                    for data in range(0, len(res[i*9 + j].choose), 1):                        if norepeat_num == int(res[i*9 + j].choose[data]):                            del res[i*9 + j].choose[data]                            break                if 1 == flag and not res_num in res[i * 9 + j].choose:                    res[i*9 + j].choose.append(res_num)def check_data(res, x, y, value):    # 检查位置x,y的值是否满足条件    # norepeat_num = int(res[x*9 + y].num) # 错在这里,不应该取res的值,也是醉了    norepeat_num = value # 1-9    # print norepeat_num    for i in range(0, 9, 1):        if x != i and norepeat_num == int(res[i * 9 + y].num): #             return False        if y != i and norepeat_num == int(res[x * 9 + i].num): #             return False    # 小方格    x0, y0 = x/3*3, y/3*3  # 分界点 0 3 6    for i in range(x0, x0+3, 1):        for j in range(y0, y0+3, 1):            if x != i and y != j and norepeat_num == int(res[i*9 + j].num):                return False    return Truedef get_next(res, x, y):    # 得到下一个未填项,包括x,y本身    if x == -1 and y == -1:        return -1, -1    if res[x * 9 + y].num == 0:        return x, y    for i in range(x*9+y+1, 9*9, 1):        if 0 == res[i].num:            return i/9, i%9    return -1, -1def searchResult(res, init_x, init_y):    # 结合初始条件,遍历每个格子,找到剩余格子可能的取值范围。    global cnt    cnt = cnt + 1    update_choose(res, init_x, init_y, res[init_x*9+init_y].num)    next_x, next_y = get_next(res, init_x, init_y) # 选下一个待填的格子    if -1 == next_x: # 递归退出        print '递归退出'        return True    for data in range(1,10,1): # 取值范围固定 1-9        if True == check_data(res, next_x, next_y, data):  # 符合递归条件            res[next_x * 9 + next_y].num = data            next_x1, next_y1 = get_next(res, next_x, next_y)  # 选下一个待填的格子            # print 'next', next_x1, next_y1            if -1 == next_x1:                return True            else:                end = searchResult(res, next_x1, next_y1)                if not end:  # 如果下一个格子找不到数,则回溯上一个格子,将其置0                    res[next_x * 9 + next_y].num = 0  # 这种回溯靠谱                else:  # 如果下一个格子找的到数,则继续往下一个格子查找                    return True    # 以下这种动态调整choose的方法,没有收敛到结果,需改进    # for data in res[next_x * 9 + next_y].choose: # 选一个可选的,取值范围变化    #     if True ==  check_data(res, next_x, next_y, data): # 符合递归条件    #         res[next_x * 9 + next_y].num = data    #         update_choose(res, next_x, next_y, data)    #         next_x1, next_y1 = get_next(res, next_x, next_y)  # 选下一个待填的格子    #         print 'next', next_x1, next_y1    #         if -1 == next_x1:    #             return True    #         else:    #             end = searchResult(res, next_x1, next_y1)    #             if not end: # 如果下一个格子找不到数,则回溯上一个格子,将其置0    #                 update_choose(res, next_x, next_y, 0)    #                 res[next_x * 9 + next_y].num = 0  # 这种回溯靠谱    #             else: # 如果下一个格子找的到数,则继续往下一个格子查找    #                 return True    #####    # return searchResult(res, next_x, next_y) # 这种回溯不靠谱,有点形式主义if __name__ == '__main__':    # a = [[0 for i in range(0,9,1)] for j in range(0,9,1)]    # sudoku_list = np.array(a)    sudoku_list = [[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]]    res = []    for i in range(0,9,1):        for j in range(0,9,1):            res.append(sudoku_cell(i,j))            res[i * 9 + j].x = i            res[i * 9 + j].y = j            res[i * 9 + j].num = sudoku_list[i][j]            res[i * 9 + j].choose = [1, 2, 3, 4, 5, 6, 7, 8, 9]    show_res(res)    cnt = 0    searchResult(res, 0, 0)    show_res(res)    print '递归次数为: %d' % cnt'''8 0 0 0 0 0 0 0 00 0 3 6 0 0 0 0 00 7 0 0 9 0 2 0 00 5 0 0 0 7 0 0 00 0 0 8 4 5 7 0 00 0 0 1 0 0 0 3 00 0 1 0 0 0 0 6 80 0 8 5 0 0 0 1 00 9 0 0 0 0 4 0 08 1 2 7 5 3 6 4 99 4 3 6 8 2 1 7 56 7 5 4 9 1 2 8 31 5 4 2 3 7 8 9 63 6 9 8 4 5 7 2 12 8 7 1 6 9 5 3 45 2 1 9 7 4 3 6 84 3 8 5 2 6 9 1 77 9 6 3 1 8 4 5 2递归次数为: 5067'''


最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台