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

数独问题

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

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

解可能不唯一

类似穷举，

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

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

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

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

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

算法：

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

从1到9填这个空格子：

若某个数合理：

找下一个空格子(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-8
import os
import numpy as np

class 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,
    print

def 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 True

def 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, -1

def 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 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

8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2
递归次数为： 5067
'''