Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from random import shuffle
- from copy import deepcopy
- n = 9
- def is_filled(table):
- for i in range(n):
- for j in range(n):
- if table[i][j] == -1:
- return False
- return True
- def remove_candidate(s, val):
- for i in range(len(s)):
- if s[i] == val:
- s[i], s[-1] = s[-1], s[i]
- s.pop()
- break
- def mark_cell(i, j, val, possible_moves, table=None):
- if table:
- table[i][j] = val
- for k in range(n):
- remove_candidate(possible_moves[i][k], val)
- remove_candidate(possible_moves[k][j], val)
- remove_candidate(possible_moves[i][j], k)
- x, y = i // 3 * 3, j // 3 * 3
- for dx in range(3):
- for dy in range(3):
- remove_candidate(possible_moves[x + dx][y + dy], val)
- possible_moves[i][j].append(val)
- log = []
- def solve_sudoku(table, possible_moves):
- if is_filled(table):
- return table
- x, y, le = -1, -1, 0
- for row in range(n):
- for col in range(n):
- if table[row][col] == -1:
- l_new = len(possible_moves[row][col])
- if x == -1 or l_new < le:
- x, y, le = row, col, l_new
- shuffle(possible_moves[x][y])
- for t in possible_moves[x][y]:
- new_table = deepcopy(table)
- new_possible_moves = deepcopy(possible_moves)
- mark_cell(x, y, t, new_possible_moves, new_table)
- new_table = solve_sudoku(new_table, new_possible_moves)
- if new_table:
- log.append(str(t + 1) + " is correct value for cell" + '(' + str(x) + ', ' + str(y) + ') ' + "possible moves: " + str([t + 1 for t in possible_moves[x][y]]))
- return new_table
- return None
- table = [input().strip() for i in range(n)]
- result = [[int(x) - 1 for x in table[row]] for row in range(n)]
- possible_moves = [0] * n
- for row in range(n):
- possible_moves[row] = [[k for k in range(n)] for col in range(n)]
- for i in range(n):
- for j in range(n):
- if result[i][j] == -1:
- continue
- mark_cell(i, j, result[i][j], possible_moves)
- result = solve_sudoku(result, possible_moves)
- if result:
- for row in result:
- print(''.join([str(x + 1) for x in row]))
- log.reverse()
- for row in log:
- print(row)
- else:
- print("OOPS!")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement