python 求数独

2018-02-26 08:12:55来源:cnblogs.com作者:enrio人点击

分享

计算数独

数独文件

000000002006002000000030040000050000001000006000400070050000000000003109470009000

代码

class Sudoku:    ALL = set(range(1, 10))    def __init__(self, sdk_file):        self.sdk_matrix = [[int(c) for c in line]                           for line in sdk_file.read().split("/n")] if sdk_file else []    def get_row(self, row):        return self.sdk_matrix[row]    def get_col(self, col):        return [row[col] for row in self.sdk_matrix]    def get_matrix(self, row, col):        sr, sc = (row // 3) * 3, (col // 3) * 3        for r in range(sr, sr + 3):            for c in range(sc, sc + 3):                yield(self.sdk_matrix[r][c])    def get_avls(self, row, col):        return self.ALL - (set(self.get_matrix(row, col)) | set(self.get_row(row)) | set(self.get_col(col)))    def __getitem__(self, n):        return self.sdk_matrix[n]    def __str__(self):        return "/n".join([str(row) for row in self.sdk_matrix])    def clone(self):        sdk_c = Sudoku(None)        for row in range(9):            sdk_c.sdk_matrix.append([])            for col in range(9):                sdk_c.sdk_matrix[row].append(self.sdk_matrix[row][col])        return sdk_cdef get_answer(sdk):    has_filled, brunch = False, None    for row in range(9):        for col in range(9):            if sdk[row][col] != 0:                continue            avls = sdk.get_avls(row, col)            if len(avls) == 0:                return False            elif len(avls) == 1:                sdk[row][col] = avls.pop()                has_filled = True            elif not brunch or len(avls) < len(brunch[0]):                brunch = (avls, row, col)    if has_filled:        answer = get_answer(sdk)        if answer:            return answer    elif brunch:        for b in brunch[0]:            sdk_c = sdk.clone()            sdk_c[brunch[1]][brunch[2]] = b            answer = get_answer(sdk_c)            if answer:                return answer    else:        return sdkwith open("4.sdk") as sdk_file:    sdk = Sudoku(sdk_file)    answer = get_answer(sdk)    print(answer)

结果

流程图

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台