Advertisement
Guest User

Untitled

a guest
Feb 24th, 2020
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.32 KB | None | 0 0
  1. from random import shuffle
  2. from copy import deepcopy
  3.  
  4.  
  5. n = 9
  6.  
  7.  
  8. def is_filled(table):
  9. for i in range(n):
  10. for j in range(n):
  11. if table[i][j] == -1:
  12. return False
  13. return True
  14.  
  15.  
  16. def remove_candidate(s, val):
  17. for i in range(len(s)):
  18. if s[i] == val:
  19. s[i], s[-1] = s[-1], s[i]
  20. s.pop()
  21. break
  22.  
  23.  
  24. def mark_cell(i, j, val, possible_moves, table=None):
  25. if table:
  26. table[i][j] = val
  27. for k in range(n):
  28. remove_candidate(possible_moves[i][k], val)
  29. remove_candidate(possible_moves[k][j], val)
  30. remove_candidate(possible_moves[i][j], k)
  31. x, y = i // 3 * 3, j // 3 * 3
  32. for dx in range(3):
  33. for dy in range(3):
  34. remove_candidate(possible_moves[x + dx][y + dy], val)
  35. possible_moves[i][j].append(val)
  36.  
  37.  
  38. log = []
  39. def solve_sudoku(table, possible_moves):
  40. if is_filled(table):
  41. return table
  42. x, y, le = -1, -1, 0
  43. for row in range(n):
  44. for col in range(n):
  45. if table[row][col] == -1:
  46. l_new = len(possible_moves[row][col])
  47. if x == -1 or l_new < le:
  48. x, y, le = row, col, l_new
  49. shuffle(possible_moves[x][y])
  50. for t in possible_moves[x][y]:
  51. new_table = deepcopy(table)
  52. new_possible_moves = deepcopy(possible_moves)
  53. mark_cell(x, y, t, new_possible_moves, new_table)
  54. new_table = solve_sudoku(new_table, new_possible_moves)
  55. if new_table:
  56. 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]]))
  57. return new_table
  58. return None
  59.  
  60.  
  61. table = [input().strip() for i in range(n)]
  62. result = [[int(x) - 1 for x in table[row]] for row in range(n)]
  63. possible_moves = [0] * n
  64. for row in range(n):
  65. possible_moves[row] = [[k for k in range(n)] for col in range(n)]
  66. for i in range(n):
  67. for j in range(n):
  68. if result[i][j] == -1:
  69. continue
  70. mark_cell(i, j, result[i][j], possible_moves)
  71. result = solve_sudoku(result, possible_moves)
  72. if result:
  73. for row in result:
  74. print(''.join([str(x + 1) for x in row]))
  75. log.reverse()
  76. for row in log:
  77. print(row)
  78. else:
  79. print("OOPS!")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement