python 求数独
程序员文章站
2022-04-14 12:55:00
计算数独 数独文件 代码 python 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 ......
计算数独
数独文件
000000002 006002000 000030040 000050000 001000006 000400070 050000000 000003109 470009000
代码
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_c def 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 sdk with open("4.sdk") as sdk_file: sdk = Sudoku(sdk_file) answer = get_answer(sdk) print(answer)