Untitled
unknown
python
4 years ago
1.8 kB
6
Indexable
from random import shuffle from math import sqrt import sys class SudokuState: def __init__(self, size, field): self.size = size self.sqrt_size = int(sqrt(size)) self.size2 = size * size self.square = field self.base = list(range(10)) def free_nums(self, i, j) -> list: free = [1] * 10 free[0] = 0 sq_i = (i // self.sqrt_size) * self.sqrt_size sq_j = (j // self.sqrt_size) * self.sqrt_size for k in range(9): qi = k // self.sqrt_size qj = k % self.sqrt_size free[self.square[i][k]] = 0 free[self.square[k][j]] = 0 free[self.square[sq_i + qi][sq_j + qj]] = 0 return free def paste_num(state: SudokuState, k: int) -> bool: if k == state.size2: return True i: int = k // state.size j: int = k % state.size if state.square[i][j] != 0: return paste_num(state, k + 1) free = state.free_nums(i, j) shuffle(state.base) for val in state.base: if not free[val]: continue state.square[i][j] = val if paste_num(state, k + 1): return True state.square[i][j] = 0 return False def pretty_print(m): print('\n'.join(map(''.join, [map(str, r) for r in m]))) def main(data): field = [list(map(int, r)) for r in data.split()] sudoku = SudokuState(9, field) paste_num(sudoku, 0) pretty_print(sudoku.square) if __name__ == '__main__': main("""800000000 003600000 070090200 050007000 000045700 000100030 001000068 008500010 090000400""")
Editor is loading...