The other day, while surfing the internet, I found the following article: "The most difficult Sudoku in the world" created by a math expert over 3 months .. Whether it's true or not, I tried to solve this with Python3. The backtrack method is used for implementation. In short, it means that you are solving by force (´ ・ ω ・ `)
import itertools
class Sudoku(object):
def __init__(self):
self.matrix = [[0 for _ in range(9)] for _ in range(9)] #0 if blank
#Solve a given Sudoku puzzle
#Fills blank cells one after another, and returns True if all blank cells are filled.(False if not filled)
def solve(self):
#Elimination method:Fill in the squares that are unique
while True:
ls = []
for i, j in itertools.product(range(9), repeat=2):
if self.matrix[i][j] != 0: continue
numbers = self.__find_numbers(i, j)
if len(numbers) == 1: ls.append((i, j, numbers[0]))
if len(ls) == 0: break
for i, j, number in ls: self.matrix[i][j] = number
blanks = [(i, j) for i, j in itertools.product(range(9), repeat=2) if self.matrix[i][j] == 0]
if len(blanks) == 0: return True #If all the squares are already filled
first_i, first_j = blanks[0]
stack = [(0, first_number) for first_number in self.__find_numbers(first_i, first_j)]
#Backtrack method:
# 1.Put a number in a blank cell
# 2.Find out if there is a number in the next blank cell
# 3. 2.In, if it does not enter, back track
while stack:
idx, number = stack.pop()
i, j = blanks[idx]
self.matrix[i][j] = number
if idx == len(blanks) - 1: return True
next_i, next_j = blanks[idx + 1]
next_numbers = self.__find_numbers(next_i, next_j)
#Back truck
if len(next_numbers) == 0:
stack_top_idx = stack[-1][0]
for temp_idx in range(stack_top_idx, idx + 1):
temp_i, temp_j = blanks[temp_idx]
self.matrix[temp_i][temp_j] = 0
stack.extend((idx + 1, next_number) for next_number in next_numbers)
return False
#Store the numbers that can be put in a certain cell in set
def __find_numbers(self, i, j):
used_numbers = set()
#Examine the same row and the same column
for x in range(9): used_numbers |= {self.matrix[x][j], self.matrix[i][x]}
#Examine the same block
box_i_min, box_j_min = (i // 3) * 3, (j // 3) * 3
for box_i, box_j in itertools.product(range(box_i_min, box_i_min + 3), \
range(box_j_min, box_j_min + 3)):
used_numbers.add(self.matrix[box_i][box_j])
return set(range(1, 10)) - used_numbers
def __str__(self):
return "\n".join("".join(map(str, row)) for row in self.matrix)
if __name__ == "__main__":
matrix = '''
..53.....
8......2.
.7..1.5..
4....53..
.1..7...6
..32....8.
.6.5....9
..4....3.
.....97..
'''.split()
sudoku = Sudoku()
for i, j in itertools.product(range(9), repeat=2):
if matrix[i][j] == ".": continue
sudoku.matrix[i][j] = int(matrix[i][j])
print(sudoku)
sudoku.solve()
print("========")
print(sudoku)
# 005300000
# 800000020
# 070010500
# 400005300
# 010070006
# 003200080
# 060500009
# 004000030
# 000009700
# =========
# 145327698
# 839654127
# 672918543
# 496185372
# 218473956
# 753296481
# 367542819
# 984761235
# 521839764
The answer is the same as GIGAZINE, so it should be okay (`・ ω ・ ´) Shakin
Recommended Posts